Задача: 27. Remove Element
Сложность: easy

Учитывая целочисленный массив nums и целочисленное значение val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в nums, которые не равны val.

Пример:

Input: nums = [3,2,2,3], val = 3  
Output: 2  

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

1⃣ Используем указатель index для отслеживания позиции, на которую записываются элементы, не равные val.

2⃣ Проходим по массиву nums, копируя в начало только элементы, отличные от val.

3⃣ Возвращаем значение index, которое соответствует количеству оставшихся элементов.

😎 Решение:

fun removeElement(nums: IntArray, `val`: Int): Int {
    var index = 0
    for (num in nums) {
        if (num != `val`) {
            nums[index] = num
            index++
        }
    }
    return index
}

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

Задача: 445. Add Two Numbers II
Сложность: medium

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

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

Пример:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

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

1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.

2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.

3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.

😎 Решение:

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

    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        var r1 = reverseList(l1)
        var r2 = reverseList(l2)

        var totalSum = 0
        var carry = 0
        var ans = ListNode(0)
        while (r1 != null || r2 != null) {
            if (r1 != null) {
                totalSum += r1.`val`
                r1 = r1.next
            }
            if (r2 != null) {
                totalSum += r2.`val`
                r2 = r2.next
            }

            ans.`val` = totalSum % 10
            carry = totalSum / 10
            val head = ListNode(carry)
            head.next = ans
            ans = head
            totalSum = carry
        }

        return if (carry == 0) ans.next else ans
    }
}

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

Задача: 134. Gas Station
Сложность: medium

Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].

У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.

Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.

Пример:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

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

1⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0.

2⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i].
Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2.

3⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer.

😎 Решение:

class Solution {
    fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
        var totalGain = 0
        var currGain = 0
        var answer = 0

        for (i in gas.indices) {
            val gain = gas[i] - cost[i]
            totalGain += gain
            currGain += gain
            if (currGain < 0) {
                currGain = 0
                answer = i + 1
            }
        }

        return if (totalGain >= 0) answer else -1
    }
}

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

Задача: 60. Permutation Sequence
Сложность: hard

Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.

Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.

Пример:

Input: n = 3, k = 3
Output: "213"

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

1⃣Сгенерируйте входной массив nums чисел от 1 до N.

2⃣Вычислите все факториальные основы от 0 до (N−1)!.

3⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1).

Используйте коэффициенты факториалов для построения перестановки.

Верните строку перестановки.

😎 Решение:

class Solution {
    fun getPermutation(n: Int, k: Int): String {
        val factorials = mutableListOf(1)
        val nums = mutableListOf("1")
        for (i in 1 until n) {
            factorials.add(factorials[i - 1] * i)
            nums.add((i + 1).toString())
        }
        var k = k - 1
        val output = mutableListOf<String>()
        for (i in n - 1 downTo 0) {
            val idx = k / factorials[i]
            k -= idx * factorials[i]
            output.add(nums[idx])
            nums.removeAt(idx)
        }
        return output.joinToString("")
    }
}

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

Задача: 632. Smallest Range Covering Elements from K Lists
Сложность: hard

У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c.

Пример:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

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

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

2⃣Нахождение минимального диапазона
Используйте кучу для извлечения минимального элемента и обновления текущего диапазона. Обновляйте максимальный элемент в текущем диапазоне при добавлении новых элементов.

3⃣Проверка и обновление диапазона
Продолжайте обновлять кучу и диапазон, пока возможно. Завершите, когда один из списков исчерпан.

😎 Решение:

import java.util.PriorityQueue

data class Element(val value: Int, val row: Int, val col: Int)

class Solution {
    fun smallestRange(nums: List<List<Int>>): IntArray {
        val minHeap = PriorityQueue<Element> { a, b -> a.value - b.value }
        var maxValue = Int.MIN_VALUE

        for (i in nums.indices) {
            minHeap.add(Element(nums[i][0], i, 0))
            maxValue = maxOf(maxValue, nums[i][0])
        }

        var rangeStart = 0
        var rangeEnd = Int.MAX_VALUE

        while (minHeap.size == nums.size) {
            val minElement = minHeap.poll()
            if (maxValue - minElement.value < rangeEnd - rangeStart) {
                rangeStart = minElement.value
                rangeEnd = maxValue
            }

            if (minElement.col + 1 < nums[minElement.row].size) {
                val value = nums[minElement.row][minElement.col + 1]
                minHeap.add(Element(value, minElement.row, minElement.col + 1))
                maxValue = maxOf(maxValue, value)
            }
        }

        return intArrayOf(rangeStart, rangeEnd)
    }
}

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

Задача: 920. Number of Music Playlists
Сложность: hard

В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

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

2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.
Заполнить массив dp, используя два случая:
Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)
Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)

3⃣Ответ находится в dp[goal][n].

😎 Решение:

class Solution {
    fun numMusicPlaylists(n: Int, goal: Int, k: Int): Int {
        val MOD = 1_000_000_007
        val dp = Array(goal + 1) { LongArray(n + 1) }
        dp[0][0] = 1

        for (i in 1..goal) {
            for (j in 1..n) {
                dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD
                if (j > k) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD
                }
            }
        }

        return dp[goal][n].toInt()
    }
}

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

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

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