Задача: 131. Palindrome Partitioning
Сложность: Medium

Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы.

Пример:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

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

1⃣В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start.
Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки.

2⃣Для каждой сгенерированной подстроки проверяем, является ли она палиндромом.
Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова.

3⃣Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат.

😎 Решение:

class Solution {
    fun partition(s: String): List<List<String>> {
        val result = mutableListOf<List<String>>()
        dfs(s, mutableListOf(), result)
        return result
    }

    private fun isPalindrome(s: String): Boolean {
        return s == s.reversed()
    }

    private fun dfs(s: String, path: MutableList<String>, result: MutableList<List<String>>) {
        if (s.isEmpty()) {
            result.add(path.toList())
            return
        }
        for (i in 1..s.length) {
            if (isPalindrome(s.substring(0, i))) {
                val newPath = path.toMutableList()
                newPath.add(s.substring(0, i))
                dfs(s.substring(i), newPath, result)
            }
        }
    }
}

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

Задача: 1436. Destination City
Сложность: easy

Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi. Вернуть конечный город, то есть город, из которого нет пути в другой город.

Гарантируется, что граф путей образует линию без циклов, поэтому будет ровно один конечный город.

Пример:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

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

1⃣Для каждого города cityBi в paths проверьте, является ли он кандидатом на конечный город.

2⃣Для каждого кандидата проверьте, нет ли пути, ведущего из него (cityAi == candidate).

3⃣Верните город, который не имеет исходящих путей.

😎 Решение:

class Solution {
    fun destCity(paths: List<List<String>>): String {
        for (path in paths) {
            val candidate = path[1]
            var good = true
            for (p in paths) {
                if (p[0] == candidate) {
                    good = false
                    break
                }
            }
            if (good) {
                return candidate
            }
        }
        return ""
    }
}

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

Задача: 948. Bag of Tokens
Сложность: medium

Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.

Пример:

Input: tokens = [100], power = 50

Output: 0

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

1⃣Отсортировать массив tokens.
Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов.
Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore

2⃣Повторять следующие шаги, пока left не превысит right:
Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет.
Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет.
Обновить максимальный счет, если текущий счет больше максимального.

3⃣Вернуть максимальный счет.

😎 Решение:

class Solution {
    fun bagOfTokensScore(tokens: IntArray, power: Int): Int {
        tokens.sort()
        var power = power
        var left = 0
        var right = tokens.size - 1
        var score = 0
        var maxScore = 0
        
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left]
                score++
                left++
                maxScore = maxOf(maxScore, score)
            } else if (score > 0) {
                power += tokens[right]
                score--
                right--
            } else {
                break
            }
        }
        
        return maxScore
    }
}

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

Задача: 1312. Minimum Insertion Steps to Make a String Palindrome
Сложность: hard

Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки.

Верните минимальное количество шагов, необходимых для превращения s в палиндром.

Палиндром — это строка, которая читается одинаково как вперед, так и назад.

Пример:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

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

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

2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1.

3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее:

Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0.
Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n].
Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo).
В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)).

😎 Решение:

class Solution {
    private fun lcs(s1: String, s2: String, m: Int, n: Int, memo: Array<IntArray>): Int {
        if (m == 0 || n == 0) {
            return 0
        }
        if (memo[m][n] != -1) {
            return memo[m][n]
        }
        if (s1[m - 1] == s2[n - 1]) {
            memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo)
        } else {
            memo[m][n] = maxOf(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo))
        }
        return memo[m][n]
    }

    fun minInsertions(s: String): Int {
        val n = s.length
        val sReverse = s.reversed()
        val memo = Array(n + 1) { IntArray(n + 1) { -1 } }
        return n - lcs(s, sReverse, n, n, memo)
    }
}

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

Задача: 1512. Number of Good Pairs
Сложность: easy

Дан массив целых чисел nums, верните количество хороших пар.

Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j.

Пример:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

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

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерируйте i от 0 до nums.length:
Итерируйте j от i + 1 до nums.length:
Если nums[i] == nums[j], увеличьте ans на 1.

3⃣Верните ans.

😎 Решение:

class Solution {
    fun numIdenticalPairs(nums: IntArray): Int {
        var ans = 0
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                if (nums[i] == nums[j]) {
                    ans++
                }
            }
        }
        return ans
    }
}

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

Задача: 974. Subarray Sums Divisible by K
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

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

1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1.

2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений.

3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k.

😎 Решение:

class Solution {
    fun subarraysDivByK(nums: IntArray, k: Int): Int {
        var prefixMod = 0
        var result = 0
        val modGroups = IntArray(k)
        modGroups[0] = 1

        for (num in nums) {
            prefixMod = (prefixMod + num % k + k) % k
            result += modGroups[prefixMod]
            modGroups[prefixMod]++
        }

        return result
    }
}

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

Задача: 1422. Maximum Score After Splitting a String
Сложность: easy

Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку).

Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.

Пример:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

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

1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения.

2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц.

3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума.

😎 Решение:

class Solution {
    fun maxScore(s: String): Int {
        val ones = s.count { it == '1' }
        var zeros = 0
        var ans = 0
        var countOnes = ones

        for (i in 0 until s.length - 1) {
            if (s[i] == '1') {
                countOnes--
            } else {
                zeros++
            }
            ans = maxOf(ans, zeros + countOnes)
        }
        return ans
    }
}

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

Задача: 1252. Cells with Odd Values in a Matrix
Сложность: easy

Имеется матрица m x n, которая инициализирована всеми 0. Имеется двумерный массив indices, в котором каждый indices[i] = [ri, ci] представляет собой местоположение с индексом 0 для выполнения некоторых операций инкремента над матрицей. Для каждого местоположения indices[i] выполните оба следующих действия: увеличьте все ячейки в строке ri. Увеличьте все ячейки в столбце ci. Учитывая m, n и indices, верните количество нечетных ячеек в матрице после применения инкремента ко всем местоположениям в indices.

Пример:

Input: nums = [12,5,7,23]
Output: true

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

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

2⃣Для каждого элемента в indices увеличьте счетчики соответствующих строк и столбцов.

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

😎 Решение:

class Solution {
    fun oddCells(m: Int, n: Int, indices: Array<IntArray>): Int {
        val row_count = IntArray(m)
        val col_count = IntArray(n)

        for (index in indices) {
            row_count[index[0]]++
            col_count[index[1]]++
        }

        var odd_count = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                if ((row_count[i] + col_count[j]) % 2 == 1) {
                    odd_count++
                }
            }
        }

        return odd_count
    }
}

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

Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One
Сложность: medium

Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам:
Если текущее число четное, его нужно разделить на 2.
Если текущее число нечетное, нужно прибавить к нему 1.
Гарантируется, что для всех тестовых случаев всегда можно достичь единицы.

Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

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

1⃣Инициализируйте переменную operations значением 0.

2⃣Повторяйте операции, пока длина строки s больше 1:
Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит.
В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию.

3⃣Верните количество операций.

😎 Решение:

class Solution {
    fun numSteps(s: String): Int {
        var str = s.toCharArray().toMutableList()
        var operations = 0

        while (str.size > 1) {
            if (str.last() == '0') {
                str.removeAt(str.size - 1)
            } else {
                var i = str.size - 1
                while (i >= 0 && str[i] == '1') {
                    str[i] = '0'
                    i -= 1
                }
                if (i < 0) {
                    str.add(0, '1')
                } else {
                    str[i] = '1'
                }
            }
            operations += 1
        }

        return operations
    }
}

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

Задача: 1119. Remove Vowels from a String
Сложность: easy

Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.

Пример:

Input: s = "leetcodeisacommunityforcoders"
Output: "ltcdscmmntyfrcdrs"

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

1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае.

2⃣Инициализируйте пустую строку ans.

3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans.

😎 Решение:

class Solution {
    fun removeVowels(s: String): String {
        val ans = StringBuilder()
        for (char in s) {
            if (!isVowel(char)) {
                ans.append(char)
            }
        }
        return ans.toString()
    }

    private fun isVowel(c: Char): Boolean {
        return c in "aeiou"
    }
}

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

Задача: 301. Remove Invalid Parentheses
Сложность: hard

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

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

Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

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

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

2⃣Обработка текущего символа:
Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии.
Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения.

3⃣Завершение рекурсии и проверка:
Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны).
Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор.
Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений.

😎 Решение:

class Solution {
    private var validExpressions = mutableSetOf<String>()
    private var minimumRemoved = Int.MAX_VALUE

    private fun reset() {
        validExpressions.clear()
        minimumRemoved = Int.MAX_VALUE
    }

    private fun recurse(s: String, index: Int, leftCount: Int, rightCount: Int, expression: StringBuilder, removedCount: Int) {
        if (index == s.length) {
            if (leftCount == rightCount) {
                if (removedCount <= minimumRemoved) {
                    val possibleAnswer = expression.toString()
                    if (removedCount < minimumRemoved) {
                        validExpressions.clear()
                        minimumRemoved = removedCount
                    }
                    validExpressions.add(possibleAnswer)
                }
            }
            return
        }

        val currentCharacter = s[index]
        val length = expression.length

        if (currentCharacter != '(' && currentCharacter != ')') {
            expression.append(currentCharacter)
            recurse(s, index + 1, leftCount, rightCount, expression, removedCount)
            expression.deleteCharAt(length)
        } else {
            recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1)
            expression.append(currentCharacter)

            if (currentCharacter == '(') {
                recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount)
            } else if (rightCount < leftCount) {
                recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount)
            }

            expression.deleteCharAt(length)
        }
    }

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

Задача: 972. Equal Rational Numbers
Сложность: hard

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

Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:

<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

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

1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.

2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.

3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения.

😎 Решение:

class Solution {
    fun isRationalEqual(S: String, T: String): Boolean {
        val f1 = convert(S)
        val f2 = convert(T)
        return f1.n == f2.n && f1.d == f2.d
    }

    fun convert(S: String): Fraction {
        var state = 0
        val ans = Fraction(0, 1)
        var decimalSize = 0

        for (part in S.split("[.()]".toRegex())) {
            state++
            if (part.isEmpty()) continue
            val x = part.toLong()
            val sz = part.length

            when (state) {
                1 -> ans.iadd(Fraction(x, 1))
                2 -> {
                    ans.iadd(Fraction(x, 10.0.pow(sz.toDouble()).toLong()))
                    decimalSize = sz
                }
                else -> {
                    var denom = 10.0.pow(decimalSize.toDouble()).toLong()
                    denom *= (10.0.pow(sz.toDouble()) - 1).toLong()
                    ans.iadd(Fraction(x, denom))
                }
            }
        }
        return ans
    }
}

class Fraction(var n: Long, var d: Long) {
    init {
        val g = gcd(n, d)
        n /= g
        d /= g
    }

    fun iadd(other: Fraction) {
        val numerator = this.n * other.d + this.d * other.n
        val denominator = this.d * other.d
        val g = gcd(numerator, denominator)
        this.n = numerator / g
        this.d = denominator / g
    }

    companion object {
        fun gcd(x: Long, y: Long): Long {
            return if (x != 0L) gcd(y % x, x) else y
        }
    }
}

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

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval(var start: Int, var end: Int)

fun employeeFreeTime(schedule: List<List<Interval>>): List<Interval> {
    val intervals = mutableListOf<Interval>()
    for (employee in schedule) {
        intervals.addAll(employee)
    }
    
    intervals.sortBy { it.start }
    
    val merged = mutableListOf<Interval>()
    for (interval in intervals) {
        if (merged.isEmpty() || merged.last().end < interval.start) {
            merged.add(interval)
        } else {
            merged.last().end = maxOf(merged.last().end, interval.end)
        }
    }
    
    val freeTime = mutableListOf<Interval>()
    for (i in 1 until merged.size) {
        if (merged[i].start > merged[i - 1].end) {
            freeTime.add(Interval(merged[i - 1].end, merged[i].start))
        }
    }
    
    return freeTime
}

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

Задача: 1074. Number of Submatrices That Sum to Target
Сложность: hard

Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению.

Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.

Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.

Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

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

1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений.

2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target.

3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count.

😎 Решение:

class Solution {
    fun numSubmatrixSumTarget(matrix: Array<IntArray>, target: Int): Int {
        val r = matrix.size
        val c = matrix[0].size
        val ps = Array(r + 1) { IntArray(c + 1) }
        
        for (i in 1..r) {
            for (j in 1..c) {
                ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1]
            }
        }
        
        var count = 0
        
        for (r1 in 1..r) {
            for (r2 in r1..r) {
                val h = mutableMapOf<Int, Int>()
                h[0] = 1
                for (col in 1..c) {
                    val currSum = ps[r2][col] - ps[r1 - 1][col]
                    count += h.getOrDefault(currSum - target, 0)
                    h[currSum] = h.getOrDefault(currSum, 0) + 1
                }
            }
        }
        
        return count
    }
}

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

Задача №44. Wildcard Matching
Сложность: hard

Учитывая входную строку s и шаблон p, реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой '?' и '*', где:
- '?' соответствует любому отдельному символу.
- '*' соответствует любой последовательности символов (включая пустую последовательность).
- Соответствие должно охватывать всю входную строку.

Пример:

Input: s = "aa", p = "a*"  
Output: true  

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

1⃣ Использовать два указателя (i1 для шаблона, i2 для строки) и переменную start, отслеживающую последний *.

2⃣ Последовательно сравнивать символы строки и шаблона, учитывая правила ? и *.

3⃣ Если * найден, запоминать его позицию и двигаться дальше. Если несовпадение, но * был найден ранее, "откатить" указатель строки и попробовать снова.

😎 Решение:

class Solution {
    fun isMatch(s: String, p: String): Boolean {
        var i1 = 0
        var i2 = 0
        var start = -1
        var match = 0

        while (i2 < s.length) {
            if (i1 < p.length && (p[i1] == s[i2] || p[i1] == '?')) {
                i1++
                i2++
            } else if (i1 < p.length && p[i1] == '*') {
                start = i1
                match = i2
                i1++
            } else if (start != -1) {
                i1 = start + 1
                match++
                i2 = match
            } else {
                return false
            }
        }

        while (i1 < p.length && p[i1] == '*') {
            i1++
        }

        return i1 == p.length
    }
}

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

Задача: 179. Largest Number
Сложность: medium

Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его.

Поскольку результат может быть очень большим, вам необходимо вернуть строку вместо целого числа.

Пример:

Input: nums = [10,2]
Output: "210"

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

1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.

2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

class Solution {
    fun largestNumber(nums: IntArray): String {
        val strNums = nums.map { it.toString() }
        val sortedNums = strNums.sortedWith(compareByDescending<String> { a, b -> (a + b).compareTo(b + a) })
        if (sortedNums.first() == "0") {
            return "0"
        }
        return sortedNums.joinToString("")
    }
}

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

Задача: 113. Path Sum II
Сложность: medium

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

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

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

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

1⃣Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке.

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

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

😎 Решение:

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

class Solution {

    fun recurseTree(
        node: TreeNode?,
        remainingSum: Int,
        pathNodes: MutableList<Int>,
        pathsList: MutableList<MutableList<Int>>
    ) {
        if (node == null) {
            return
        }

        pathNodes.add(node.`val`)

        if (remainingSum == node.`val` && node.left == null && node.right == null) {
            pathsList.add(ArrayList(pathNodes))
        } else {
            node.left?.let {
                recurseTree(it, remainingSum - node.`val`, pathNodes, pathsList)
            }
            node.right?.let {
                recurseTree(it, remainingSum - node.`val`, pathNodes, pathsList)
            }
        }

        pathNodes.removeAt(pathNodes.size - 1)
    }

    fun pathSum(root: TreeNode?, sum: Int): MutableList<MutableList<Int>> {
        val pathsList = mutableListOf<MutableList<Int>>()
        recurseTree(root, sum, mutableListOf(), pathsList)
        return pathsList
    }
}

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

Задача: 1002. Find Common Characters
Сложность: easy

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

Пример:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

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

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

2⃣Обработка каждого слова:
Для каждого слова создайте временный массив для хранения частоты каждого символа в этом слове.
Обновите основной частотный массив, сравнивая его с временным массивом и сохраняя минимальные частоты каждого символа.

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

😎 Решение:

class Solution {
    fun commonChars(words: Array<String>): List<String> {
        val minFreq = IntArray(26) { Int.MAX_VALUE }
        
        for (word in words) {
            val freq = IntArray(26)
            for (char in word) {
                freq[char - 'a']++
            }
            for (i in 0..25) {
                minFreq[i] = minOf(minFreq[i], freq[i])
            }
        }
        
        val result = mutableListOf<String>()
        for (i in 0..25) {
            repeat(minFreq[i]) {
                result.add(('a' + i).toString())
            }
        }
        return result
    }
}

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

Задача: 244. Shortest Word Distance II
Сложность: medium

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

Реализуйте класс WordDistance:

WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.

Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

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

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

2⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎 Решение:

class WordDistance(words: Array<String>) {

    private val locations: MutableMap<String, MutableList<Int>> = HashMap()

    init {
        for (i in words.indices) {
            if (!locations.containsKey(words[i])) {
                locations[words[i]] = ArrayList()
            }
            locations[words[i]]!!.add(i)
        }
    }

    fun shortest(word1: String, word2: String): Int {
        val loc1 = locations[word1]!!
        val loc2 = locations[word2]!!
        var l1 = 0
        var l2 = 0
        var minDiff = Int.MAX_VALUE

        while (l1 < loc1.size && l2 < loc2.size) {
            minDiff = Math.min(minDiff, Math.abs(loc1[l1] - loc2[l2]))
            if (loc1[l1] < loc2[l2]) {
                l1++
            } else {
                l2++
            }
        }
        return minDiff
    }
}

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

Задача: 993. Cousins in Binary Tree
Сложность: easy

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

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

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

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

1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.

2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

3⃣Возврат результата:
Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false.

😎 Решение:

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

class Solution {
    private var parentX: TreeNode? = null
    private var parentY: TreeNode? = null
    private var depthX = -1
    private var depthY = -1
    
    fun isCousins(root: TreeNode?, x: Int, y: Int): Boolean {
        dfs(root, null, 0, x, y)
        return depthX == depthY && parentX != parentY
    }
    
    private fun dfs(node: TreeNode?, parent: TreeNode?, depth: Int, x: Int, y: Int) {
        if (node == null) return
        if (node.`val` == x) {
            parentX = parent
            depthX = depth
        } else if (node.`val` == y) {
            parentY = parent
            depthY = depth
        } else {
            dfs(node.left, node, depth + 1, x, y)
            dfs(node.right, node, depth + 1, x, y)
        }
    }
}

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

Задача: 514. Freedom Trail
Сложность: hard

В видеоигре Fallout 4 в квесте "Дорога к свободе" игрокам нужно добраться до металлического диска, называемого "Кольцо Свободы", и использовать его для набора определённого ключевого слова, чтобы открыть дверь.

Дана строка ring, представляющая код, выгравированный на внешнем кольце, и другая строка key, представляющая ключевое слово, которое нужно набрать. Верните минимальное количество шагов, чтобы набрать все символы ключевого слова.

Изначально первый символ кольца выровнен в направлении "12 часов". Вы должны набирать все символы из строки key один за другим, поворачивая кольцо по часовой или против часовой стрелки, чтобы каждый символ строки key выровнять в направлении "12 часов", а затем нажимая на центральную кнопку.

На этапе вращения кольца для набора символа key[i]:

Вы можете вращать кольцо по часовой или против часовой стрелки на одно место, что считается одним шагом. Конечная цель вращения — выровнять один из символов кольца в направлении "12 часов", и этот символ должен быть равен key[i].
Если символ key[i] уже выровнен в направлении "12 часов", нажмите центральную кнопку, чтобы набрать его, что также считается одним шагом. После нажатия вы можете начинать набирать следующий символ из key (следующий этап). Иначе, вы завершили весь набор.

Пример:

Input: ring = "godding", key = "godding"
Output: 13

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

1⃣Определите функцию countSteps для вычисления минимального пути между двумя индексами кольца ring. Создайте переменные ringLen и keyLen для хранения длин кольца и ключа соответственно. Создайте словарь bestSteps для хранения минимального количества шагов для нахождения символа на keyIndex, когда ringIndex кольца выровнен в позиции "12 часов".

2⃣Определите функцию tryLock, которая возвращает минимальное количество шагов для набора ключевого слова. Параметры: ringIndex, keyIndex, minSteps (минимальные шаги для набора ключевого слова на данный момент). Проверьте, равен ли keyIndex значению keyLen; если да, верните 0. Проверьте, есть ли пара (ringIndex, keyIndex) в bestSteps. Если есть, верните bestSteps[ringIndex][keyIndex]. Пройдите по каждому charIndex в ring. Если ring[charIndex] равен key[keyIndex], вычислите totalSteps, добавляя результат countSteps, единицу (нажатие центральной кнопки) и результат tryLock для следующего символа в key. Сохраните минимальное значение между totalSteps и текущим minSteps в minSteps. Сохраните minSteps для (ringIndex, keyIndex) в bestSteps.

3⃣Вызовите tryLock(0, 0, INT_MAX), начиная с нулевого индекса ring в позиции "12 часов" и первого символа в key. Наибольшее целое число передается как последний параметр, так как путь между нулевым индексом ring и первым символом key еще не определен.

😎 Решение:

class Solution {
    fun findRotateSteps(ring: String, key: String): Int {
        val ringLen = ring.length
        val keyLen = key.length
        val bestSteps = mutableMapOf<Pair<Int, Int>, Int>()
        
        fun countSteps(curr: Int, next: Int): Int {
            val stepsBetween = kotlin.math.abs(curr - next)
            val stepsAround = ringLen - stepsBetween
            return kotlin.math.min(stepsBetween, stepsAround)
        }
        
        fun tryLock(ringIndex: Int, keyIndex: Int): Int {
            bestSteps[Pair(ringIndex, keyIndex)]?.let { return it }
            
            if (keyIndex == keyLen) {
                bestSteps[Pair(ringIndex, keyIndex)] = 0
                return 0
            }
            
            var minSteps = Int.MAX_VALUE
            for (charIndex in ring.indices) {
                if (ring[charIndex] == key[keyIndex]) {
                    minSteps = minSteps.coerceAtMost(
                        countSteps(ringIndex, charIndex)
                        + 1
                        + tryLock(charIndex, keyIndex + 1)
                    )
                }
            }
            bestSteps[Pair(ringIndex, keyIndex)] = minSteps
            return minSteps
        }
        
        return tryLock(0, 0)
    }
}

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