Задача: 526. Beautiful Arrangement
Сложность: medium

Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.

Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

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

2⃣ Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.

3⃣ Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.

😎 Решение:

class Solution {
    private var count = 0
    
    fun countArrangement(N: Int): Int {
        val nums = (1..N).toList().toIntArray()
        permute(nums, 0)
        return count
    }
    
    private fun permute(nums: IntArray, l: Int) {
        if (l == nums.size) {
            count++
        }
        for (i in l until nums.size) {
            nums.swap(i, l)
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                permute(nums, l + 1)
            }
            nums.swap(i, l)
        }
    }
    
    private fun IntArray.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

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

Задача: 329. Longest Increasing Path in a Matrix
Сложность: hard

Дана матрица целых чисел размером m x n. Верните длину самого длинного возрастающего пути в матрице.
Из каждой ячейки можно перемещаться в четырех направлениях: влево, вправо, вверх или вниз. Перемещение по диагонали или выход за границы матрицы (т.е. замкнутые переходы) не допускается.

Пример:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

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

1⃣Инициализация и создание матрицы:
Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке.
Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree.

2⃣Поиск начальных листьев:
Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления".

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

😎 Решение:

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

    fun longestIncreasingPath(matrix: Array<IntArray>): Int {
        val m = matrix.size
        if (m == 0) return 0
        val n = matrix[0].size
        val outdegree = Array(m + 2) { IntArray(n + 2) }
        val newMatrix = Array(m + 2) { IntArray(n + 2) }

        for (i in 0 until m) {
            for (j in 0 until n) {
                newMatrix[i + 1][j + 1] = matrix[i][j]
            }
        }

        for (i in 1..m) {
            for (j in 1..n) {
                for (d in dir) {
                    if (newMatrix[i][j] < newMatrix[i + d[0]][j + d[1]]) {
                        outdegree[i][j]++
                    }
                }
            }
        }

        val leaves = mutableListOf<IntArray>()
        for (i in 1..m) {
            for (j in 1..n) {
                if (outdegree[i][j] == 0) leaves.add(intArrayOf(i, j))
            }
        }

        var height = 0
        while (leaves.isNotEmpty()) {
            height++
            val newLeaves = mutableListOf<IntArray>()
            for (node in leaves) {
                for (d in dir) {
                    val x = node[0] + d[0]
                    val y = node[1] + d[1]
                    if (newMatrix[node[0]][node[1]] > newMatrix[x][y]) {
                        outdegree[x][y]--
                        if (outdegree[x][y] == 0) newLeaves.add(intArrayOf(x, y))
                    }
                }
            }
            leaves.clear()
            leaves.addAll(newLeaves)
        }

        return height
    }
}

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

Задача: 165. Compare Version Numbers
Сложность: medium

Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей.

Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0.

Верните следующее:

- Если version1 < version2, верните -1.
- Если version1 > version2, верните 1.
- В противном случае верните 0.

Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

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

1⃣Разделение строк: Разделите обе строки по символу точки на два массива.

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

3⃣Определение результатов сравнения:
Если два сегмента не равны, верните 1 или -1 в зависимости от того, какой сегмент больше.
Если все сегменты равны после завершения цикла, версии считаются равными. Верните 0

😎 Решение:

class Solution {
    fun compareVersion(version1: String, version2: String): Int {
        val tokens1 = version1.split('.').map { it.toInt() }
        val tokens2 = version2.split('.').map { it.toInt() }

        for (i in 0 until maxOf(tokens1.size, tokens2.size)) {
            val i1 = if (i < tokens1.size) tokens1[i] else 0
            val i2 = if (i < tokens2.size) tokens2[i] else 0

            if (i1 != i2) {
                return if (i1 > i2) 1 else -1
            }
        }
        return 0
    }
}

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

Задача: 589. N-ary Tree Preorder Traversal
Сложность: easy

Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.

Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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

1⃣Инициализация
Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack.

2⃣Итеративный обход
Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack.

3⃣Возврат результата
Верните список output как результат.

😎 Решение:

class Node(var `val`: Int) {
    var children: List<Node?> = listOf()
}

class Solution {
    fun preorder(root: Node?): List<Int> {
        val output = mutableListOf<Int>()
        if (root == null) return output
        val stack = LinkedList<Node>()
        stack.add(root)
        
        while (stack.isNotEmpty()) {
            val node = stack.removeLast()
            output.add(node.`val`)
            for (child in node.children.reversed()) {
                if (child != null) {
                    stack.add(child)
                }
            }
        }
        
        return output
    }
}

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

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

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

Задача: 145. Binary Tree Postorder Traversal
Сложность: easy

Дан корень бинарного дерева, верните обход значений узлов в постпорядке.

Пример:

Input: root = [1,null,2,3]
Output: [3,2,1]

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

1⃣Создайте стек и положите в него корень.

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

3⃣В конце переверните результат — он будет в порядке: корень → правый → левый, а нам нужен левый → правый → корень.

😎 Решение:

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

class Solution {
    fun postorderTraversal(root: TreeNode?): List<Int> {
        if (root == null) {
            return emptyList()
        }

        val stack = mutableListOf(root)
        val output = mutableListOf<Int>()

        while (stack.isNotEmpty()) {
            val node = stack.removeAt(stack.lastIndex)
            output.add(node.`val`)
            node.left?.let { stack.add(it) }
            node.right?.let { stack.add(it) }
        }

        return output.asReversed()
    }
}

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

Задача: 76. Minimum Window Substring
Сложность: hard

Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "".

Тестовые примеры будут сформированы таким образом, что ответ будет уникальным.

Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

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

1⃣Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S.

2⃣Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.

3⃣Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.

😎 Решение:

class Solution {
    fun minWindow(s: String, t: String): String {
        if (t.isEmpty() || s.isEmpty()) return ""

        val dictT = t.groupingBy { it }.eachCount().toMutableMap()
        val required = dictT.size
        var l = 0
        var r = 0
        var formed = 0
        val windowCounts = mutableMapOf<Char, Int>()
        var ans = Triple(Int.MAX_VALUE, 0, 0)

        while (r < s.length) {
            val character = s[r]
            windowCounts[character] = windowCounts.getOrDefault(character, 0) + 1

            if (dictT.containsKey(character) && windowCounts[character] == dictT[character]) {
                formed++
            }

            while (l <= r && formed == required) {
                character = s[l]
                if (r - l + 1 < ans.first) {
                    ans = Triple(r - l + 1, l, r)
                }

                windowCounts[character] = windowCounts.getOrDefault(character, 0) - 1
                if (dictT.containsKey(character) && windowCounts[character]!! < dictT[character]!!) {
                    formed--
                }

                l++
            }

            r++
        }

        return if (ans.first == Int.MAX_VALUE) "" else s.substring(ans.second, ans.third + 1)
    }
}

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

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:

Input: arr = [0]
Output: 1

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

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

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

3⃣Вернуть размер множества.

😎 Решение:

fun subarrayBitwiseORs(arr: IntArray): Int {
    val result = mutableSetOf<Int>()
    var current = mutableSetOf<Int>()
    for (num in arr) {
        val next = mutableSetOf(num)
        for (x in current) {
            next.add(x or num)
        }
        current = next
        result.addAll(current)
    }
    return result.size

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

Задача: 498. Diagonal Traverse
Сложность: medium

Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.

Пример:

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

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

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

2⃣Итерация по диагоналям
Внешний цикл для прохождения по всем диагоналям. Головы диагоналей находятся в первой строке и последнем столбце. Внутренний цикл для итерации по элементам каждой диагонали. Индексы элементов диагонали изменяются до выхода за пределы матрицы.

3⃣Обработка диагоналей
Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result.

😎 Решение:

class Solution {
    fun findDiagonalOrder(mat: Array<IntArray>): IntArray {
        if (mat.isEmpty()) return intArrayOf()
        val N = mat.size
        val M = mat[0].size
        val result = mutableListOf<Int>()
        
        for (d in 0 until N + M - 1) {
            val intermediate = mutableListOf<Int>()
            var r = if (d < M) 0 else d - M + 1
            var c = if (d < M) d else M - 1
            
            while (r < N && c >= 0) {
                intermediate.add(mat[r][c])
                r++
                c--
            }
            
            if (d % 2 == 0) {
                result.addAll(intermediate.reversed())
            } else {
                result.addAll(intermediate)
            }
        }
        
        return result.toIntArray()
    }
}

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

Задача: 506. Relative Ranks
Сложность: easy

Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.

Пример:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

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

1⃣Инициализация и нахождение максимального значения
Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score.

2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].

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

😎 Решение:

class Solution {
    fun findRelativeRanks(score: IntArray): Array<String> {
        val N = score.size
        val maxScore = score.maxOrNull()!!
        val scoreToIndex = IntArray(maxScore + 1)
        
        for (i in score.indices) {
            scoreToIndex[score[i]] = i + 1
        }
        
        val MEDALS = arrayOf("Gold Medal", "Silver Medal", "Bronze Medal")
        val rank = Array(N) { "" }
        var place = 1
        
        for (i in maxScore downTo 0) {
            if (scoreToIndex[i] != 0) {
                val originalIndex = scoreToIndex[i] - 1
                rank[originalIndex] = if (place < 4) MEDALS[place - 1] else place.toString()
                place++
            }
        }
        
        return rank
    }
}

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

Задача: 906. Super Palindromes
Сложность: hard

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

Input: left = "4", right = "1000"
Output: 4

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

1⃣Найти все палиндромы до корня из right.

2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right].

3⃣Подсчитать количество таких суперпалиндромов.

😎 Решение:

class Solution {
    fun isPalindrome(x: Long): Boolean {
        val s = x.toString()
        return s == s.reversed()
    }

    fun superpalindromesInRange(left: String, right: String): Int {
        val leftNum = left.toLong()
        val rightNum = right.toLong()
        var count = 0

        for (i in 1 until 100000) {
            val s = i.toString()
            val palin1 = (s + s.reversed()).toLong()
            val palin2 = (s + s.dropLast(1).reversed()).toLong()

            if (palin1 * palin1 > rightNum) {
                break
            }
            if (palin1 * palin1 >= leftNum && isPalindrome(palin1 * palin1)) {
                count++
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && isPalindrome(palin2 * palin2)) {
                count++
            }
        }

        return count
    }
}

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

Задача: 518. Coin Change II
Сложность: medium

Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0.

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

Ответ гарантированно вписывается в знаковое 32-битное целое число.

Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

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

1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты.

2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его.

3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу.

😎 Решение:

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val memo = Array(coins.size) { IntArray(amount + 1) { -1 } }
        
        fun numberOfWays(i: Int, amount: Int): Int {
            if (amount == 0) return 1
            if (i == coins.size) return 0
            if (memo[i][amount] != -1) return memo[i][amount]
            
            memo[i][amount] = if (coins[i] > amount) {
                numberOfWays(i + 1, amount)
            } else {
                numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
            }
            return memo[i][amount]
        }
        
        return numberOfWays(0, amount)
    }
}

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

Задача: 231. Power of Two
Сложность: easy

Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.

Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.

Пример:

Input: n = 1
Output: true
Explanation: 2^0 = 1

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

1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки.

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

3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x.

😎 Решение:

class Solution {
    fun isPowerOfTwo(n: Int): Boolean {
        if (n == 0) return false
        val x = n.toLong()
        return (x and -x) == x
    }
}

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

Задача: 935. Knight Dialer
Сложность: medium

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


Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 10

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

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

2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1).
На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня.

3⃣Вернуть сумму всех значений в массиве DP на последнем шаге.

😎 Решение:

class Solution {
    fun knightDialer(n: Int): Int {
        val MOD = 1000000007
        val moves = arrayOf(
            intArrayOf(4, 6),
            intArrayOf(6, 8),
            intArrayOf(7, 9),
            intArrayOf(4, 8),
            intArrayOf(0, 3, 9),
            intArrayOf(),
            intArrayOf(0, 1, 7),
            intArrayOf(2, 6),
            intArrayOf(1, 3),
            intArrayOf(2, 4)
        )
        
        var dp = IntArray(10) { 1 }
        
        for (step in 1 until n) {
            val newDp = IntArray(10)
            for (i in 0 until 10) {
                for (move in moves[i]) {
                    newDp[move] = (newDp[move] + dp[i]) % MOD
                }
            }
            dp = newDp
        }
        
        return dp.fold(0) { acc, count -> (acc + count) % MOD }
    }
}

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

Задача: 157. Read N Characters Given Read4
Сложность: easy

У вас есть файл, который можно читать только через API read4(buf4).
Реализуйте метод read(buf, n), который прочитает не более n символов и запишет их в buf.

Пример:

Input: file = "abc", n = 4 Output: 3
buf после вызова должен содержать "abc".

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

1⃣Создайте вспомогательный буфер buf4 размером 4 и переменные copiedChars = 0 и readChars = 4.

2⃣Пока copiedChars < n и readChars == 4, вызывайте read4(buf4).
Копируйте символы из buf4 в buf, пока не достигнете n.

3⃣Когда достигнут EOF или прочитано n символов, остановитесь и верните copiedChars — общее количество успешно прочитанных символов.

😎 Решение:

class Solution {
    fun read(buf: Array<Char>, n: Int): Int {
        var copiedChars = 0
        var readChars = 4
        val buf4 = Array(4) { ' ' } 

        while (copiedChars < n && readChars == 4) {
            readChars = read4(buf4)

            for (i in 0 until readChars) {
                if (copiedChars == n) {
                    return copiedChars
                }
                buf[copiedChars] = buf4[i]
                copiedChars++
            }
        }
        return copiedChars
    }

    private fun read4(buf4: Array<Char>): Int {
        return 0
    }
}

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

Задача: 118. Pascal's Triangle
Сложность: easy

Дано целое число numRows. Верните первые numRows строк треугольника Паскаля.

В треугольнике Паскаля каждое число является суммой двух чисел, непосредственно расположенных над ним, как показано:

Пример:

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

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

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

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

3⃣Поскольку numRows всегда больше 0, мы можем инициализировать треугольник первой строкой [1] и продолжить заполнять строки следующим образом:

😎 Решение:

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val triangle = mutableListOf<List<Int>>()

        for (rowNum in 0 until numRows) {
            val row = MutableList(rowNum + 1) { 0 }
            row[0] = 1
            row[row.lastIndex] = 1

            for (j in 1 until row.size - 1) {
                row[j] = triangle[rowNum - 1][j - 1] + triangle[rowNum - 1][j]
            }

            triangle.add(row)
        }

        return triangle
    }
}

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

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

Input: n = 4
Output: [2,1,4,3]

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

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

😎 Решение:

class Solution {
    fun beautifulArray(n: Int): IntArray {
        return construct(n).toIntArray()
    }
    
    private fun construct(n: Int): List<Int> {
        if (n == 1) return listOf(1)
        val odd = construct((n + 1) / 2).map { 2 * it - 1 }
        val even = construct(n / 2).map { 2 * it }
        return odd + even
    }
}

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

Задача: 737. Sentence Similarity II
Сложность: medium

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

fun areSentencesSimilar(sentence1: Array<String>, sentence2: Array<String>, similarPairs: List<List<String>>): Boolean {
    if (sentence1.size != sentence2.size) {
        return false
    }
    
    val graph = mutableMapOf<String, MutableList<String>>()
    for (pair in similarPairs) {
        val (x, y) = pair
        graph.computeIfAbsent(x) { mutableListOf() }.add(y)
        graph.computeIfAbsent(y) { mutableListOf() }.add(x)
    }
    
    fun dfs(word1: String, word2: String, visited: MutableSet<String>): Boolean {
        if (word1 == word2) {
            return true
        }
        visited.add(word1)
        for (neighbor in graph[word1].orEmpty()) {
            if (neighbor !in visited && dfs(neighbor, word2, visited)) {
                return true
            }
        }
        return false
    }
    
    for (i in sentence1.indices) {
        if (sentence1[i] != sentence2[i]) {
            if (!dfs(sentence1[i], sentence2[i], mutableSetOf())) {
                return false
            }
        }
    }
    
    return true
}

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

Задача: 838. Push Dominoes
Сложность: medium

Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо.
Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа.
Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил.

В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино.
Вам дано строковое представление начального состояния домино:
dominoes[i] = 'L', если i-е домино толкнули влево,
dominoes[i] = 'R', если i-е домино толкнули вправо, и
dominoes[i] = '.', если i-е домино не было толкнуто.
Верните строку, представляющую конечное состояние.

Пример:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

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

1⃣Пройдите по строке и сохраните индексы и символы не пустых домино в массивы.

2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики.

3⃣Обработайте промежутки между соседними домино, обновляя их состояния согласно правилам.

😎 Решение:

class Solution {
    fun pushDominoes(dominoes: String): String {
        val N = dominoes.length
        val indexes = mutableListOf(-1)
        val symbols = mutableListOf('L')
        
        for (i in dominoes.indices) {
            if (dominoes[i] != '.') {
                indexes.add(i)
                symbols.add(dominoes[i])
            }
        }
        
        indexes.add(N)
        symbols.add('R')
        
        val ans = dominoes.toCharArray()
        for (idx in 0 until indexes.size - 1) {
            val i = indexes[idx]
            val j = indexes[idx + 1]
            val x = symbols[idx]
            val y = symbols[idx + 1]
            if (x == y) {
                for (k in i + 1 until j) {
                    ans[k] = x
                }
            } else if (x == 'R' && y == 'L') {
                for (k in i + 1 until j) {
                    if (k - i == j - k) {
                        ans[k] = '.'
                    } else if (k - i < j - k) {
                        ans[k] = 'R'
                    } else {
                        ans[k] = 'L'
                    }
                }
            }
        }
        
        return String(ans)
    }

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