Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

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

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
    var count = 0

    fun dfs(node: Int, parent: Int, adj: Map<Int, List<Pair<Int, Int>>>) {
        adj[node]?.forEach { (neighbor, sign) ->
            if (neighbor != parent) {
                count += sign
                dfs(neighbor, node, adj)
            }
        }
    }

    fun minReorder(n: Int, connections: Array<IntArray>): Int {
        val adj = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()
        for (connection in connections) {
            adj.computeIfAbsent(connection[0]) { mutableListOf() }.add(connection[1] to 1)
            adj.computeIfAbsent(connection[1]) { mutableListOf() }.add(connection[0] to 0)
        }
        dfs(0, -1, adj)
        return count
    }
}

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

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

😎 Решение:

class CombinationIterator(characters: String, combinationLength: Int) {
    private val combinations: MutableList<String> = mutableListOf()

    init {
        val n = characters.length
        val k = combinationLength
        for (bitmask in 0 until (1 shl n)) {
            if (bitmask.countOneBits() == k) {
                val curr = StringBuilder()
                for (j in 0 until n) {
                    if (bitmask and (1 shl (n - j - 1)) != 0) {
                        curr.append(characters[j])
                    }
                }
                combinations.add(curr.toString())
            }
        }
    }

    fun next(): String {
        return combinations.removeAt(combinations.size - 1)
    }

    fun hasNext(): Boolean {
        return combinations.isNotEmpty()
    }
}

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

Задача: 98. Validate Binary Search Tree
Сложность: medium

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

Пример:

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

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

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

2⃣Храним значение предыдущего узла и сравниваем его с текущим: если текущее значение не больше предыдущего — дерево не BST.

3⃣Таким образом, проходим дерево один раз, не храня весь список обхода, что экономит память.

😎 Решение:

class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

class Solution {
    private var prev: Long = Long.MIN_VALUE

    private fun inorder(root: TreeNode?): Boolean {
        if (root == null) {
            return true
        }
        if (!inorder(root.left)) {
            return false
        }
        if (root.value <= prev) {
            return false
        }
        prev = root.value.toLong()
        return inorder(root.right)
    }

    fun isValidBST(root: TreeNode?): Boolean {
        return inorder(root)
    }
}

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

Задача: 754. Reach a Number
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

fun reachTarget(target: Int): Int {
    var target = kotlin.math.abs(target)
    var position = 0
    var steps = 0
    while (position < target || (position - target) % 2 != 0) {
        steps++
        position += steps
    }
    return steps
}

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

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

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

1⃣Установите два указателя — с начала и конца строки.

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

3⃣Если встретились несовпадающие символы — это не палиндром, иначе — да.

😎 Решение:

class Solution {
    fun isPalindrome(s: String): Boolean {
        var i = 0
        var j = s.length - 1

        while (i < j) {
            while (i < j && !s[i].isLetterOrDigit()) {
                i++
            }
            while (i < j && !s[j].isLetterOrDigit()) {
                j--
            }

            if (s[i].toLowerCase() != s[j].toLowerCase()) {
                return false
            }

            i++
            j--
        }

        return true
    }
}

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

Задача: 1243. Array Transformation
Сложность: easy

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

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

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

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

class Solution {
    fun transformArray(arr: IntArray): IntArray {
        var arr = arr
        var changed: Boolean
        do {
            changed = false
            val newArr = arr.copyOf()
            for (i in 1 until arr.size - 1) {
                if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                    newArr[i]++
                    changed = true
                } else if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                    newArr[i]--
                    changed = true
                }
            }
            arr = newArr
        } while (changed)
        return arr
    }
}

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

Задача: 250. Count Univalue Subtrees
Сложность: medium

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

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

Пример:

Input: root = [5,1,5,5,5,null,5]
Output: 4

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

1⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.

2⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, верните true.
Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false.

3⃣Верните count.

😎 Решение:

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

class Solution {
    private var count = 0

    private fun dfs(node: TreeNode?): Boolean {
        if (node == null) {
            return true
        }

        val isLeftUniValue = dfs(node.left)
        val isRightUniValue = dfs(node.right)

        if (isLeftUniValue && isRightUniValue) {
            if (node.left != null && node.left!!.`val` != node.`val`) {
                return false
            }
            if (node.right != null && node.right!!.`val` != node.`val`) {
                return false
            }
            count++
            return true
        }
        return false
    }

    fun countUnivalSubtrees(root: TreeNode?): Int {
        dfs(root)
        return count
    }
}

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

Задача: 36. Valid Sudoku
Сложность: medium

Определите, является ли доска Судоку 9x9 валидной. Проверяются только заполненные ячейки, следуя правилам:
- В каждой строке числа 1-9 не повторяются.
- В каждом столбце числа 1-9 не повторяются.
- В каждом 3x3 блоке числа 1-9 не повторяются.

Пример:

Input: board =  
[["5","3",".",".","7",".",".",".","."]  
,["6",".",".","1","9","5",".",".","."]  
,[".","9","8",".",".",".",".","6","."]  
,["8",".",".",".","6",".",".",".","3"]  
,["4",".",".","8",".","3",".",".","1"]  
,["7",".",".",".","2",".",".",".","6"]  
,[".","6",".",".",".",".","2","8","."]  
,[".",".",".","4","1","9",".",".","5"]  
,[".",".",".",".","8",".",".","7","9"]]  
Output: true  

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

1⃣Создаем три массива Set, чтобы отслеживать числа в строках, столбцах и 3x3 блоках.

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

3⃣Если не найдено повторений, возвращаем true, иначе false.

😎 Решение:

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        val N = 9
        val rows = Array(N) { mutableSetOf<Char>() }
        val cols = Array(N) { mutableSetOf<Char>() }
        val boxes = Array(N) { mutableSetOf<Char>() }

        for (r in 0 until N) {
            for (c in 0 until N) {
                val value = board[r][c]
                if (value == '.') continue

                if (!rows[r].add(value) || !cols[c].add(value) || !boxes[(r / 3) * 3 + (c / 3)].add(value)) {
                    return false
                }
            }
        }

        return true
    }
}

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

Задача: 1493. Longest Subarray of 1's After Deleting One Element
Сложность: medium

Дан бинарный массив nums, из которого следует удалить один элемент.

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

Пример:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

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

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

2⃣Итерация по массиву:
При каждом элементе увеличиваем zeroCount, если это ноль.
Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1.
Обновляем longestWindow текущей длиной окна i - start.

3⃣Возврат результата:
Вернуть longestWindow.

😎 Решение:

class Solution {
    fun longestSubarray(nums: IntArray): Int {
        var zeroCount = 0
        var longestWindow = 0
        var start = 0

        for (i in nums.indices) {
            if (nums[i] == 0) {
                zeroCount++
            }

            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--
                }
                start++
            }

            longestWindow = maxOf(longestWindow, i - start)
        }

        return longestWindow
    }
}

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

Задача: 513. Find Bottom Left Tree Value
Сложность: medium

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

Пример:

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

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

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

2⃣Реализуйте рекурсивную функцию dfs, которая обходит дерево и находит самое левое значение в последней строке дерева. Параметры функции: current (текущий узел) и depth (его глубина). Проверьте, пуст ли текущий узел. Если да, то вернитесь.

3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎 Решение:

class Solution {
    private var maxDepth = -1
    private var bottomLeftValue = 0
    
    fun findBottomLeftValue(root: TreeNode?): Int {
        dfs(root, 0)
        return bottomLeftValue
    }
    
    private fun dfs(current: TreeNode?, depth: Int) {
        if (current == null) return
        
        if (depth > maxDepth) {
            maxDepth = depth
            bottomLeftValue = current.`val`
        }
        
        dfs(current.left, depth + 1)
        dfs(current.right, depth + 1)
    }
}

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

Задача: 269. Alien Dictionary
Сложность: hard

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

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

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

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

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

import java.util.*

class Solution {
    fun alienOrder(words: Array<String>): String {
        val adjList = mutableMapOf<Char, MutableSet<Char>>()
        val inDegree = mutableMapOf<Char, Int>()

        for (word in words) {
            for (char in word) {
                inDegree[char] = 0
            }
        }

        for ((firstWord, secondWord) in words.zip(words.drop(1))) {
            for ((c, d) in firstWord.zip(secondWord)) {
                if (c != d) {
                    if (d !in adjList.getOrDefault(c, mutableSetOf())) {
                        adjList.getOrPut(c) { mutableSetOf() }.add(d)
                        inDegree[d] = inDegree.getOrDefault(d, 0) + 1
                    }
                    break
                }
            }
            if (secondWord.length < firstWord.length && firstWord.startsWith(secondWord)) {
                return ""
            }
        }

        val output = mutableListOf<Char>()
        val queue: Queue<Char> = LinkedList()

        for ((char, degree) in inDegree) {
            if (degree == 0) {
                queue.add(char)
            }
        }

        while (queue.isNotEmpty()) {
            val c = queue.poll()
            output.add(c)
            for (d in adjList.getOrDefault(c, emptySet())) {
                inDegree[d] = inDegree[d]!! - 1
                if (inDegree[d] == 0) {
                    queue.add(d)
                }
            }
        }

        if (output.size < inDegree.size) {
            return ""
        }

        return output.joinToString("")
    }
}

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

Задача: 79. Word Search
Сложность: medium

Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.

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

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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

1⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки.

2⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова.

3⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования.

😎 Решение:

class Solution {
    lateinit var board: Array<CharArray>
    var ROWS: Int = 0
    var COLS: Int = 0

    fun exist(board: Array<CharArray>, word: String): Boolean {
        this.board = board
        ROWS = board.size
        COLS = board[0].size

        for (row in 0 until ROWS) {
            for (col in 0 until COLS) {
                if (backtrack(row, col, word, 0)) {
                    return true
                }
            }
        }
        return false
    }

    private fun backtrack(row: Int, col: Int, word: String, index: Int): Boolean {
        if (index == word.length) return true
        if (row < 0 || row == ROWS || col < 0 || col == COLS || board[row][col] != word[index]) return false

        board[row][col] = '#'
        val result = (backtrack(row + 1, col, word, index + 1) ||
                      backtrack(row - 1, col, word, index + 1) ||
                      backtrack(row, col + 1, word, index + 1) ||
                      backtrack(row, col - 1, word, index + 1))
        board[row][col] = word[index]
        return result
    }
}

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

Задача: 91. Decode Ways
Сложность: medium

Сообщение, содержащее только цифры, нужно декодировать в буквы от 'A' до 'Z', где 'A' → "1", 'B' → "2", ..., 'Z' → "26". Верните количество всех возможных способов декодирования строки.

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

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

1⃣Входим в рекурсию с данной строкой, начиная с индекса 0.

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

3⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.


😎 Решение:

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

    private fun recursiveWithMemo(index: Int, s: String): Int {
        if (index == s.length) {
            return 1
        }

        if (s[index] == '0') {
            return 0
        }

        if (index == s.length - 1) {
            return 1
        }

        memo[index]?.let {
            return it
        }

        var answer = recursiveWithMemo(index + 1, s)
        if (index < s.length - 1 && s.substring(index, index + 2).toInt() <= 26) {
            answer += recursiveWithMemo(index + 2, s)
        }

        memo[index] = answer
        return answer
    }

    fun numDecodings(s: String): Int {
        return recursiveWithMemo(0, s)
    }
}

fun main() {
    val solution = Solution()
    val s = "226"
    println("Number of ways to decode: ${solution.numDecodings(s)}")
}

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

Задача: 557. Reverse Words in a String III
Сложность: easy

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

Пример:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

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

1⃣Создайте переменную lastSpaceIndex и установите её значение в -1. Пройдите по каждому символу строки s от 0-го до n-го индекса, используя указатель strIndex.

2⃣Когда strIndex указывает на пробел, определите начало (startIndex = lastSpaceIndex + 1) и конец (endIndex = strIndex - 1) текущего слова. Используя два указателя, измените порядок символов в текущем слове.

3⃣Обновите lastSpaceIndex значением strIndex. После окончания цикла измените порядок символов в последнем слове (от lastSpaceIndex + 1 до конца строки).

😎 Решение:

class Solution {
    fun reverseWords(s: String): String {
        val chars = s.toCharArray()
        var lastSpaceIndex = -1
        val len = chars.size

        for (strIndex in 0..len) {
            if (strIndex == len || chars[strIndex] == ' ') {
                var startIndex = lastSpaceIndex + 1
                var endIndex = strIndex - 1
                while (startIndex < endIndex) {
                    val temp = chars[startIndex]
                    chars[startIndex] = chars[endIndex]
                    chars[endIndex] = temp
                    startIndex++
                    endIndex--
                }
                lastSpaceIndex = strIndex
            }
        }

        return String(chars)
    }
}

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

Задача: 1485. Clone Binary Tree With Random Pointer
Сложность: medium

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

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

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

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

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

3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎 Решение:

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

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

class Solution {
    private val newOldPairs = HashMap<Node, NodeCopy>()

    private fun deepCopy(root: Node?): NodeCopy? {
        root ?: return null
        val newRoot = NodeCopy(root.`val`)
        newRoot.left = deepCopy(root.left)
        newRoot.right = deepCopy(root.right)
        newOldPairs[root] = newRoot
        return newRoot
    }

    private fun mapRandomPointers(oldNode: Node?) {
        oldNode ?: return
        val newNode = newOldPairs[oldNode]
        newNode?.random = newOldPairs[oldNode.random]
        mapRandomPointers(oldNode.left)
        mapRandomPointers(oldNode.right)
    }

    fun copyRandomBinaryTree(root: Node?): NodeCopy? {
        val newRoot = deepCopy(root)
        mapRandomPointers(root)
        return newRoot
    }
}

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

Задача: 153. Find Minimum in Rotated Sorted Array
Сложность: medium

Дан массив nums, отсортированный по возрастанию и повернутый несколько раз.
Нужно найти минимальный элемент массива.
Все элементы уникальны, и требуется решение за O(log n).

Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

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

1⃣Если массив уже отсортирован (nums[0] < nums[n-1]), то минимум — первый элемент.

2⃣Иначе используем бинарный поиск: Если nums[mid] > nums[mid + 1] — минимум справа (mid+1). Если nums[mid - 1] > nums[mid] — минимум в mid.

3⃣В зависимости от значения nums[mid], сдвигаем границы поиска влево или вправо, пока не найдём точку перегиба.

😎 Решение:

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

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

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

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

Задача: 653. Two Sum IV - Input is a BST
Сложность: easy

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

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

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

3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎 Решение:

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

fun findTarget(root: TreeNode?, k: Int): Boolean {
    val seen = mutableSetOf<Int>()
    fun find(node: TreeNode?): Boolean {
        if (node == null) return false
        if (seen.contains(k - node.`val`)) return true
        seen.add(node.`val`)
        return find(node.left) || find(node.right)
    }
    return find(root)
}

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

Задача: 636. Exclusive Time of Functions
Сложность: medium

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов
Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

3⃣Обновление времени выполнения
Когда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций.

😎 Решение:

class Solution {
    fun exclusiveTime(n: Int, logs: List<String>): IntArray {
        val stack = mutableListOf<Int>()
        val times = IntArray(n)
        var prevTime = 0
        
        for (log in logs) {
            val parts = log.split(":")
            val fid = parts[0].toInt()
            val type = parts[1]
            val time = parts[2].toInt()
            
            if (type == "start") {
                if (stack.isNotEmpty()) {
                    times[stack.last()] += time - prevTime
                }
                stack.add(fid)
                prevTime = time
            } else {
                times[stack.removeAt(stack.size - 1)] += time - prevTime + 1
                prevTime = time + 1
            }
        }
        
        return times
    }
}

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

Задача: 995. Minimum Number of K Consecutive Bit Flips
Сложность: hard

Дан бинарный массив nums и целое число k.

Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0.

Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1.

Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

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

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

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

3⃣Проверка возможности выполнения задачи:
Если количество переворотов больше длины массива, верните -1.

😎 Решение:

class Solution {
    fun minKBitFlips(nums: IntArray, k: Int): Int {
        val n = nums.size
        var flip = 0
        var flips = 0
        val flipQueue = IntArray(n)
        
        for (i in 0 until n) {
            if (i >= k) {
                flip = flip xor flipQueue[i - k]
            }
            if (nums[i] == flip) {
                if (i + k > n) return -1
                flips++
                flip = flip xor 1
                flipQueue[i] = 1
            }
        }
        return flips
    }
}

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

Задача: 1009. Complement of Base 10 Integer
Сложность: easy

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5
Output: 2

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

1⃣Определение длины двоичного представления:
Найдите длину двоичного представления числа n.

2⃣Создание маски:
Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

3⃣Вычисление дополнения:
Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа.

😎 Решение:

class Solution {
    fun findComplement(num: Int): Int {
        val length = 32 - Integer.numberOfLeadingZeros(num)
        val mask = (1 shl length) - 1
        return num xor mask
    }
}

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