Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard

Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.

Пример:

Input: n = 2, m = 3
Output: 3

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

1⃣Инициализация рекурсивной функции:
Функция принимает размеры прямоугольника n x m.

2⃣Базовый случай:
Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия.

3⃣Рекурсивный случай:
Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

class Solution {
    fun tilingRectangle(n: Int, m: Int): Int {
        val dp = Array(n + 1) { IntArray(m + 1) { Int.MAX_VALUE } }
        
        for (i in 1..minOf(n, m)) {
            dp[i][i] = 1
        }
        
        for (h in 1..n) {
            for (w in 1..m) {
                if (h == w) continue
                for (i in 1..h / 2) {
                    dp[h][w] = minOf(dp[h][w], dp[i][w] + dp[h - i][w])
                }
                for (j in 1..w / 2) {
                    dp[h][w] = minOf(dp[h][w], dp[h][j] + dp[h][w - j])
                }
            }
        }
        return dp[n][m]
    }
}

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

Задача: 895. Maximum Frequency Stack
Сложность: hard

Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.

Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.

2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.

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

😎 Решение:

class FreqStack() {
    private val freq = mutableMapOf<Int, Int>()
    private val group = mutableMapOf<Int, MutableList<Int>>()
    private var maxfreq = 0

    fun push(`val`: Int) {
        val f = (freq[`val`] ?: 0) + 1
        freq[`val`] = f
        if (f > maxfreq) {
            maxfreq = f
            group[f] = mutableListOf()
        }
        group[f]?.add(`val`)
    }

    fun pop(): Int {
        val val = group[maxfreq]?.removeAt(group[maxfreq]?.lastIndex ?: 0) ?: -1
        freq[val] = freq[val]!! - 1
        if (group[maxfreq]?.isEmpty() == true) {
            maxfreq--
        }
        return val
    }

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

Задача: 42. Trapping Rain Water
Сложность: hard

Дан массив height, представляющий карту высот.
Каждый столбец имеет ширину 1. Вычислите, сколько воды можно удержать после дождя.

Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]  
Output: 6  

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

1⃣Создаем массивы left_max и right_max, хранящие максимальные высоты слева и справа для каждого индекса.

2⃣Проходим массив, вычисляя минимальную границу воды min(left_max[i], right_max[i]) и добавляем разницу с height[i] в ans.

3⃣Возвращаем ans, содержащий общий объем воды.

😎 Решение:

class Solution {
    fun trap(height: IntArray): Int {
        if (height.isEmpty()) return 0
        val size = height.size
        var ans = 0
        val leftMax = IntArray(size)
        val rightMax = IntArray(size)

        leftMax[0] = height[0]
        for (i in 1 until size) {
            leftMax[i] = maxOf(height[i], leftMax[i - 1])
        }

        rightMax[size - 1] = height[size - 1]
        for (i in size - 2 downTo 0) {
            rightMax[i] = maxOf(height[i], rightMax[i + 1])
        }

        for (i in 1 until size - 1) {
            ans += minOf(leftMax[i], rightMax[i]) - height[i]
        }

        return ans
    }
}

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

Задача: 292. Nim Game
Сложность: easy

Вы играете в следующую игру Nim со своим другом:

Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

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

1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎 Решение:

class Solution {
    fun canWinNim(n: Int): Boolean {
        return n % 4 != 0
    }
}

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

Задача: 35. Search Insert Position
Сложность: easy

Дан отсортированный массив уникальных целых чисел и target.
Верните индекс, если target найден. Если нет, верните индекс, куда он должен быть вставлен.
Алгоритм должен работать за O(log n).

Пример:

Input: nums = [1,3,5,6], target = 5  
Output: 2  

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

1⃣Используем бинарный поиск, инициализируя left = 0 и right = nums.size - 1.

2⃣Пока left <= right, сравниваем target с nums[mid] и сужаем границы поиска.

3⃣Если target не найден, left указывает на его позицию для вставки.

😎 Решение:

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

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

Задача: 404. Sum of Left Leaves
Сложность: easy

Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 24

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

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

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

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

😎 Решение:

class Solution {
    fun sumOfLeftLeaves(root: TreeNode?): Int {
        return dfs(root, false)
    }
    
    private fun dfs(node: TreeNode?, isLeft: Boolean): Int {
        if (node == null) return 0
        if (node.left == null && node.right == null) {
            return if (isLeft) node.`val` else 0
        }
        return dfs(node.left, true) + dfs(node.right, false)
    }
}

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

Задача: 741. Cherry Pickup
Сложность: hard

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

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

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

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

😎 Решение:

fun cherryPickup(grid: Array<IntArray>): Int {
    val n = grid.size
    val dp = Array(n) { Array(n) { IntArray(2 * n - 1) { Int.MIN_VALUE } } }
    dp[0][0][0] = grid[0][0]

    for (k in 1 until 2 * n - 1) {
        for (i1 in maxOf(0, k - n + 1)..minOf(n - 1, k)) {
            for (i2 in maxOf(0, k - n + 1)..minOf(n - 1, k)) {
                val j1 = k - i1
                val j2 = k - i2
                if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
                    var maxCherries = Int.MIN_VALUE
                    if (i1 > 0 && i2 > 0) maxCherries = maxOf(maxCherries, dp[i1 - 1][i2 - 1][k - 1])
                    if (i1 > 0) maxCherries = maxOf(maxCherries, dp[i1 - 1][i2][k - 1])
                    if (i2 > 0) maxCherries = maxOf(maxCherries, dp[i1][i2 - 1][k - 1])
                    maxCherries = maxOf(maxCherries, dp[i1][i2][k - 1])
                    if (maxCherries != Int.MIN_VALUE) {
                        dp[i1][i2][k] = maxCherries + grid[i1][j1]
                        if (i1 != i2) dp[i1][i2][k] += grid[i2][j2]
                    }
                }
            }
        }
    }

    return maxOf(0, dp[n - 1][n - 1][2 * n - 1])
}

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.

Пример:

Input: left = 5, right = 7
Output: 4

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

1⃣Сдвигать left и right вправо, пока они не станут равными.

2⃣Подсчитать количество сдвигов.

3⃣Сдвинуть left влево на количество сдвигов и вернуть результат.

😎 Решение:

class Solution {
    fun rangeBitwiseAnd(left: Int, right: Int): Int {
        var m = left
        var n = right
        var shift = 0
        
        while (m < n) {
            m = m shr 1
            n = n shr 1
            shift += 1
        }
        
        return m shl shift
    }
}

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

Задача: 1482. Minimum Number of Days to Make m Bouquets
Сложность: medium

Вам дан массив целых чисел bloomDay, целое число m и целое число k.

Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада.
Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете.

Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -1.

Пример:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

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

1⃣Инициализация:
Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay.
Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день.

2⃣Поиск минимального числа дней:
Выполняйте бинарный поиск, пока start меньше или равен end:
- рассчитайте mid как среднее значение между start и end.
- используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день.
- если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево.
- иначе переместите start вправо.

3⃣Возвращение результата:
Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно.

😎 Решение:

class Solution {
    private fun getNumOfBouquets(bloomDay: IntArray, mid: Int, k: Int): Int {
        var numOfBouquets = 0
        var count = 0
        for (day in bloomDay) {
            if (day <= mid) {
                count++
            } else {
                count = 0
            }
            if (count == k) {
                numOfBouquets++
                count = 0
            }
        }
        return numOfBouquets
    }

    fun minDays(bloomDay: IntArray, m: Int, k: Int): Int {
        if (bloomDay.size < m * k) return -1
        var start = 0
        var end = bloomDay.maxOrNull()!!
        var minDays = -1
        while (start <= end) {
            val mid = (start + end) / 2
            if (getNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid
                end = mid - 1
            } else {
                start = mid + 1
            }
        }
        return minDays
    }
}

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

Задача: 361. Bomb Enemy
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

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

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

2⃣Реализовать функцию killEnemies(row, col), которая считает количество врагов, убитых бомбой, установленных в пустой ячейке (row, col), проверяя все четыре направления (влево, вправо, вверх, вниз) до стены или границы сетки.

3⃣Вернуть максимальное количество врагов, убитых среди всех пустых ячеек.

😎 Решение:

class Solution {
    fun maxKilledEnemies(grid: Array<CharArray>): Int {
        if (grid.isEmpty()) return 0

        val rows = grid.size
        val cols = grid[0].size
        var maxCount = 0

        for (row in 0 until rows) {
            for (col in 0 until cols) {
                if (grid[row][col] == '0') {
                    val hits = killEnemies(row, col, grid)
                    maxCount = maxOf(maxCount, hits)
                }
            }
        }

        return maxCount
    }

    private fun killEnemies(row: Int, col: Int, grid: Array<CharArray>): Int {
        var enemyCount = 0
        val directions = arrayOf(
            intArrayOf(-1, 0), intArrayOf(1, 0),
            intArrayOf(0, -1), intArrayOf(0, 1)
        )

        for (direction in directions) {
            var r = row + direction[0]
            var c = col + direction[1]

            while (r in grid.indices && c in grid[0].indices) {
                when (grid[r][c]) {
                    'W' -> break
                    'E' -> enemyCount++
                }
                r += direction[0]
                c += direction[1]
            }
        }

        return enemyCount
    }
}

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

Задача: 712. Minimum ASCII Delete Sum for Two Strings
Сложность: medium

Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.

Пример:

Input: s1 = "sea", s2 = "eat"
Output: 231

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

1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2.

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

3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])).

😎 Решение:

fun minimumDeleteSum(s1: String, s2: String): Int {
    val dp = Array(s1.length + 1) { IntArray(s2.length + 1) }
    for (i in 1..s1.length) {
        dp[i][0] = dp[i - 1][0] + s1[i - 1].toInt()
    }
    for (j in 1..s2.length) {
        dp[0][j] = dp[0][j - 1] + s2[j - 1].toInt()
    }
    for (i in 1..s1.length) {
        for (j in 1..s2.length) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = minOf(dp[i - 1][j] + s1[i - 1].toInt(), dp[i][j - 1] + s2[j - 1].toInt())
            }
        }
    }
    return dp[s1.length][s2.length]
}

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

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

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

Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

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

1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.

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

3⃣Создайте новую строку, удалив все помеченные скобки.

😎 Решение:

class Solution {
    fun minRemoveToMakeValid(s: String): String {
        val stack = Stack<Int>()
        val sb = StringBuilder(s)
        for (i in sb.indices) {
            when (sb[i]) {
                '(' -> stack.push(i)
                ')' -> {
                    if (stack.isNotEmpty()) {
                        stack.pop()
                    } else {
                        sb.setCharAt(i, '*')
                    }
                }
            }
        }
        while (stack.isNotEmpty()) {
            sb.setCharAt(stack.pop(), '*')
        }
        return sb.toString().replace("*", "")
    }
}

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

Задача: 934. Shortest Bridge
Сложность: medium

Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.

Пример:

Input: grid = [[0,1],[1,0]]
Output: 1

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

1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.

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

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

😎 Решение:

class Solution {
    fun shortestBridge(grid: Array<IntArray>): Int {
        val n = grid.size
        val directions = arrayOf(
            intArrayOf(-1, 0),
            intArrayOf(1, 0),
            intArrayOf(0, -1),
            intArrayOf(0, 1)
        )
        
        fun neighbors(x: Int, y: Int): List<Pair<Int, Int>> {
            return directions.map { (dx, dy) -> Pair(x + dx, y + dy) }.filter { (nx, ny) -> nx in 0 until n && ny in 0 until n }
        }
        
        fun bfs(queue: MutableList<Pair<Int, Int>>): Int {
            val visited = mutableSetOf<Pair<Int, Int>>().apply { addAll(queue) }
            var steps = 0
            while (queue.isNotEmpty()) {
                val newQueue = mutableListOf<Pair<Int, Int>>()
                for ((x, y) in queue) {
                    for ((nx, ny) in neighbors(x, y)) {
                        if (Pair(nx, ny) !in visited) {
                            if (grid[nx][ny] == 1) {
                                return steps
                            }
                            visited.add(Pair(nx, ny))
                            newQueue.add(Pair(nx, ny))
                        }
                    }
                }
                queue = newQueue
                steps++
            }
            return -1
        }
        
        fun findFirstIsland(): MutableList<Pair<Int, Int>> {
            for (i in 0 until n) {
                for (j in 0 until n) {
                    if (grid[i][j] == 1) {
                        val queue = mutableListOf(Pair(i, j))
                        grid[i][j] = -1
                        val island = mutableListOf(Pair(i, j))
                        while (queue.isNotEmpty()) {
                            val (x, y) = queue.removeAt(0)
                            for ((nx, ny) in neighbors(x, y)) {
                                if (grid[nx][ny] == 1) {
                                    grid[nx][ny] = -1
                                    queue.add(Pair(nx, ny))
                                    island.add(Pair(nx, ny))
                                }
                            }
                        }
                        return island
                    }
                }
            }
            return mutableListOf()
        }
        
        val island = findFirstIsland()
        return bfs(island)
    }
}

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

Задача: 919. Complete Binary Tree Inserter
Сложность: medium

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

Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.

Пример:

Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

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

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

2⃣Вставка: Добавление нового узла в первое доступное место слева направо.

3⃣Возвращение корня: Просто возвращает корневой узел.

😎 Решение:

using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class CBTInserter {
    private TreeNode root;
    private Queue<TreeNode> deque;

    public CBTInserter(TreeNode root) {
        this.root = root;
        this.deque = new Queue<TreeNode>();
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.Count > 0) {
            TreeNode node = queue.Dequeue();
            if (node.left == null || node.right == null) {
                deque.Enqueue(node);
            }
            if (node.left != null) {
                queue.Enqueue(node.left);
            }
            if (node.right != null) {
                queue.Enqueue(node.right);
            }
        }
    }

    public int Insert(int v) {
        TreeNode node = deque.Peek();
        TreeNode newNode = new TreeNode(v);
        if (node.left == null) {
            node.left = newNode;
        } else {
            node.right = newNode;
            deque.Dequeue();
        }
        deque.Enqueue(newNode);
        return node.val;
    }

    public TreeNode Get_root() {
        return root;
    }
}

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

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

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

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

3⃣Рекурсивный вызов для левого и правого дочерних узлов:
Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎 Решение:

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

class Solution {
    private var maxLength = 0

    fun longestZigZag(root: TreeNode?): Int {
        dfs(root, true, 0)
        dfs(root, false, 0)
        return maxLength
    }

    private fun dfs(node: TreeNode?, isLeft: Boolean, length: Int) {
        if (node == null) return
        maxLength = kotlin.math.max(maxLength, length)
        if (isLeft) {
            dfs(node.left, false, length + 1)
            dfs(node.right, true, 1)
        } else {
            dfs(node.right, true, length + 1)
            dfs(node.left, false, 1)
        }
    }
}

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

Задача: 328. Odd Even Linked List
Сложность: medium

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

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

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

Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n).

Пример:

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

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

1⃣Инициализация указателей:
Создайте указатели odd и even для работы с нечетными и четными узлами, соответственно. Инициализируйте odd началом списка head, а even — следующим узлом head.next. Также создайте указатель evenHead для сохранения начала четного списка.

2⃣Разделение списка:
Используйте цикл для прохождения списка, перенаправляя нечетные узлы в oddList, а четные узлы в evenList. Обновляйте указатели odd и even в процессе итерации.

3⃣Соединение списков:
После окончания цикла соедините конец нечетного списка с началом четного списка, используя указатель evenHead.

😎 Решение:

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

class Solution {
    fun oddEvenList(head: ListNode?): ListNode? {
        if (head == null) return null
        var odd = head
        var even = head.next
        val evenHead = even
        
        while (even != null && even.next != null) {
            odd?.next = even.next
            odd = odd?.next
            even.next = odd?.next
            even = even.next
        }
        odd?.next = evenHead
        return head
    }
}

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

Задача: 234. Palindrome Linked List
Сложность: easy

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

Пример:

Input: head = [1,2,2,1]
Output: true

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

1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null.

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

3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата.

😎 Решение:

class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        val vals = ArrayList<Int>()
        var currentNode = head

        while (currentNode != null) {
            vals.add(currentNode.`val`)
            currentNode = currentNode.next
        }

        var front = 0
        var back = vals.size - 1
        while (front < back) {
            if (vals[front] != vals[back]) {
                return false
            }
            front++
            back--
        }
        return true
    }
}

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

Задача: 1342. Number of Steps to Reduce a Number to Zero
Сложность: easy

Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля.

На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1.

Пример:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

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

1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2.

2⃣Если число нечетное (number % 2 == 1), вычтите из него 1.

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

😎 Решение:

fun numberOfSteps(num: Int): Int {
    var num = num
    var steps = 0
    while (num != 0) {
        if (num % 2 == 0) {
            num /= 2
        } else {
            num -= 1
        }
        steps++
    }
    return steps
}

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

Задача: 950. Reveal Cards In Increasing Order
Сложность: medium

Вам дана колода целочисленных массивов. Имеется колода карт, в которой каждая карта имеет уникальное целое число. Целое число на i-й карте - deck[i]. Вы можете упорядочить колоду в любом порядке. Изначально все карты в одной колоде лежат лицевой стороной вниз (нераскрытыми). Вы будете выполнять следующие действия несколько раз, пока все карты не будут раскрыты: возьмите верхнюю карту колоды, раскройте ее и выньте из колоды. Если в колоде еще есть карты, положите следующую верхнюю карту колоды на дно колоды. Если еще есть нераскрытые карты, вернитесь к шагу 1. В противном случае остановитесь. Верните порядок колоды, при котором карты раскрываются в порядке возрастания. Обратите внимание, что первая запись в ответе считается верхом колоды.

Пример:

Input: deck = [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]

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

1⃣Создать индексы карт в порядке, в котором они будут раскрываться.

2⃣Отсортировать колоду карт по возрастанию.

3⃣Заполнить результат раскрытия карт по ранее созданным индексам.

😎 Решение:

class Solution {
    fun deckRevealedIncreasing(deck: IntArray): IntArray {
        val n = deck.size
        val index = ArrayDeque<Int>().apply { addAll(deck.indices) }
        val result = IntArray(n)
        val sortedDeck = deck.sorted()
        
        for (card in sortedDeck) {
            result[index.removeFirst()] = card
            if (index.isNotEmpty()) {
                index.addLast(index.removeFirst())
            }
        }
        
        return result
    }
}

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

Задача: 26. Remove Duplicates from Sorted Array
Сложность: easy

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

Пример:

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

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

1⃣ Если массив пуст, возвращаем 0.

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

3⃣ Проходим по массиву и, если встречаем новое значение, записываем его на lastIdx и увеличиваем счетчик.

😎 Решение:

fun removeDuplicates(nums: IntArray): Int {
    if (nums.isEmpty()) return 0

    var lastIdx = 1
    var curVal = nums[0]

    for (i in 1 until nums.size) {
        if (nums[i] > curVal) {
            curVal = nums[i]
            nums[lastIdx] = nums[i]
            lastIdx++
        }
    }
    
    return lastIdx
}

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