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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

Задача: 933. Number of Recent Calls
Сложность: easy

У вас есть класс RecentCounter, который подсчитывает количество последних запросов за определенный промежуток времени. Реализуйте класс RecentCounter: RecentCounter() Инициализирует счетчик нулем последних запросов. int ping(int t) Добавляет новый запрос в момент времени t, где t представляет собой некоторое время в миллисекундах, и возвращает количество запросов, произошедших за последние 3000 миллисекунд (включая новый запрос). Точнее, возвращается количество запросов, произошедших в диапазоне [t - 3000, t]. Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов.

Пример:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

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

1⃣Создать класс RecentCounter с конструктором для инициализации пустой очереди.

2⃣Реализовать метод ping, который принимает время запроса t:
Добавить t в очередь.
Удалить из очереди все запросы, которые не попадают в диапазон [t - 3000, t].

3⃣Вернуть размер очереди.

😎 Решение:

class RecentCounter {
    private val q: ArrayDeque<Int> = ArrayDeque()
    
    fun ping(t: Int): Int {
        q.addLast(t)
        while (q.first() < t - 3000) {
            q.removeFirst()
        }
        return q.size
    }
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 93. Restore IP Addresses
Сложность: medium

Дана строка s, содержащая только цифры. Верните все возможные корректные IP-адреса, которые можно получить из s, вставляя три точки. IP-адрес состоит из четырёх чисел (от 0 до 255), разделённых точками. Нельзя использовать ведущие нули (например, "01" — недопустимо).

Пример:

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 fun isValid(s: String, start: Int, length: Int): Boolean {
        if (length == 1) return true
        if (s[start] == '0') return false
        if (length > 3) return false
        val num = s.substring(start, start + length).toInt()
        return num <= 255
    }

    private fun helper(s: String, startIndex: Int, dots: MutableList<Int>, ans: MutableList<String>) {
        val remainingLength = s.length - startIndex
        val remainingNumberOfIntegers = 4 - dots.size
        if (remainingLength > remainingNumberOfIntegers * 3 || remainingLength < remainingNumberOfIntegers) {
            return
        }
        if (dots.size == 3) {
            if (isValid(s, startIndex, remainingLength)) {
                var temp = ""
                var last = 0
                for (dot in dots) {
                    temp += s.substring(last, last + dot) + "."
                    last += dot
                }
                temp += s.substring(startIndex)
                ans.add(temp)
            }
            return
        }
        for (curPos in 1..minOf(3, remainingLength)) {
            dots.add(curPos)
            if (isValid(s, startIndex, curPos)) {
                helper(s, startIndex + curPos, dots, ans)
            }
            dots.removeAt(dots.size - 1)
        }
    }

    fun restoreIpAddresses(s: String): List<String> {
        val answer = mutableListOf<String>()
        helper(s, 0, mutableListOf(), answer)
        return answer
    }
}

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

Задача: 780. Reaching Points
Сложность: hard

Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false.

Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (x + y, y).

Пример:

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

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

1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}.

2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно.

3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy.

😎 Решение:

class Solution {
    fun reachingPoints(sx: Int, sy: Int, tx: Int, ty: Int): Boolean {
        var tx = tx
        var ty = ty
        while (tx >= sx && ty >= sy) {
            if (sx == tx && sy == ty) return true
            if (tx > ty) {
                tx -= ty
            } else {
                ty -= tx
            }
        }
        return false
    }
}

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

Задача: 1189. Maximum Number of Balloons
Сложность: easy

Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon".

Каждый символ строки text можно использовать не более одного раза. Верните максимальное количество экземпляров, которые можно сформировать.

Пример:

Input: text = "nlaebolko"
Output: 1

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

1⃣Подсчитайте количество появлений каждого символа 'b', 'a', 'l', 'o', 'n' в строке text.

2⃣Вычислите потенциал для каждого символа: для 'b' и 'a' потенциал равен количеству их появлений, для 'l' и 'o' потенциал равен количеству их появлений, деленному на 2, а для 'n' потенциал равен количеству его появлений.

3⃣Найдите символ с наименьшим потенциалом среди 'b', 'a', 'l', 'o', 'n', который ограничивает количество возможных слов "balloon", и верните это значение.

😎 Решение:

class Solution {
    fun maxNumberOfBalloons(text: String): Int {
        var bCount = 0
        var aCount = 0
        var lCount = 0
        var oCount = 0
        var nCount = 0

        for (char in text) {
            when (char) {
                'b' -> bCount++
                'a' -> aCount++
                'l' -> lCount++
                'o' -> oCount++
                'n' -> nCount++
            }
        }

        lCount /= 2
        oCount /= 2

        return minOf(bCount, aCount, lCount, oCount, nCount)
    }
}

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

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

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