Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

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

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

class Solution {
    fun atMostNGivenDigitSet(digits: Array<String>, n: Int): Int {
        val s = n.toString()
        val K = s.length
        val dp = IntArray(K + 1)
        dp[K] = 1

        for (i in K - 1 downTo 0) {
            for (d in digits) {
                if (d[0] < s[i]) {
                    dp[i] += Math.pow(digits.size.toDouble(), (K - i - 1).toDouble()).toInt()
                } else if (d[0] == s[i]) {
                    dp[i] += dp[i + 1]
                }
            }
        }

        for (i in 1 until K) {
            dp[0] += Math.pow(digits.size.toDouble(), i.toDouble()).toInt()
        }

        return dp[0]
    }
}

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

Задача: 1218. Longest Arithmetic Subsequence of Given Difference
Сложность: medium

Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference.

Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов.

Пример:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

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

1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1.

2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]:
Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference:
- если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference].
- в противном случае, установите before_a = 0.
Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]).

3⃣Верните answer после завершения итерации.

😎 Решение:

class Solution {
    fun longestSubsequence(arr: IntArray, difference: Int): Int {
        val dp = mutableMapOf<Int, Int>()
        var answer = 1
        
        for (a in arr) {
            val beforeA = dp.getOrDefault(a - difference, 0)
            dp[a] = beforeA + 1
            answer = maxOf(answer, dp[a]!!)
        }
        
        return answer
    }
}

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

Задача: 725. Split Linked List in Parts
Сложность: medium

Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.

Пример:

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

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

1⃣Определите общую длину связного списка.

2⃣Вычислите базовый размер каждой части и количество частей, которые должны быть на одну единицу длиннее.

3⃣Разделите список на части, присваивая каждую часть в массив результатов.

😎 Решение:

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

fun splitListToParts(root: ListNode?, k: Int): Array<ListNode?> {
    var length = 0
    var node = root
    while (node != null) {
        length++
        node = node.next
    }

    val partLength = length / k
    val extraParts = length % k

    val parts = Array<ListNode?>(k) { null }
    node = root
    for (i in 0 until k) {
        val partHead = node
        val partSize = partLength + if (i < extraParts) 1 else 0
        for (j in 0 until partSize - 1) {
            if (node != null) node = node.next
        }
        if (node != null) {
            val nextPart = node.next
            node.next = null
            node = nextPart
        }
        parts[i] = partHead
    }

    return parts
}

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

Задача №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.

Пример:

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]  

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

1⃣ Использовать рекурсивный бэктрекинг для генерации комбинаций.

2⃣ Добавлять (, если осталось добавить открывающие скобки.

3⃣ Добавлять ), если количество закрывающих скобок больше открывающих.

😎 Решение:

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()
        generate("", n, n, result)
        return result
    }

    private fun generate(current: String, left: Int, right: Int, result: MutableList<String>) {
        if (left == 0 && right == 0) {
            result.add(current)
            return
        }
        if (left > 0) generate(current + "(", left - 1, right, result)
        if (right > left) generate(current + ")", left, right - 1, result)
    }
}

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

Задача: 910. Smallest Range II
Сложность: medium

Вам дан целочисленный массив nums и целое число k. Для каждого индекса i, где 0 <= i < nums.length, измените nums[i] на nums[i] + k или nums[i] - k. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после изменения значений в каждом индексе.

Пример:

Input: nums = [1], k = 0
Output: 0

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

1⃣Отсортировать массив nums.

2⃣Рассчитать начальную разницу между максимальным и минимальным элементами.

3⃣Пройтись по всем элементам массива, пытаясь минимизировать разницу, изменяя текущий элемент на +k и -k и вычисляя новые максимальные и минимальные значения массива.

😎 Решение:

class Solution {
    fun smallestRangeII(nums: IntArray, k: Int): Int {
        val nums = nums.sorted()
        val n = nums.size
        var result = nums[n - 1] - nums[0]
        val minVal = nums[0]
        val maxVal = nums[n - 1]

        for (i in 0 until n - 1) {
            val high = maxOf(nums[i] + k, maxVal - k)
            val low = minOf(nums[i + 1] - k, minVal + k)
            result = minOf(result, high - low)
        }

        return result
    }
}

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

Задача: 562. Longest Line of Consecutive One in Matrix
Сложность: medium

Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.

Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.

Пример:

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

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

1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.

2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.

3⃣Верните максимальную длину.

😎 Решение:

class Solution {
    fun longestLine(mat: Array<IntArray>): Int {
        if (mat.isEmpty() || mat[0].isEmpty()) return 0
        
        val m = mat.size
        val n = mat[0].size
        var maxLength = 0
        
        val horizontal = Array(m) { IntArray(n) }
        val vertical = Array(m) { IntArray(n) }
        val diagonal = Array(m) { IntArray(n) }
        val antiDiagonal = Array(m) { IntArray(n) }
        
        for (i in mat.indices) {
            for (j in mat[0].indices) {
                if (mat[i][j] == 1) {
                    horizontal[i][j] = (if (j > 0) horizontal[i][j - 1] else 0) + 1
                    vertical[i][j] = (if (i > 0) vertical[i - 1][j] else 0) + 1
                    diagonal[i][j] = (if (i > 0 && j > 0) diagonal[i - 1][j - 1] else 0) + 1
                    antiDiagonal[i][j] = (if (i > 0 && j < n - 1) antiDiagonal[i - 1][j + 1] else 0) + 1
                    
                    maxLength = maxOf(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j])
                }
            }
        }
        
        return maxLength
    }
}

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

Задача: 521. Longest Uncommon Subsequence I
Сложность: easy

Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1.

Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них.

Пример:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

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

1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности.

2⃣В противном случае: Вычислите длины строк a и b. Верните длину более длинной строки.

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

😎 Решение:

class Solution {
    fun findLUSlength(a: String, b: String): Int {
        return if (a == b) {
            -1
        } else {
            maxOf(a.length, b.length)
        }
    }
}

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

Задача: 459. Repeated Substring Pattern
Сложность: easy

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

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

1⃣Создайте целочисленную переменную n, равную длине строки s.

2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2:
Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s.
Если pattern равен s, вернуть true.

3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false.

😎 Решение:

class Solution {
    fun repeatedSubstringPattern(s: String): Boolean {
        val n = s.length
        for (i in 1..n / 2) {
            if (n % i == 0) {
                val pattern = s.substring(0, i).repeat(n / i)
                if (s == pattern) {
                    return true
                }
            }
        }
        return false
    }
}

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

Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени.

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:

class TopVotedCandidate(persons: IntArray, times: IntArray) {
    private val times = times
    private val leaders = mutableListOf<Int>()

    init {
        val counts = mutableMapOf<Int, Int>()
        var leader = -1

        for (person in persons) {
            counts[person] = counts.getOrDefault(person, 0) + 1
            if (counts[person]!! >= counts.getOrDefault(leader, 0)) {
                leader = person
            }
            leaders.add(leader)
        }
    }

    fun q(t: Int): Int {
        var left = 0
        var right = times.size - 1
        while (left < right) {
            val mid = (left + right + 1) / 2
            if (times[mid] <= t) {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return leaders[left]
    }
}

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

Задача: 243. Shortest Word Distance
Сложность: easy

Дан массив строк wordsDict и две разные строки, которые уже существуют в массиве: word1 и word2. Верните кратчайшее расстояние между этими двумя словами в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

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

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

2⃣При каждом обнаружении первого слова переберите массив в поисках ближайшего вхождения второго слова, сохраняя позицию и сравнивая расстояние с предыдущими найденными.

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

😎 Решение:

class Solution {
    fun shortestDistance(words: Array<String>, word1: String, word2: String): Int {
        var minDistance = words.size
        for (i in words.indices) {
            if (words[i] == word1) {
                for (j in words.indices) {
                    if (words[j] == word2) {
                        minDistance = kotlin.math.min(minDistance, kotlin.math.abs(i - j))
                    }
                }
            }
        }
        return minDistance
    }
}

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

Задача: 1669. Merge In Between Linked Lists
Сложность: medium

Вам даны два связанных списка: list1 и list2 размером n и m соответственно.

Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.

Синие ребра и узлы на рисунке в вверху поста указывают на результат:

Пример:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

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

1⃣Инициализация и добавление узлов из list1 до узла a в массив:

Инициализировать переменную index равную 0 и current1 равную list1.
Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index.

2⃣Добавление узлов из list2 в массив:
Инициализировать current2 равную list2.
Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next.

3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка:
Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1.
Добавлять узлы из current1 в массив, пока current1 не станет null.
Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его.

😎 Решение:

class Solution {
    fun mergeInBetween(list1: ListNode?, a: Int, b: Int, list2: ListNode?): ListNode? {
        val mergeArray = mutableListOf<Int>()
        var index = 0
        var current1 = list1
        
        while (index < a) {
            mergeArray.add(current1!!.`val`)
            current1 = current1.next
            index++
        }
        
        var current2 = list2
        while (current2 != null) {
            mergeArray.add(current2.`val`)
            current2 = current2.next
        }
        
        while (index < b + 1) {
            current1 = current1!!.next
            index++
        }
        
        while (current1 != null) {
            mergeArray.add(current1.`val`)
            current1 = current1.next
        }
        
        var resultList: ListNode? = null
        for (val in mergeArray.asReversed()) {
            val newNode = ListNode(val, resultList)
            resultList = newNode
        }
        
        return resultList
    }
}

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

Задача: 1004. Max Consecutive Ones III
Сложность: medium

Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.

Пример:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

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

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

2⃣Перемещение правого указателя и обновление окна:
Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k).

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

😎 Решение:

class Solution {
    fun longestOnes(nums: IntArray, k: Int): Int {
        var left = 0
        var maxOnes = 0
        var zeroCount = 0

        for (right in nums.indices) {
            if (nums[right] == 0) {
                zeroCount++
            }

            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--
                }
                left++
            }

            maxOnes = maxOf(maxOnes, right - left + 1)
        }

        return maxOnes
    }
}

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

Задача: 1006. Clumsy Factorial
Сложность: medium

Факториал целого положительного числа n - это произведение всех целых положительных чисел, меньших или равных n. Например, факториал(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.
Мы составляем неуклюжий факториал, используя целые числа в порядке убывания, заменяя операции умножения на фиксированную последовательность операций с умножением "*", делением "/", сложением "+" и вычитанием "-" в этом порядке. Например, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Однако эти операции по-прежнему применяются с использованием обычного порядка операций арифметики. Мы выполняем все шаги умножения и деления перед шагами сложения и вычитания, а шаги умножения и деления выполняются слева направо. Кроме того, деление, которое мы используем, является делением с полом, так что 10 * 9 / 8 = 90 / 8 = 11. Учитывая целое число n, верните неуклюжий факториал n.

Пример:

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

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

1⃣Инициализация переменных и обработка первых трех чисел:
Создайте переменные для хранения результата и текущего значения.
Если n меньше или равен 3, обработайте случай отдельно, выполняя операции в порядке убывания, и верните результат.

2⃣Выполнение операций в цикле:
Создайте цикл, который будет обрабатывать числа от n до 1 в порядке убывания.
В цикле выполняйте операции *, /, +, и - последовательно.
Обновляйте текущий результат на каждом шаге в зависимости от остатка от деления текущего индекса на 4.

3⃣Учет оставшихся операций и возврат результата:
После завершения цикла добавьте или вычтите оставшиеся числа (если есть) к результату.
Верните окончательный результат.

😎 Решение:

class Solution {
    fun clumsy(n: Int): Int {
        if (n == 0) return 0
        if (n == 1) return 1
        if (n == 2) return 2 * 1
        if (n == 3) return 3 * 2 / 1
        
        var res = n * (n - 1) / (n - 2)
        var n = n - 3
        if (n > 0) res += n
        n -= 1
        
        while (n > 0) {
            res -= n * (n - 1) / (n - 2)
            n -= 3
            if (n > 0) res += n
            n -= 1
        }
        
        return res
    }
}

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

Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"
Output: 5

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

1⃣Создать двумерный массив dp, где dp[i][j] представляет количество допустимых перестановок длины i, оканчивающихся на j.

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

class Solution {
    fun numPermsDISequence(s: String): Int {
        val MOD = 1_000_000_007
        val n = s.length
        val dp = Array(n + 1) { IntArray(n + 1) }
        dp[0][0] = 1

        for (i in 1..n) {
            for (j in 0..i) {
                if (s[i - 1] == 'D') {
                    for (k in j until i) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD
                    }
                } else {
                    for (k in 0 until j) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD
                    }
                }
            }
        }

        var result = 0
        for (j in 0..n) {
            result = (result + dp[n][j]) % MOD
        }

        return result
    }
}

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

Задача: 624. Maximum Distance in Arrays
Сложность: medium

Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.

Пример:

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

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

1⃣Найдите минимальный элемент из всех первых элементов массивов и максимальный элемент из всех последних элементов массивов.

2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами.

3⃣Верните это максимальное расстояние.

😎 Решение:

fun maxDistance(arrays: List<List<Int>>): Int {
    var minVal = arrays[0][0]
    var maxVal = arrays[0].last()
    var maxDistance = 0
    
    for (i in 1 until arrays.size) {
        maxDistance = maxOf(maxDistance, kotlin.math.abs(arrays[i].last() - minVal), kotlin.math.abs(arrays[i][0] - maxVal))
        minVal = minOf(minVal, arrays[i][0])
        maxVal = maxOf(maxVal, arrays[i].last())
    }
    
    return maxDistance
}

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

Задача: 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

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