Kotlin | LeetCode

Задача: 1102. Path With Maximum Minimum Value
Сложность: medium

Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях.

Значение пути определяется минимальным числом на этом пути.

Пример:

Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow. 

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

1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы.

2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore:
Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore.
Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди.
Если успешно достигли правой нижней ячейки, значит путь существует.
Если очередь опустела до достижения правой нижней ячейки, пути не существует.

3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2.
В противном случае, верните curScore как ответ.

😎 Решение:

class Solution {
    private val dirs = arrayOf(
        intArrayOf(1, 0), intArrayOf(0, 1), intArrayOf(-1, 0), intArrayOf(0, -1)
    )

    fun maximumMinimumPath(grid: Array<IntArray>): Int {
        var curScore = minOf(grid[0][0], grid[grid.size - 1][grid[0].size - 1])

        while (curScore >= 0) {
            if (pathExists(grid, curScore)) {
                return curScore
            }
            curScore -= 1
        }
        return -1
    }

    private fun pathExists(grid: Array<IntArray>, curScore: Int): Boolean {
        val R = grid.size
        val C = grid[0].size
        val visited = Array(R) { BooleanArray(C) }
        val dq = ArrayDeque<Pair<Int, Int>>()
        dq.add(0 to 0)
        visited[0][0] = true

        fun push(row: Int, col: Int) {
            if (row in 0 until R && col in 0 until C && !visited[row][col] && grid[row][col] >= curScore) {
                dq.add(row to col)
                visited[row][col] = true
            }
        }

        while (dq.isNotEmpty()) {
            val (curRow, curCol) = dq.removeFirst()
            if (curRow == R - 1 && curCol == C - 1) {
                return true
            }

            for (dir in dirs) {
                push(curRow + dir[0], curCol + dir[1])
            }
        }
        return false
    }
}

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

Задача: 257. Binary Tree Paths
Сложность: easy

Дано корневое дерево, верните все пути от корня до листа в любом порядке.

Лист — это узел без детей.

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2⃣Начните с корневого узла, пустого пути и пустого списка путей.

3⃣Верните список всех путей от корня до листа.

😎 Решение:

class Solution {
    fun construct_paths(root: TreeNode?, path: String, paths: MutableList<String>) {
        if (root != null) {
            var path = path + root.`val`
            if (root.left == null && root.right == null) {
                paths.add(path)
            } else {
                path += "->"
                construct_paths(root.left, path, paths)
                construct_paths(root.right, path, paths)
            }
        }
    }

    fun binaryTreePaths(root: TreeNode?): List<String> {
        val paths = mutableListOf<String>()
        construct_paths(root, "", paths)
        return paths
    }
}

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

🔥 Скрытые вакансии с удаленной работой для Android разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.

🔹 Android Jobs | Вакансии
🔹 Flutter Dart Jobs | Вакансии
🔹 iOS Jobs | Вакансии

🔸 Все каналы с вакансиями

Задача: 491. Non-decreasing Subsequences
Сложность: medium

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

Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

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

2⃣Функция обратного отслеживания
Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента.

3⃣Возврат результата
После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его.

😎 Решение:

class Solution {
    fun findSubsequences(nums: IntArray): List<List<Int>> {
        val result = mutableSetOf<List<Int>>()
        val sequence = mutableListOf<Int>()
        backtrack(nums, 0, sequence, result)
        return result.toList()
    }

    private fun backtrack(nums: IntArray, index: Int, sequence: MutableList<Int>, result: MutableSet<List<Int>>) {
        if (index == nums.size) {
            if (sequence.size >= 2) {
                result.add(sequence.toList())
            }
            return
        }
        if (sequence.isEmpty() || sequence.last() <= nums[index]) {
            sequence.add(nums[index])
            backtrack(nums, index + 1, sequence, result)
            sequence.removeAt(sequence.size - 1)
        }
        backtrack(nums, index + 1, sequence, result)
    }
}

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

Задача: 635. Design Log Storage System
Сложность: medium

Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.

Пример:

Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]

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

1⃣Инициализация и хранение журналов
Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.

2⃣Формирование диапазона
Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.

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

😎 Решение:

class LogSystem {
    private val logs = mutableListOf<Pair<Int, String>>()
    private val granularity = mapOf(
        "Year" to 4,
        "Month" to 7,
        "Day" to 10,
        "Hour" to 13,
        "Minute" to 16,
        "Second" to 19
    )

    fun put(id: Int, timestamp: String) {
        logs.add(id to timestamp)
    }

    fun retrieve(start: String, end: String, granularity: String): List<Int> {
        val length = this.granularity[granularity]!!
        val start = start.substring(0, length)
        val end = end.substring(0, length)
        return logs.filter { (id, timestamp) ->
            val ts = timestamp.substring(0, length)
            start <= ts && ts <= end
        }.map { it.first }
    }
}

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

Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium

Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.

Пример:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

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

1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.

2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.

3⃣Вернуть первые j символов строки.

😎 Решение:

class Solution {
    fun removeDuplicates(s: String, k: Int): String {
        val counts = mutableListOf<Int>()
        val sa = s.toCharArray()
        var j = 0
        
        for (i in sa.indices) {
            sa[j] = sa[i]
            if (j == 0 || sa[j] != sa[j - 1]) {
                counts.add(1)
            } else {
                val incremented = counts.removeAt(counts.size - 1) + 1
                if (incremented == k) {
                    j -= k
                } else {
                    counts.add(incremented)
                }
            }
            j++
        }
        return String(sa, 0, j)
    }
}

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

Задача: 535. Encode and Decode TinyURL
Сложность: medium

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

Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.

Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

1⃣ Инициализация:
Создайте строку, содержащую все возможные символы (цифры и буквы), которые могут быть использованы для генерации кода.
Создайте хэш-таблицу для хранения соответствий коротких и длинных URL-адресов.
Создайте объект для генерации случайных чисел.

2⃣ Кодирование:
Сгенерируйте случайный 6-символьный код.
Если такой код уже существует в хэш-таблице, повторите генерацию.
Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице.
Верните полный короткий URL.

3⃣ Декодирование:
Удалите префикс короткого URL, чтобы получить код.
Используйте код для поиска длинного URL в хэш-таблице.
Верните длинный URL.

😎 Решение:

class Codec {
    private val alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    private val map = mutableMapOf<String, String>()
    private val rand = java.util.Random()
    
    private fun getRand(): String {
        val sb = StringBuilder()
        repeat(6) {
            sb.append(alphabet[rand.nextInt(62)])
        }
        return sb.toString()
    }

    fun encode(longUrl: String): String {
        var key = getRand()
        while (map.containsKey(key)) {
            key = getRand()
        }
        map[key] = longUrl
        return "http://tinyurl.com/$key"
    }

    fun decode(shortUrl: String): String? {
        val key = shortUrl.replace("http://tinyurl.com/", "")
        return map[key]
    }
}

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

Задача: 981. Time Based Key-Value Store
Сложность: medium

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

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

TimeMap() Инициализирует объект структуры данных.
void set(String key, String value, int timestamp) Сохраняет ключ key с значением value в заданное время timestamp.
String get(String key, int timestamp) Возвращает значение, такое что set был вызван ранее с timestamp_prev <= timestamp. Если таких значений несколько, возвращается значение, связанное с наибольшим timestamp_prev. Если значений нет, возвращается "".

Пример:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

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

1⃣Создайте hashmap keyTimeMap, который хранит строку в качестве ключа и другой hashmap в качестве значения, как обсуждалось выше.

2⃣В функции set() сохраните значение в позиции timestamp в корзине ключа keyTimeMap, т.е. keyTimeMap[key][timestamp] = value.

3⃣В функции get() итерируйтесь по всем временам в порядке убывания от timestamp до 1. Для любого времени во время итерации, если существует значение в корзине ключа, верните это значение. В противном случае, в конце верните пустую строку.

😎 Решение:

class TimeMap {
    private val keyTimeMap = mutableMapOf<String, MutableMap<Int, String>>()

    fun set(key: String, value: String, timestamp: Int) {
        if (!keyTimeMap.containsKey(key)) {
            keyTimeMap[key] = mutableMapOf()
        }
        keyTimeMap[key]?.put(timestamp, value)
    }

    fun get(key: String, timestamp: Int): String {
        val times = keyTimeMap[key] ?: return ""
        for (currTime in timestamp downTo 1) {
            if (times.containsKey(currTime)) {
                return times[currTime]!!
            }
        }
        return ""
    }
}

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

Задача: 970. Powerful Integers
Сложность: medium

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

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

Пример:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

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

1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎 Решение:

class Solution {
    fun powerfulIntegers(x: Int, y: Int, bound: Int): List<Int> {
        val a = if (x == 1) bound else (Math.log(bound.toDouble()) / Math.log(x.toDouble())).toInt()
        val b = if (y == 1) bound else (Math.log(bound.toDouble()) / Math.log(y.toDouble())).toInt()
        val powerfulIntegers = mutableSetOf<Int>()

        for (i in 0..a) {
            for (j in 0..b) {
                val value = Math.pow(x.toDouble(), i.toDouble()).toInt() + Math.pow(y.toDouble(), j.toDouble()).toInt()
                if (value <= bound) {
                    powerfulIntegers.add(value)
                }
                if (y == 1) break
            }
            if (x == 1) break
        }

        return powerfulIntegers.toList()
    }
}

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

Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

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

2⃣Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

class Solution {
    fun countBits(num: Int): IntArray {
        val ans = IntArray(num + 1)
        for (x in 1..num) {
            ans[x] = ans[x and (x - 1)] + 1
        }
        return ans
    }
}

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

Задача: 790. Domino and Tromino Tiling
Сложность: medium

У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.

Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

При укладке каждая клетка должна быть покрыта плиткой. Две укладки считаются разными, если и только если есть две 4-направленно смежные клетки на доске, такие, что в одной укладке обе клетки заняты плиткой, а в другой - нет.

Пример:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

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

1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n).

2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас.

3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся.

😎 Решение:

class Solution {
    private val MOD = 1_000_000_007
    private val fCache = mutableMapOf<Int, Int>()
    private val pCache = mutableMapOf<Int, Int>()

    private fun p(n: Int): Int {
        if (pCache.containsKey(n)) {
            return pCache[n]!!
        }
        if (n == 2) {
            return 1
        }
        val result = (p(n - 1) + f(n - 2)) % MOD
        pCache[n] = result
        return result
    }

    private fun f(n: Int): Int {
        if (fCache.containsKey(n)) {
            return fCache[n]!!
        }
        if (n <= 2) {
            return n
        }
        val result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD
        fCache[n] = result
        return result
    }

    fun numTilings(n: Int): Int {
        return f(n)
    }
}

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

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

Дан массив nums размера n, верните элемент большинства.

Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.

Пример:

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

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

1⃣Использование HashMap для подсчета:
Создайте HashMap для отслеживания количества каждого элемента в массиве.

2⃣Подсчет вхождений элементов:
Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.

3⃣Поиск элемента большинства:
Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋

😎 Решение:

fun majorityElement(nums: IntArray): Int {
    val counts = mutableMapOf<Int, Int>()
    nums.forEach { num ->
        counts[num] = counts.getOrDefault(num, 0) + 1
    }
    
    counts.forEach { (num, count) ->
        if (count > nums.size / 2) return num
    }
    return 0
}

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

Задача: 334. Increasing Triplet Subsequence
Сложность: Medium

Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.

Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

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

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

2⃣Итерация по массиву:
Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки:
- если текущий элемент меньше или равен first_num, обновите first_num текущим элементом.
- иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом.
- иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true.

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

😎 Решение:

class Solution {
    fun increasingTriplet(nums: IntArray): Boolean {
        var firstNum = Int.MAX_VALUE
        var secondNum = Int.MAX_VALUE
        
        for (n in nums) {
            if (n <= firstNum) {
                firstNum = n
            } else if (n <= secondNum) {
                secondNum = n
            } else {
                return true
            }
        }
        return false
    }
}

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

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

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

Задача: 606. Construct String from Binary Tree
Сложность: Medium

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

Представление узлов: Каждый узел в дереве должен быть представлен его целочисленным значением.

Скобки для дочерних узлов: Если у узла есть хотя бы один дочерний узел (левый или правый), его дочерние узлы должны быть представлены в скобках. Конкретно:

- Если у узла есть левый дочерний узел, значение левого дочернего узла должно быть заключено в скобки сразу после значения узла.
- Если у узла есть правый дочерний узел, значение правого дочернего узла также должно быть заключено в скобки. Скобки для правого дочернего узла должны следовать за скобками для левого дочернего узла.

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

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

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

3⃣Объединение результатов
Собираем результаты для каждого узла, учитывая все упомянутые случаи, чтобы получить строковое представление дерева.

😎 Решение:

class Solution {
    fun tree2str(t: TreeNode?): String {
        val res = StringBuilder()
        dfs(t, res)
        return res.toString()
    }

    private fun dfs(t: TreeNode?, res: StringBuilder) {
        if (t == null) return
        res.append(t.`val`)
        if (t.left == null && t.right == null) return
        res.append('(')
        dfs(t.left, res)
        res.append(')')
        if (t.right != null) {
            res.append('(')
            dfs(t.right, res)
            res.append(')')
        }
    }
}

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

Задача: 275. H-Index II
Сложность: medium

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.

Пример:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1⃣Найти середину массива:
Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n].

2⃣Сравнить количество статей с цитированиями больше или равными citations[mid]:
Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.
Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].
Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3⃣Возвращение результата:
Продолжать процесс, пока не будет найден h-индекс.
Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎 Решение:

class Solution {
    fun hIndex(citations: IntArray): Int {
        val n = citations.size
        var left = 0
        var right = n - 1
        
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (citations[mid] == n - mid) {
                return n - mid
            } else if (citations[mid] < n - mid) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return n - left
    }
}

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

Задача: 1275. Find Winner on a Tic Tac Toe Game
Сложность: easy

В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные.
Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым.

Пример:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

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

1⃣Инициализируйте пустую 3x3 сетку.

2⃣Пройдите по списку ходов и обновите сетку в соответствии с ходами игроков A и B.

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

😎 Решение:

class Solution {
    fun tictactoe(moves: Array<IntArray>): String {
        val grid = Array(3) { CharArray(3) }
        for (i in moves.indices) {
            val (r, c) = moves[i]
            grid[r][c] = if (i % 2 == 0) 'X' else 'O'
        }

        for (i in 0..2) {
            if (grid[i][0] == grid[i][1] && grid[i][1] == grid[i][2] && grid[i][0] != '\u0000')
                return if (grid[i][0] == 'X') "A" else "B"
            if (grid[0][i] == grid[1][i] && grid[1][i] == grid[2][i] && grid[0][i] != '\u0000')
                return if (grid[0][i] == 'X') "A" else "B"
        }

        if (grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2] && grid[0][0] != '\u0000')
            return if (grid[0][0] == 'X') "A" else "B"
        if (grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0] && grid[0][2] != '\u0000')
            return if (grid[0][2] == 'X') "A" else "B"

        return if (moves.size == 9) "Draw" else "Pending"
    }
}

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

Задача: 723. Candy Crush
Сложность: medium

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

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

2⃣Удалите отмеченные конфеты, установив их значение в 0.

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

😎 Решение:

class Solution {
    fun candyCrush(board: Array<IntArray>): Array<IntArray> {
        val m = board.size
        val n = board[0].size
        var stable = false

        while (!stable) {
            stable = true
            val crush = Array(m) { BooleanArray(n) }

            for (i in 0 until m) {
                for (j in 0 until n - 2) {
                    val v = Math.abs(board[i][j])
                    if (v != 0 && v == Math.abs(board[i][j + 1]) && v == Math.abs(board[i][j + 2])) {
                        stable = false
                        crush[i][j] = true
                        crush[i][j + 1] = true
                        crush[i][j + 2] = true
                    }
                }
            }

            for (i in 0 until m - 2) {
                for (j in 0 until n) {
                    val v = Math.abs(board[i][j])
                    if (v != 0 && v == Math.abs(board[i + 1][j]) && v == Math.abs(board[i + 2][j])) {
                        stable = false
                        crush[i][j] = true
                        crush[i + 1][j] = true
                        crush[i + 2][j] = true
                    }
                }
            }

            for (i in 0 until m) {
                for (j in 0 until n) {
                    if (crush[i][j]) {
                        board[i][j] = 0
                    }
                }
            }

            for (j in 0 until n) {
                var idx = m - 1
                for (i in m - 1 downTo 0) {
                    if (board[i][j] != 0) {
                        board[idx][j] = board[i][j]
                        idx--
                    }
                }
                for (i in idx downTo 0) {
                    board[i][j] = 0
                }
            }
        }

        return board
    }
}

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

Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter(words: Array<String>) {
    private val prefixSuffixMap = mutableMapOf<String, Int>()
    
    init {
        for ((index, word) in words.withIndex()) {
            val length = word.length
            for (prefixLength in 1..length) {
                for (suffixLength in 1..length) {
                    val prefix = word.substring(0, prefixLength)
                    val suffix = word.substring(length - suffixLength)
                    val key = "$prefix#$suffix"
                    prefixSuffixMap[key] = index
                }
            }
        }
    }
    
    fun f(pref: String, suff: String): Int {
        val key = "$pref#$suff"
        return prefixSuffixMap[key] ?: -1
    }
}

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

Задача: 25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

1⃣ Проверяем, хватает ли элементов в текущей группе (не менее k узлов).

2⃣ Если хватает, переворачиваем узлы в группе, используя указатели.

3⃣ Рекурсивно вызываем reverseKGroup для следующей группы и соединяем с уже перевернутыми узлами.

😎 Решение:

class Solution {
    fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        var count = 0
        var cur = head
        while (count < k && cur != null) {
            cur = cur.next
            count++
        }
        if (count < k) return head

        var prev: ListNode? = null
        cur = head
        repeat(k) {
            val next = cur?.next
            cur?.next = prev
            prev = cur
            cur = next
        }

        head?.next = reverseKGroup(cur, k)
        return prev
    }
}

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