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

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

Задача: 594. Longest Harmonious Subsequence
Сложность: Easy

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

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

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

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

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

3⃣Верните максимальную длину гармоничной подпоследовательности.

😎 Решение:

class Solution {
    fun findLHS(nums: IntArray): Int {
        val count = mutableMapOf<Int, Int>()
        var res = 0
        
        for (num in nums) {
            count[num] = count.getOrDefault(num, 0) + 1
            if (count.containsKey(num + 1)) {
                res = Math.max(res, count[num]!! + count[num + 1]!!)
            }
            if (count.containsKey(num - 1)) {
                res = Math.max(res, count[num]!! + count[num - 1]!!)
            }
        }
        
        return res
    }
}

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

Задача: 931. Minimum Falling Path Sum
Сложность: medium

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

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

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

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

3⃣Вернуть минимальное значение в последней строке dp массива.

😎 Решение:

class Solution {
    fun minFallingPathSum(matrix: Array<IntArray>): Int {
        val n = matrix.size
        var dp = matrix[0].clone()
        
        for (i in 1 until n) {
            val newDp = IntArray(n)
            for (j in 0 until n) {
                newDp[j] = matrix[i][j] + minOf(dp[j], if (j > 0) dp[j - 1] else Int.MAX_VALUE, if (j < n - 1) dp[j + 1] else Int.MAX_VALUE)
            }
            dp = newDp
        }
        
        return dp.minOrNull()!!
    }
}

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

Задача: 348. Design Tic-Tac-Toe
Сложность: medium

Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:

Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:

TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.

Пример:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

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

1⃣Инициализация:
Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно.
Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно.
Инициализируйте размер доски n.

2⃣Выполнение хода:
Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода.
Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal.

3⃣Проверка победы:
Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя.
Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода.

😎 Решение:

class TicTacToe(n: Int) {
    private val rows = IntArray(n)
    private val cols = IntArray(n)
    private var diagonal = 0
    private var antiDiagonal = 0
    private val n = n

    fun move(row: Int, col: Int, player: Int): Int {
        val add = if (player == 1) 1 else -1
        rows[row] += add
        cols[col] += add
        if (row == col) {
            diagonal += add
        }
        if (row + col == n - 1) {
            antiDiagonal += add
        }
        return if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || Math.abs(diagonal) == n || Math.abs(antiDiagonal) == n) player else 0
    }
}

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

Задача: 1165. Single-Row Keyboard
Сложность: easy

Есть специальная клавиатура, на которой все клавиши расположены в один ряд.

Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.

Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.

Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

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

1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0.

2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c.

3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова.

😎 Решение:

class Solution {
    fun calculateTime(keyboard: String, word: String): Int {
        val keyIndices = IntArray(26) { -1 }
        for (i in keyboard.indices) {
            keyIndices[keyboard[i] - 'a'] = i
        }
        
        var prev = 0
        var result = 0
        
        for (c in word) {
            val index = keyIndices[c - 'a']
            result += kotlin.math.abs(prev - index)
            prev = index
        }
        
        return result
    }
}

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

Задача: 520. Detect Capital
Сложность: easy

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

class Solution {
    fun detectCapitalUse(word: String): Boolean {
        val pattern = Regex("[A-Z]*|.[a-z]*")
        return pattern.matches(word)
    }
}

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

Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard

Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.

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

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

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

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

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

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

class Solution {
    fun minmaxGasDist(stations: IntArray, K: Int): Double {
        val N = stations.size
        val deltas = DoubleArray(N-1)
        for (i in 0 until N-1) {
            deltas[i] = (stations[i+1] - stations[i]).toDouble()
        }

        val dp = Array(N-1) { DoubleArray(K+1) }
        for (i in 0..K) {
            dp[0][i] = deltas[0] / (i+1)
        }

        for (p in 1 until N-1) {
            for (k in 0..K) {
                var bns = Double.MAX_VALUE
                for (x in 0..k) {
                    bns = minOf(bns, maxOf(deltas[p] / (x+1), dp[p-1][k-x]))
                }
                dp[p][k] = bns
            }
        }

        return dp[N-2][K]
    }
}

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