Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

class NumArray(nums: IntArray) {
    private val sum: IntArray = IntArray(nums.size + 1)

    init {
        for (i in nums.indices) {
            sum[i + 1] = sum[i] + nums[i]
        }
    }

    fun sumRange(i: Int, j: Int): Int {
        return sum[j + 1] - sum[i]
    }
}

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

Задача: 869. Reordered Power of 2
Сложность: medium

Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем.

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

Пример:

Input: n = 1
Output: true

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

1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.

2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.

3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false.

😎 Решение:

class Solution {
    fun reorderedPowerOf2(N: Int): Boolean {
        val A = N.toString().map { it - '0' }.toIntArray()
        return permutations(A, 0)
    }

    private fun isPowerOfTwo(A: IntArray): Boolean {
        if (A[0] == 0) return false
        var N = A.joinToString("").toInt()
        while (N > 0 && (N and 1) == 0) N = N shr 1
        return N == 1
    }

    private fun permutations(A: IntArray, start: Int): Boolean {
        if (start == A.size) return isPowerOfTwo(A)
        for (i in start until A.size) {
            A.swap(start, i)
            if (permutations(A, start + 1)) return true
            A.swap(start, i)
        }
        return false
    }

    private fun IntArray.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

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

Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

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

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

1⃣Отсортируйте массив nums.

2⃣Определите минимальное и максимальное возможные расстояния.

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

😎 Решение:

fun countPairs(nums: IntArray, mid: Int): Int {
    var count = 0
    var j = 0
    for (i in nums.indices) {
        while (j < nums.size && nums[j] - nums[i] <= mid) {
            j++
        }
        count += j - i - 1
    }
    return count
}

fun smallestDistancePair(nums: IntArray, k: Int): Int {
    nums.sort()
    var left = 0
    var right = nums.last() - nums.first()
    while (left < right) {
        val mid = (left + right) / 2
        if (countPairs(nums, mid) < k) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

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

Задача: 1531. String Compression II
Сложность: hard

Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

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

1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

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

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение:

class Solution {
    private val memo = mutableMapOf<Int, Int>()
    private val add = setOf(1, 9, 99)

    fun getLengthOfOptimalCompression(s: String, k: Int): Int {
        return dp(s, 0, ('a' + 26), 0, k)
    }

    private fun dp(s: String, idx: Int, lastChar: Char, lastCharCount: Int, k: Int): Int {
        if (k < 0) return Int.MAX_VALUE / 2

        if (idx == s.length) return 0

        val key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k

        if (memo.containsKey(key)) return memo[key]!!

        val deleteChar = dp(s, idx + 1, lastChar, lastCharCount, k - 1)
        val keepChar = if (s[idx] == lastChar) {
            dp(s, idx + 1, lastChar, lastCharCount + 1, k) + if (add.contains(lastCharCount)) 1 else 0
        } else {
            dp(s, idx + 1, s[idx], 1, k) + 1
        }

        val res = minOf(keepChar, deleteChar)
        memo[key] = res

        return res
    }
}

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

Задача: 937. Reorder Data in Log Files
Сложность: medium

Вам дается массив журналов. Каждый журнал представляет собой строку слов, ограниченную пробелами, где первое слово является идентификатором. Существует два типа журналов: Буквенные журналы: Все слова (кроме идентификатора) состоят из строчных английских букв. Цифровые журналы: Все слова (кроме идентификатора) состоят из цифр. Упорядочите эти журналы таким образом: буквенные журналы идут перед всеми цифровыми журналами. Буквенные журналы сортируются лексикографически по их содержанию. Если их содержимое одинаково, то отсортируйте их лексикографически по их идентификаторам. Цифровые журналы сохраняют свой относительный порядок. Верните окончательный порядок журналов.

Пример:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

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

1⃣Разделить журналы на буквенные и цифровые.

2⃣Отсортировать буквенные журналы:
Лексикографически по содержимому.
Если содержимое одинаково, отсортировать по идентификатору.
Объединить отсортированные буквенные журналы и цифровые журналы в исходном порядке.

3⃣Вернуть окончательный результат.

😎 Решение:

class Solution {
    fun reorderLogFiles(logs: Array<String>): Array<String> {
        return logs.sortedWith { log1, log2 ->
            val split1 = log1.split(" ", limit = 2)
            val split2 = log2.split(" ", limit = 2)
            val isDigit1 = split1[1][0].isDigit()
            val isDigit2 = split2[1][0].isDigit()
            
            if (!isDigit1 && !isDigit2) {
                val cmp = split1[1].compareTo(split2[1])
                if (cmp != 0) cmp else split1[0].compareTo(split2[0])
            } else if (isDigit1 && isDigit2) {
                0
            } else if (isDigit1) {
                1
            } else {
                -1
            }
        }.toTypedArray()
    }
}

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

Задача: 904. Fruit Into Baskets
Сложность: medium

Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.

Пример:

Input: fruits = [1,2,1]
Output: 3

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

1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов.

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

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

😎 Решение:

class Solution {
    fun totalFruit(fruits: IntArray): Int {
        val basket = mutableMapOf<Int, Int>()
        var left = 0
        var maxFruits = 0

        for (right in fruits.indices) {
            basket[fruits[right]] = basket.getOrDefault(fruits[right], 0) + 1
            while (basket.size > 2) {
                basket[fruits[left]] = basket[fruits[left]]!! - 1
                if (basket[fruits[left]] == 0) {
                    basket.remove(fruits[left])
                }
                left++
            }
            maxFruits = maxOf(maxFruits, right - left + 1)
        }

        return maxFruits
    }
}

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

Задача: 477. Total Hamming Distance
Сложность: Medium

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.

Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

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

😎 Решение:

class Solution {
    fun totalHammingDistance(nums: IntArray): Int {
        var ans = 0
        
        if (nums.isEmpty()) {
            return ans
        }
        
        for (i in 0 until nums.size - 1) {
            for (j in i + 1 until nums.size) {
                ans += Integer.bitCount(nums[i] xor nums[j])
            }
        }
        
        return ans
    }
}

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

Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium

Дан массив nums, отсортированный в неубывающем порядке. Найдите начальную и конечную позицию заданного target.
Если target не найден, верните [-1, -1]. Алгоритм должен работать за O(log n).

Пример:

Input: nums = [5,7,7,8,8,10], target = 8  
Output: [3,4]  

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

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

2⃣Если target не найден, возвращаем [-1, -1].

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

😎 Решение:

class Solution {
    fun searchRange(nums: IntArray, target: Int): IntArray {
        val firstOccurrence = findBound(nums, target, true)
        if (firstOccurrence == -1) {
            return intArrayOf(-1, -1)
        }
        val lastOccurrence = findBound(nums, target, false)
        return intArrayOf(firstOccurrence, lastOccurrence)
    }

    private fun findBound(nums: IntArray, target: Int, isFirst: Boolean): Int {
        var left = 0
        var right = nums.size - 1

        while (left <= right) {
            val mid = (left + right) / 2
            if (nums[mid] == target) {
                if (isFirst) {
                    if (mid == left || nums[mid - 1] != target) return mid
                    right = mid - 1
                } else {
                    if (mid == right || nums[mid + 1] != target) return mid
                    left = mid + 1
                }
            } else if (nums[mid] > target) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return -1
    }
}

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

Задача: 819. Most Common Word
Сложность: easy

Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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

1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

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

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

class Solution {
    fun mostCommonWord(paragraph: String, banned: List<String>): String {
        val normalizedStr = paragraph.map { if (it.isLetterOrDigit()) it.lowercaseChar() else ' ' }.joinToString("")
        val words = normalizedStr.split("\\s+".toRegex()).filter { it.isNotEmpty() }
        val wordCount = mutableMapOf<String, Int>()
        val bannedWords = banned.toSet()

        for (word in words) {
            if (word !in bannedWords) {
                wordCount[word] = wordCount.getOrDefault(word, 0) + 1
            }
        }

        return wordCount.maxByOrNull { it.value }!!.key
    }

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

Задача: 713. Subarray Product Less Than K
Сложность: medium

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

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

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

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

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

😎 Решение:

fun numSubarrayProductLessThanK(nums: IntArray, k: Int): Int {
    if (k <= 1) return 0
    var product = 1
    var count = 0
    var left = 0
    for (right in nums.indices) {
        product *= nums[right]
        while (product >= k) {
            product /= nums[left]
            left++
        }
        count += right - left + 1
    }
    return count
}

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

Задача: 82. Remove Duplicates from Sorted List II
Сложность: medium

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

Пример:

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

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

1⃣Инициализация "стража" и предшественника:
Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены.
Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж.

2⃣Проход по списку с проверкой на дубликаты:
Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.
Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов.

3⃣Переход к следующему узлу и возврат результата:
Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел.
Двигаем указатель head на следующий узел в списке.
После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов.

😎 Решение:

class Solution {
    fun deleteDuplicates(head: ListNode?): ListNode? {
        val sentinel = ListNode(0)
        sentinel.next = head
        var pred = sentinel
        var current = head

        while (current != null) {
            if (current.next != null && current.`val` == current.next!!.`val`) {
                while (current.next != null && current.`val` == current.next!!.`val`) {
                    current = current.next
                }
                pred.next = current.next
            } else {
                pred = pred.next!!
            }
            current = current.next
        }

        return sentinel.next
    }

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

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

Задача: 162. Find Peak Element
Сложность: medium

Пиковый элемент — это такой элемент массива, который строго больше своих соседей.
Нужно найти любой пик и вернуть его индекс.
Допустим, что nums[-1] = nums[n] = -∞.
Решение должно работать за O(log n).

Пример:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

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

1⃣Инициализируем low = 0 и high = nums.lastIndex. На каждом шаге находим mid = (low + high) / 2.

2⃣Если nums[mid] > nums[mid + 1], это значит, что слева есть пик — сдвигаем high = mid.

3⃣Иначе пик находится справа — сдвигаем low = mid + 1. Завершаем, когда low == high — это и есть индекс пика.

😎 Решение:

class Solution {
    fun findPeakElement(nums: IntArray): Int {
        return search(nums, 0, nums.size - 1)
    }

    private fun search(nums: IntArray, l: Int, r: Int): Int {
        if (l == r) return l
        val mid = (l + r) / 2
        return if (nums[mid] > nums[mid + 1]) search(nums, l, mid)
        else search(nums, mid + 1, r)
    }
}

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

Задача: 393. UTF-8 Validation
Сложность: medium

Символ вДан целочисленный массив данных, представляющий возвращаемые данные, является ли это допустимой кодировкой UTF-8 (т.е. переводится в последовательность допустимых закодированных символов UTF-8).
Символ в UTF-8 может иметь длину от 1 до 4 байтов, с соблюдением таких правил:

1 байт: начинается с 0, далее 7 бит кода

n байтов: n битовединиц, за ними 0, затем (n - 1) байтов с префиксом10

Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

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

1⃣Преобразовать каждый элемент массива в 8-битную бинарную форму ( padStart(8, '0')).

2⃣Если nBytes == 0, определите количество ведущих единиц — это размер текущего символа UTF-8. Если 1 или больше 4 — ошибка.

3⃣Если nBytes > 0вы уверены, что настоящий байт начинается с 10. Уменьшить nBytes. В конце nBytesдолжно быть 0.

😎 Решение:

fun main() {
    val solution = Solution()
    println(solution.validUtf8(intArrayOf(197, 130, 1))) // true
    println(solution.validUtf8(intArrayOf(235, 140, 4))) // false
}

class Solution {
    fun validUtf8(data: IntArray): Boolean {
        var nBytes = 0

        for (num in data) {
            val binRep = num.toString(2).padStart(8, '0').takeLast(8)

            if (nBytes == 0) {
                for (bit in binRep) {
                    if (bit == '0') break
                    nBytes++
                }

                if (nBytes == 0) {
                    continue
                }

                if (nBytes == 1 || nBytes > 4) {
                    return false
                }
            } else {
                if (!(binRep[0] == '1' && binRep[1] == '0')) {
                    return false
                }
            }

            nBytes--
        }

        return nBytes == 0
    }
}

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

Задача: 923. 3Sum With Multiplicity
Сложность: medium

Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

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

2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.

3⃣Вернуть результат по модулю 10^9 + 7.

😎 Решение:

class Solution {
    fun threeSumMulti(arr: IntArray, target: Int): Int {
        arr.sort()
        val MOD = 1_000_000_007
        var count: Long = 0
        
        for (i in arr.indices) {
            var j = i + 1
            var k = arr.size - 1
            while (j < k) {
                val sum = arr[i] + arr[j] + arr[k]
                if (sum == target) {
                    if (arr[j] == arr[k]) {
                        count += (k - j + 1).toLong() * (k - j) / 2
                        break
                    } else {
                        var left = 1
                        var right = 1
                        while (j + 1 < k && arr[j] == arr[j + 1]) {
                            left++
                            j++
                        }
                        while (k - 1 > j && arr[k] == arr[k - 1]) {
                            right++
                            k--
                        }
                        count += left.toLong() * right
                        j++
                        k--
                    }
                } else if (sum < target) {
                    j++
                } else {
                    k--
                }
            }
        }
        
        return (count % MOD).toInt()
    }
}

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

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

Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target.

Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [9], target = 3
Output: 0

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

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

2⃣Из-за рекурсивной природы формулы мы можем напрямую перевести формулу в рекурсивную функцию.

3⃣Здесь, соответственно, мы определяем рекурсивную функцию под названием combs(remain), которая возвращает количество комбинаций, где каждая комбинация в сумме дает значение remain.

😎 Решение:

class Solution {
    private val memo = mutableMapOf<Int, Int>()

    fun combinationSum4(nums: IntArray, target: Int): Int {
        return combs(nums, target)
    }

    private fun combs(nums: IntArray, remain: Int): Int {
        if (remain == 0) return 1
        if (memo.containsKey(remain)) return memo[remain]!!

        var result = 0
        for (num in nums) {
            if (remain - num >= 0) {
                result += combs(nums, remain - num)
            }
        }
        memo[remain] = result
        return result
    }
}

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

Задача: 1510. Stone Game IV
Сложность: hard

Алиса и Боб поочередно играют в игру, причем Алиса начинает первой.

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

Кроме того, если игрок не может сделать ход, он/она проигрывает игру.

Дано положительное целое число n, верните true, если и только если Алиса выиграет игру, иначе верните false, предполагая, что оба игрока играют оптимально.

Пример:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

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

1⃣Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях.

2⃣Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs.

3⃣Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True.

😎 Решение:

class Solution {
    fun winnerSquareGame(n: Int): Boolean {
        val cache = mutableMapOf(0 to false)
        return dfs(cache, n)
    }

    private fun dfs(cache: MutableMap<Int, Boolean>, remain: Int): Boolean {
        if (cache.containsKey(remain)) {
            return cache[remain]!!
        }
        val sqrtRoot = kotlin.math.sqrt(remain.toDouble()).toInt()
        for (i in 1..sqrtRoot) {
            if (!dfs(cache, remain - i * i)) {
                cache[remain] = true
                return true
            }
        }
        cache[remain] = false
        return false
    }
}

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

Задача: 1018. Binary Prefix Divisible By 5
Сложность: easy

Вам дан двоичный массив nums (индексированный 0). Мы определяем xi как число, двоичным представлением которого является подмассив nums[0..i] (от старшего бита к младшему). Например, если nums = [1,0,1], то x0 = 1, x1 = 2 и x2 = 5. Верните массив булевых чисел answer, где answer[i] истинно, если xi делится на 5.

Пример:

Input: nums = [0,1,1]
Output: [true,false,false]

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

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

2⃣Итерация по массиву:
Пройдите по всем элементам массива nums. Для каждого элемента:
Обновите значение x, учитывая текущий бит.
Проверяйте, делится ли x на 5, и добавьте результат (true или false) в массив answer.
Чтобы избежать переполнения, используйте модуль 5 для переменной x.

3⃣Возврат результата:
Верните массив answer с результатами проверки делимости на 5.

😎 Решение:

class Solution {
    fun prefixesDivBy5(nums: IntArray): BooleanArray {
        var x = 0
        val answer = BooleanArray(nums.size)
        for (i in nums.indices) {
            x = (x * 2 + nums[i]) % 5
            answer[i] = x == 0
        }
        return answer
    }
}

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

Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    fun wordPatternMatch(pattern: String, s: String): Boolean {
        val symbolMap = mutableMapOf<Char, String>()
        val wordSet = mutableSetOf<String>()
        return isMatch(s, 0, pattern, 0, symbolMap, wordSet)
    }

    private fun isMatch(s: String, sIndex: Int, pattern: String, pIndex: Int,
                        symbolMap: MutableMap<Char, String>, wordSet: MutableSet<String>): Boolean {
        if (pIndex == pattern.length) {
            return sIndex == s.length
        }

        val symbol = pattern[pIndex]
        if (symbolMap.containsKey(symbol)) {
            val word = symbolMap[symbol]!!
            if (!s.startsWith(word, sIndex)) {
                return false
            }
            return isMatch(s, sIndex + word.length, pattern, pIndex + 1, symbolMap, wordSet)
        }

        for (k in sIndex + 1..s.length) {
            val newWord = s.substring(sIndex, k)
            if (wordSet.contains(newWord)) {
                continue
            }
            symbolMap[symbol] = newWord
            wordSet.add(newWord)
            if (isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true
            }
            symbolMap.remove(symbol)
            wordSet.remove(newWord)
        }
        return false
    }
}

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

Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

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

😎 Решение:

class Solution {
    companion object {
        const val WHITE = 1
        const val GRAY = 2
        const val BLACK = 3
    }

    private var isPossible: Boolean = true
    private lateinit var color: MutableMap<Int, Int>
    private val adjList: MutableMap<Int, MutableList<Int>> = HashMap()
    private val topologicalOrder: MutableList<Int> = ArrayList()

    private fun init(numCourses: Int) {
        isPossible = true
        color = HashMap()
        adjList.clear()
        topologicalOrder.clear()
        for (i in 0 until numCourses) {
            color[i] = WHITE
        }
    }

    private fun dfs(node: Int) {
        if (!isPossible) return
        color[node] = GRAY
        for (neighbor in adjList.getOrDefault(node, mutableListOf())) {
            when (color[neighbor]) {
                WHITE -> dfs(neighbor)
                GRAY -> isPossible = false
            }
        }
        color[node] = BLACK
        topologicalOrder.add(node)
    }

    fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
        init(numCourses)
        for (prerequisite in prerequisites) {
            val (dest, src) = prerequisite
            adjList.computeIfAbsent(src) { mutableListOf() }.add(dest)
        }
        for (i in 0 until numCourses) {
            if (color[i] == WHITE) {
                dfs(i)
            }
        }
        return if (isPossible) {
            val order = IntArray(numCourses)
            for (i in 0 until numCourses) {
                order[i] = topologicalOrder[numCourses - i - 1]
            }
            order
        } else {
            intArrayOf()
        }
    }
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

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

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

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

2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.

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

😎 Решение:

fun prevPermOpt1(arr: IntArray): IntArray {
    val n = arr.size
    var i = n - 2
    while (i >= 0 && arr[i] <= arr[i + 1]) {
        i--
    }
    if (i == -1) return arr
    
    var j = n - 1
    while (arr[j] >= arr[i] || (j < n - 1 && arr[j] == arr[j + 1])) {
        j--
    }
    
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
    
    return arr
}

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

Задача: 523. Continuous Subarray Sum
Сложность: medium

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

Хороший подмассив — это подмассив, который:

имеет длину не менее двух, и
сумма элементов подмассива является кратной k.
Учтите:

Подмассив — это непрерывная часть массива.
Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k.

Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

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

1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

2⃣Итеративно пройдите по всем элементам массива nums.

3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false.

😎 Решение:

class Solution {
    fun checkSubarraySum(nums: IntArray, k: Int): Boolean {
        var prefixMod = 0
        val modSeen = mutableMapOf(0 to -1)
        
        for (i in nums.indices) {
            prefixMod = (prefixMod + nums[i]) % k
            
            if (modSeen.containsKey(prefixMod)) {
                if (i - modSeen[prefixMod]!! > 1) {
                    return true
                }
            } else {
                modSeen[prefixMod] = i
            }
        }
        
        return false
    }
}

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