Задача: 1268. Search Suggestions System
Сложность: medium

Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord.

Пример:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

👨‍💻 Алгоритм:

1⃣Отсортируйте массив продуктов.

2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу.

3⃣Сохраняйте не более трех лексикографически минимальных продуктов для каждого префикса.

😎 Решение:

class Solution {
    fun suggestedProducts(products: Array<String>, searchWord: String): List<List<String>> {
        products.sort()
        val result = mutableListOf<List<String>>()
        var prefix = ""
        for (char in searchWord) {
            prefix += char
            val suggestions = products.filter { it.startsWith(prefix) }.take(3)
            result.add(suggestions)
        }
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 661. Image Smoother
Сложность: easy

Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.

Пример:

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

👨‍💻 Алгоритм:

1⃣Инициализация:
Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания.

2⃣Обработка каждой ячейки:
Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку).
Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы.

3⃣Возврат результата:
Верните результирующую матрицу после применения сглаживания ко всем ячейкам.

😎 Решение:

class Solution {
    fun imageSmoother(img: Array<IntArray>): Array<IntArray> {
        val m = img.size
        val n = img[0].size
        val result = Array(m) { IntArray(n) }
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                var count = 0
                var total = 0
                for (ni in maxOf(0, i - 1)..minOf(m - 1, i + 1)) {
                    for (nj in maxOf(0, j - 1)..minOf(n - 1, j + 1)) {
                        total += img[ni][nj]
                        count += 1
                    }
                }
                result[i][j] = total / count
            }
        }
        
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1014. Best Sightseeing Pair
Сложность: medium

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.

😎 Решение:

class Solution {
    fun maxScoreSightseeingPair(values: IntArray): Int {
        var maxScore = 0
        var maxIPlusValue = values[0]
        
        for (j in 1 until values.size) {
            maxScore = maxOf(maxScore, maxIPlusValue + values[j] - j)
            maxIPlusValue = maxOf(maxIPlusValue, values[j] + j)
        }
        
        return maxScore
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

👨‍💻 Алгоритм:

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

2⃣Определение границ компонента:
Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет.

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

class Solution {
    fun colorBorder(grid: Array<IntArray>, row: Int, col: Int, color: Int): Array<IntArray> {
        val m = grid.size
        val n = grid[0].size
        val originalColor = grid[row][col]
        val visited = Array(m) { BooleanArray(n) }
        val borders = mutableListOf<Pair<Int, Int>>()

        fun dfs(r: Int, c: Int) {
            visited[r][c] = true
            var isBorder = false
            for ((dr, dc) in listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)) {
                val nr = r + dr
                val nc = c + dc
                if (nr in 0 until m && nc in 0 until n) {
                    if (!visited[nr][nc]) {
                        if (grid[nr][nc] == originalColor) {
                            dfs(nr, nc)
                        } else {
                            isBorder = true
                        }
                    }
                } else {
                    isBorder = true
                }
            }
            if (isBorder || r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                borders.add(r to c)
            }
        }

        dfs(row, col)
        for ((r, c) in borders) {
            grid[r][c] = color
        }

        return grid
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard

Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.

Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз.

Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить).

Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

👨‍💻 Алгоритм:

1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).

2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием:
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой).
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).

3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.

😎 Решение:

class Solution {
    fun maxProfit(k: Int, prices: IntArray): Int {
        val n = prices.size
        if (n <= 0 || k <= 0) return 0
        if (k * 2 >= n) {
            return prices.toList().windowed(2, 1).sumOf { maxOf(0, it[1] - it[0]) }
        }
        val dp = Array(n) { Array(k + 1) { IntArray(2) { Int.MIN_VALUE / 2 } } }
        dp[0][0][0] = 0
        dp[0][1][1] = -prices[0]

        for (i in 1 until n) {
            for (j in 0..k) {
                dp[i][j][0] = maxOf(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
                if (j > 0) {
                    dp[i][j][1

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1423. Maximum Points You Can Obtain from Cards
Сложность: medium

Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного массива cardPoints.
За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт.
Ваш результат - это сумма очков взятых карт.

Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить.

Пример:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

👨‍💻 Алгоритм:

1⃣Инициализируйте два массива размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в массиве.

2⃣Рассчитайте префиксные суммы для первых k карт и последних k карт.

3⃣Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала массива и k - i карт с конца, обновляя максимальный результат при необходимости.

😎 Решение:

class Solution {
    fun maxScore(cardPoints: IntArray, k: Int): Int {
        val n = cardPoints.size
        val frontSetOfCards = IntArray(k + 1)
        val rearSetOfCards = IntArray(k + 1)
        
        for (i in 0 until k) {
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i]
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i]
        }
        
        var maxScore = 0
        for (i in 0..k) {
            val currentScore = frontSetOfCards[i] + rearSetOfCards[k - i]
            maxScore = maxOf(maxScore, currentScore)
        }
        
        return maxScore
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 638. Shopping Offers
Сложность: medium

В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.

Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

👨‍💻 Алгоритм:

1⃣Рекурсивное вычисление стоимости
Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений.

2⃣Использование специальных предложений
Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, учитывая это предложение.

3⃣Выбор минимальной стоимости
Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость.

😎 Решение:

class Solution {
    fun shoppingOffers(price: List<Int>, special: List<List<Int>>, needs: List<Int>): Int {
        val memo = mutableMapOf<List<Int>, Int>()
        return dfs(price, special, needs, memo)
    }

    private fun dfs(price: List<Int>, special: List<List<Int>>, needs: List<Int>, memo: MutableMap<List<Int>, Int>): Int {
        if (needs in memo) return memo[needs]!!
        
        var minPrice = needs.indices.sumBy { needs[it] * price[it] }
        
        for (offer in special) {
            val newNeeds = needs.indices.map { needs[it] - offer[it] }
            if (newNeeds.all { it >= 0 }) {
                minPrice = minOf(minPrice, offer.last() + dfs(price, special, newNeeds, memo))
            }
        }
        
        memo[needs] = minPrice
        return minPrice
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 206. Reverse Linked List
Сложность: easy

Дан односвязный список, разверните этот список и верните развернутый список.

Пример:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

👨‍💻 Алгоритм:

1⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.

2⃣Пройдитесь по списку с помощью цикла:
Сохраните ссылку на следующий узел curr в переменную nextTemp.
Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.
Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.

3⃣После завершения цикла верните prev как новую голову развернутого списка.

😎 Решение:

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        var prev: ListNode? = null
        var curr = head
        while (curr != null) {
            val nextTemp = curr.next
            curr.next = prev
            prev = curr
            curr = nextTemp
        }
        return prev
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 813. Largest Sum of Averages
Сложность: medium

Вам дан целочисленный массив nums и целое число k. Вы можете разбить массив на не более чем k непустых смежных подмассивов. Оценка разбиения равна сумме средних значений каждого подмассива.

Обратите внимание, что при разбиении должны быть использованы все целые числа из nums, и что оценка не обязательно является целым числом.

Верните максимальную оценку, которую можно достичь среди всех возможных разбиений. Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

👨‍💻 Алгоритм:

1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N).

2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i).

3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)).

😎 Решение:

class Solution {
    fun largestSumOfAverages(A: IntArray, K: Int): Double {
        val P = DoubleArray(A.size + 1)
        for (i in A.indices) {
            P[i + 1] = P[i] + A[i]
        }
        
        fun average(i: Int, j: Int): Double {
            return (P[j] - P[i]) / (j - i)
        }

        val N = A.size
        val dp = DoubleArray(N) { average(it, N) }
        for (k in 0 until K - 1) {
            for (i in 0 until N) {
                for (j in i + 1 until N) {
                    dp[i] = maxOf(dp[i], average(i, j) + dp[j])
                }
            }
        }
        
        return dp[0]
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 941. Valid Mountain Array
Сложность: easy

Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Пример:

Input: arr = [2,1]
Output: false

👨‍💻 Алгоритм:

1⃣Убедиться, что длина массива не меньше 3.

2⃣Найти вершину горы, которая удовлетворяет условиям горного массива.
Проверить, что все элементы слева от вершины строго возрастают.
Проверить, что все элементы справа от вершины строго убывают.

3⃣Вернуть true, если оба условия выполнены, иначе вернуть false.

😎 Решение:

class Solution {
    fun validMountainArray(arr: IntArray): Boolean {
        if (arr.size < 3) return false
        
        var i = 1
        while (i < arr.size && arr[i] > arr[i - 1]) i++
        
        if (i == 1 || i == arr.size) return false
        
        while (i < arr.size && arr[i] < arr[i - 1]) i++
        
        return i == arr.size
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 537. Complex Number Multiplication
Сложность: medium

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

👨‍💻 Алгоритм:

1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

class Solution {
    fun complexNumberMultiply(a: String, b: String): String {
        val x = a.split("+", "i")
        val y = b.split("+", "i")
        val a_real = x[0].toInt()
        val a_img = x[1].toInt()
        val b_real = y[0].toInt()
        val b_img = y[1].toInt()
        val realPart = a_real * b_real - a_img * b_img
        val imaginaryPart = a_real * b_img + a_img * b_real
        return "$realPart+$imaginaryPart" + "i"
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1000. Minimum Cost to Merge Stones
Сложность: hard

Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.

Пример:

Input: stones = [3,2,4,1], k = 2
Output: 20

👨‍💻 Алгоритм:

1⃣Проверка на возможность объединения:
Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1.

2⃣Инициализация и динамическое программирование:
Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней.
Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве.

3⃣Заполнение таблицы dp:
Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование.
Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения.

😎 Решение:

class Solution {
    fun mergeStones(stones: IntArray, k: Int): Int {
        val n = stones.size
        if ((n - 1) % (k - 1) != 0) return -1

        val prefix = IntArray(n + 1)
        for (i in stones.indices) {
            prefix[i + 1] = prefix[i] + stones[i]
        }

        val dp = Array(n) { IntArray(n) }
        for (m in k..n) {
            for (i in 0..n - m) {
                val j = i + m - 1
                dp[i][j] = Int.MAX_VALUE
                for (t in i until j step k - 1) {
                    dp[i][j] = minOf(dp[i][j], dp[i][t] + dp[t + 1][j])
                }
                if ((j - i) % (k - 1) == 0) {
                    dp[i][j] += prefix[j + 1] - prefix[i]
                }
            }
        }

        return dp[0][n - 1]
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1216. Valid Palindrome III
Сложность: hard

Дана строка s и целое число k. Верните true, если s является k-палиндромом.
Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.

Пример:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

👨‍💻 Алгоритм:

1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j.

2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo.

3⃣Реализуйте основные случаи рекурсивного вычисления: если символы на позициях i и j совпадают, продолжайте проверку для подстроки без этих символов. В противном случае, рассмотрите два варианта удаления символов и выберите минимальное количество удалений, добавив 1 за текущее удаление.

😎 Решение:

class Solution {
    private lateinit var memo: Array<IntArray?>

    fun isValidPalindrome(s: String, k: Int): Boolean {
        val n = s.length
        memo = Array(n) { IntArray(n) { -1 } }
        return isValidPalindromeHelper(s.toCharArray(), 0, n - 1) <= k
    }

    private fun isValidPalindromeHelper(s: CharArray, i: Int, j: Int): Int {
        if (i == j) return 0
        if (i == j - 1) return if (s[i] != s[j]) 1 else 0
        if (memo[i][j] != -1) return memo[i][j]
        memo[i][j] = if (s[i] == s[j]) {
            isValidPalindromeHelper(s, i + 1, j - 1)
        } else {
            1 + minOf(isValidPalindromeHelper(s, i + 1, j), isValidPalindromeHelper(s, i, j - 1))
        }
        return memo[i][j]
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1208. Get Equal Substrings Within Budget
Сложность: medium

Вам даны две строки s и t одинаковой длины и целое число maxCost.
Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).

Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0.

Пример:

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost.
start для хранения начального индекса текущей подстроки.
currCost для хранения текущих затрат на преобразование подстроки s в t.

2⃣Итерация по индексам от 0 до N-1:
Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost.
Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost.
Обновить maxLen длиной текущей подстроки.

3⃣Возврат maxLen как результата.

😎 Решение:

class Solution {
    fun equalSubstring(s: String, t: String, maxCost: Int): Int {
        val N = s.length
        
        var maxLen = 0
        var start = 0
        var currCost = 0
        
        for (i in 0 until N) {
            currCost += kotlin.math.abs(s[i] - t[i])
            
            while (currCost > maxCost) {
                currCost -= kotlin.math.abs(s[start] - t[start])
                start++
            }
            
            maxLen = maxOf(maxLen, i - start + 1)
        }
        
        return maxLen
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 663. Equal Tree Partition
Сложность: medium

Дан корень бинарного дерева. Верните true, если можно разделить дерево на два дерева с равными суммами значений после удаления ровно одного ребра из исходного дерева.

Пример:

Input: root = [5,10,10,null,null,2,3]
Output: true

👨‍💻 Алгоритм:

1⃣Вычисление общей суммы:
Напишите функцию для вычисления общей суммы всех узлов дерева.

2⃣Проверка возможности разделения:
Напишите функцию, чтобы рекурсивно проверить, может ли поддерево быть равно половине общей суммы. Если такое поддерево найдено, значит дерево можно разделить на две части с равными суммами.

3⃣Валидация и возврат результата:
Проверьте, что общая сумма четная (так как только в этом случае возможно её разделение на две равные части), и используйте функцию проверки поддерева, чтобы определить, можно ли разделить дерево на две части с равными суммами.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun checkEqualTree(root: TreeNode?): Boolean {
        if (root == null) return false
        val totalSum = sumTree(root)
        if (totalSum % 2 != 0) return false
        val target = totalSum / 2
        return checkSubtreeSum(root, target, root)
    }

    private fun sumTree(node: TreeNode?): Int {
        if (node == null) return 0
        return node.`val` + sumTree(node.left) + sumTree(node.right)
    }

    private fun checkSubtreeSum(node: TreeNode?, target: Int, root: TreeNode): Boolean {
        if (node == null) return false
        if (node !== root && sumTree(node) == target) {
            return true
        }
        return checkSubtreeSum(node.left, target, root) || checkSubtreeSum(node.right, target, root)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 39. Combination Sum
Сложность: medium

Дан массив candidates уникальных целых чисел и целевое число target.
Верните все уникальные комбинации, сумма которых равна target.
Одно число можно использовать неограниченное количество раз.

Пример:

  
Input: candidates = [2,3,5], target = 8  
Output: [[2,2,2,2],[2,3,3],[3,5]]  

👨‍💻 Алгоритм:

1⃣Используем backtracking, начиная с пустой комбинации и target.

2⃣Если target == 0, добавляем комбинацию в результат.

3⃣Если target < 0, отменяем текущий путь, иначе продолжаем рекурсию, начиная с текущего индекса.

😎 Решение:

class Solution {
    fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
        val results = mutableListOf<List<Int>>()

        fun backtrack(remain: Int, comb: MutableList<Int>, start: Int) {
            when {
                remain == 0 -> results.add(ArrayList(comb))
                remain > 0 -> {
                    for (i in start until candidates.size) {
                        comb.add(candidates[i])
                        backtrack(remain - candidates[i], comb, i)
                        comb.removeAt(comb.size - 1)
                    }
                }
            }
        }

        backtrack(target, mutableListOf(), 0)
        return results
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 927. Three Equal Parts
Сложность: hard

Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с i + 1 < j, такой что: arr[0], arr[1], ..., arr[i] - это первая часть, arr[i + 1], arr[i + 2], ...., arr[j - 1] - вторая часть, и arr[j], arr[j + 1], ..., arr[arr.length - 1] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение.

Пример:

Input: arr = [1,0,1,0,1]
Output: [0,3]

👨‍💻 Алгоритм:

1⃣Подсчитать количество единиц в массиве.

2⃣Если количество единиц не делится на три, вернуть [-1, -1].
Найти индексы начала каждой части, игнорируя ведущие нули.
Использовать эти индексы для проверки, могут ли три части быть одинаковыми.

3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1].

😎 Решение:

class Solution {
    fun threeEqualParts(arr: IntArray): IntArray {
        val ones = arr.sum()
        if (ones % 3 != 0) return intArrayOf(-1, -1)
        if (ones == 0) return intArrayOf(0, arr.size - 1)

        val partOnes = ones / 3
        var first = 0
        var second = 0
        var third = 0
        var cnt = 0
        for (i in arr.indices) {
            if (arr[i] == 1) {
                when (cnt) {
                    0 -> first = i
                    partOnes -> second = i
                    2 * partOnes -> third = i
                }
                cnt++
            }
        }

        while (third < arr.size && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++
            second++
            third++
        }

        return if (third == arr.size) intArrayOf(first - 1, second) else intArrayOf(-1, -1)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 66. Plus One
Сложность: easy

Вам дано большое число, представленное в виде массива целых чисел digits, где каждый элемент digits[i] — это i-я цифра числа. Цифры расположены в порядке от старшей к младшей слева направо. Большое число не содержит ведущих нулей.

Увеличьте большое число на один и верните результирующий массив цифр.

Пример:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

👨‍💻 Алгоритм:

1⃣Проходим по входному массиву, начиная с конца массива.

2⃣Устанавливаем все девятки на конце массива в ноль. Если мы встречаем цифру, не равную девяти, увеличиваем её на один. Работа выполнена — возвращаем массив цифр.

3⃣Мы здесь, потому что все цифры были равны девяти. Теперь они все установлены в ноль. Затем мы добавляем цифру 1 в начало остальных цифр и возвращаем результат.

😎 Решение:

class Solution {
    fun plusOne(digits: IntArray): IntArray {
        val n = digits.size
        for (i in n - 1 downTo 0) {
            if (digits[i] == 9) {
                digits[i] = 0
            } else {
                digits[i]++
                return digits
            }
        }
        val result = IntArray(n + 1)
        result[0] = 1
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 358. Rearrange String k Distance Apart
Сложность: hard

Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "".

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

👨‍💻 Алгоритм:

1⃣Создайте словарь частот для символов строки и определите максимальную частоту.

2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов.

3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎 Решение:

class Solution {
    fun rearrangeString(s: String, k: Int): String {
        val freqs = mutableMapOf<Char, Int>()
        var maxFreq = 0
        
        for (char in s) {
            freqs[char] = freqs.getOrDefault(char, 0) + 1
            maxFreq = maxOf(maxFreq, freqs[char]!!)
        }
        
        val mostChars = freqs.filter { it.value == maxFreq }.keys
        val secondChars = freqs.filter { it.value == maxFreq - 1 }.keys
        
        val segments = Array(maxFreq) { StringBuilder() }
        
        for (i in 0 until maxFreq) {
            for (char in mostChars) {
                segments[i].append(char)
            }
            if (i < maxFreq - 1) {
                for (char in secondChars) {
                    segments[i].append(char)
                }
            }
        }
        
        var segmentId = 0
        
        for ((char, freq) in freqs) {
            if (char in mostChars || char in secondChars) {
                continue
            }
            
            var freq = freq
            while (freq > 0) {
                segments[segmentId].append(char)
                segmentId = (segmentId + 1) % (maxFreq - 1)
                freq--
            }
        }
        
        for (i in 0 until maxFreq - 1) {
            if (segments[i].length < k) {
                return ""
            }
        }
        
        return segments.joinToString("") { it.toString() }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов.

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

👨‍💻 Алгоритм:

1⃣Инициализация и построение частотного массива:
Создайте хеш-таблицу для отслеживания частот элементов массива arr.
Итеративно увеличивайте частоту элементов в хеш-таблице.

2⃣Сортировка и удаление элементов:
Создайте массив частот и заполните его значениями из хеш-таблицы.
Отсортируйте массив частот.
Инициализируйте переменную для отслеживания числа удаленных элементов и итеративно добавляйте частоты, пока количество удаленных элементов не превысит k.

3⃣Возвращение результата:
Если количество удаленных элементов превысило k, верните оставшееся количество уникальных элементов.
Если все элементы были удалены, верните 0.

😎 Решение:

class Solution {
    fun findLeastNumOfUniqueInts(arr: IntArray, k: Int): Int {
        val freqMap = mutableMapOf<Int, Int>()
        for (num in arr) {
            freqMap[num] = freqMap.getOrDefault(num, 0) + 1
        }
        
        val frequencies = freqMap.values.sorted()
        
        var elementsRemoved = 0
        for (i in frequencies.indices) {
            elementsRemoved += frequencies[i]
            if (elementsRemoved > k) {
                return frequencies.size - i
            }
        }
        
        return 0
    }
}

Ставь 👍 и забирай 📚 Базу знаний