Задача: 658. Find K Closest Elements
Сложность: easy

Дан отсортированный массив целых чисел arr, два целых числа k и x. Верните k ближайших к x целых чисел в массиве. Результат также должен быть отсортирован в порядке возрастания.

Целое число a ближе к x, чем целое число b, если:

|a - x| < |b - x|, или
|a - x| == |b - x| и a < b.

Пример:

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

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

1⃣Бинарный поиск:
Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска.

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

3⃣Сортировка:
Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован).

😎 Решение:

class Solution {
    fun findClosestElements(arr: List<Int>, k: Int, x: Int): List<Int> {
        var left = 0
        var right = arr.size - k

        while (left < right) {
            val mid = (left + right) / 2
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1
            } else {
                right = mid
            }
        }

        return arr.subList(left, left + k)
    }
}

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

Задача: 786. K-th Smallest Prime Fraction
Сложность: medium

Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k.

Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j].

Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

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

1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей.

2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью.

3⃣Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби.

😎 Решение:

import java.util.PriorityQueue

class Solution {
    fun kthSmallestPrimeFraction(arr: IntArray, k: Int): IntArray {
        val pq = PriorityQueue(compareBy<Pair<Double, IntArray>> { it.first })

        for (i in 0 until arr.size - 1) {
            pq.add(Pair(arr[i].toDouble() / arr[arr.size - 1], intArrayOf(i, arr.size - 1)))
        }

        repeat(k - 1) {
            val (_, indices) = pq.poll()
            val (numeratorIndex, denominatorIndex) = indices
            val newDenominatorIndex = denominatorIndex - 1
            if (newDenominatorIndex > numeratorIndex) {
                pq.add(Pair(arr[numeratorIndex].toDouble() / arr[newDenominatorIndex], intArrayOf(numeratorIndex, newDenominatorIndex)))
            }
        }

        val (_, result) = pq.poll()
        return intArrayOf(arr[result[0]], arr[result[1]])
    }
}

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

Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

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

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

😎 Решение:

class Solution {
    fun sortItems(n: Int, m: Int, group: IntArray, beforeItems: List<List<Int>>): IntArray {
        var groupId = m
        for (i in 0 until n) if (group[i] == -1) group[i] = groupId++

        val itemGraph = mutableMapOf<Int, MutableList<Int>>()
        val groupGraph = mutableMapOf<Int, MutableList<Int>>()
        val itemIndegree = IntArray(n)
        val groupIndegree = IntArray(groupId)
        for (i in 0 until n) itemGraph[i] = mutableListOf()
        for (i in 0 until groupId) groupGraph[i] = mutableListOf()

        for (curr in 0 until n) {
            for (prev in beforeItems[curr]) {
                itemGraph[prev]!!.add(curr)
                itemIndegree[curr]++
                if (group[curr] != group[prev]) {
                    groupGraph[group[prev]]!!.add(group[curr])
                    groupIndegree[group[curr]]++
                }
            }
        }

        val itemOrder = topologicalSort(itemGraph, itemIndegree)
        val groupOrder = topologicalSort(groupGraph, groupIndegree)
        if (itemOrder.isEmpty() || groupOrder.isEmpty()) return intArrayOf()

        val orderedGroups = mutableMapOf<Int, MutableList<Int>>()
        for (item in itemOrder) orderedGroups.computeIfAbsent(group[item]) { mutableListOf() }.add(item)

        val answerList = mutableListOf<Int>()
        for (groupIndex in groupOrder) answerList.addAll(orderedGroups.getOrDefault(groupIndex, mutableListOf()))

        return answerList.toIntArray()
    }

    private fun topologicalSort(graph: Map<Int, List<Int>>, indegree: IntArray): List<Int> {
        val visited = mutableListOf<Int>()
        val stack = ArrayDeque<Int>()
        for (key in graph.keys) if (indegree[key] == 0) stack.add(key)

        while (stack.isNotEmpty()) {
            val curr = stack.removeLast()
            visited.add(curr)
            for (next in graph[curr]!!) if (--indegree[next] == 0) stack.add(next)
        }

        return if (visited.size == graph.size) visited else emptyList()
    }
}

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

Задача: 1235. Maximum Profit in Job Scheduling
Сложность: hard

У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X.

Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

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

2⃣Использование динамического программирования с двоичным поиском:
Используем массив dp, где dp[i] будет хранить максимальную прибыль, которую можно получить, рассматривая первые i заданий.

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

😎 Решение:

class Solution {
    fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
        val jobs = startTime.indices.map { Triple(endTime[it], startTime[it], profit[it]) }.sortedBy { it.first }

        val dp = mutableListOf(Pair(0, 0))

        for ((e, s, p) in jobs) {
            val i = dp.binarySearch { if (it.first <= s) -1 else 1 }
            val newProfit = dp[if (i < 0) -i - 2 else i].second + p
            if (newProfit > dp.last().second) {
                dp.add(Pair(e, newProfit))
            }
        }

        return dp.last().second
    }
}

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

Задача: 81. Search in Rotated Sorted Array II
Сложность: medium

В массиве целых чисел nums, отсортированном в неубывающем порядке (не обязательно содержащем уникальные значения), произведена ротация в неизвестном индексе поворота k (0 <= k < nums.length). В результате массив принимает вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (нумерация с 0). Например, массив [0,1,2,4,4,4,5,6,6,7] может быть повернут в индексе 5 и превратиться в [4,5,6,6,7,0,1,2,4,4].

Для данного массива nums после ротации и целого числа target необходимо вернуть true, если target присутствует в nums, и false в противном случае.

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

Пример:

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

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

1⃣Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска.

2⃣Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске:
Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end].
Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid).
Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска.
Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска.

3⃣Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно.

😎 Решение:

class Solution {
    fun search(nums: IntArray, target: Int): Boolean {
        val n = nums.size
        if (n == 0) return false
        var end = n - 1
        var start = 0

        while (start <= end) {
            val mid = start + (end - start) / 2
            if (nums[mid] == target) return true

            if (!isBinarySearchHelpful(nums, start, nums[mid])) {
                start += 1
                continue
            }

            val pivotArray = existsInFirst(nums, start, nums[mid])
            val targetArray = existsInFirst(nums, start, target)

            if (pivotArray xor targetArray) {
                if (pivotArray) {
                    start = mid + 1
                } else {
                    end = mid - 1
                }
            } else {
                if (nums[mid] < target) {
                    start = mid + 1
                } else {
                    end = mid - 1
                }
            }
        }
        return false
    }

    private fun isBinarySearchHelpful(nums: IntArray, start: Int, element: Int): Boolean {
        return nums[start] != element
    }

    private fun existsInFirst(nums: IntArray, start: Int, element: Int): Boolean {
        return nums[start] <= element
    }
}

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

Задача: 1134. Armstrong Number
Сложность: easy

Дано целое число n, верните true, если и только если оно является числом Армстронга.

k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.

Пример:

Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.

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

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

2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n.
Инициализируйте переменную result для хранения результата.
Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру.

3⃣Верните true, если результат равен исходному числу n.

😎 Решение:

class Solution {
    fun getSumOfKthPowerOfDigits(n: Int, k: Int): Int {
        var result = 0
        var number = n
        while (number != 0) {
            val digit = number % 10
            result += Math.pow(digit.toDouble(), k.toDouble()).toInt()
            number /= 10
        }
        return result
    }

    fun isArmstrong(n: Int): Boolean {
        val length = n.toString().length
        return getSumOfKthPowerOfDigits(n, length) == n
    }
}

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

Задача: 155. Min Stack
Сложность: medium

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

Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.

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

Пример:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

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

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

2⃣Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.

3⃣Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.

😎 Решение:

class MinStack() {
    private val stack = mutableListOf<Pair<Int, Int>>()

    fun push(x: Int) {
        val currentMin = stack.lastOrNull()?.second ?: x
        stack.add(Pair(x, kotlin.math.min(x, currentMin)))
    }

    fun pop() {
        if (stack.isNotEmpty()) {
            stack.removeAt(stack.lastIndex)
        }
    }

    fun top(): Int? {
        return stack.lastOrNull()?.first
    }

    fun getMin(): Int? {
        return stack.lastOrNull()?.second
    }
}

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

Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

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

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

Задача: 926. Flip String to Monotone Increasing
Сложность: medium

Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.

Пример:

Input: s = "00110"
Output: 1

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

1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0).

2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1).
Пройти по строке и заполнить массивы left и right.

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

😎 Решение:

class Solution {
    fun minFlipsMonoIncr(s: String): Int {
        val n = s.length
        val left = IntArray(n + 1)
        val right = IntArray(n + 1)
        
        for (i in 0 until n) {
            left[i + 1] = left[i] + if (s[i] == '1') 1 else 0
        }
        
        for (i in n - 1 downTo 0) {
            right[i] = right[i + 1] + if (s[i] == '0') 1 else 0
        }
        
        var result = Int.MAX_VALUE
        for (i in 0..n) {
            result = minOf(result, left[i] + right[i])
        }
        return result
    }
}

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

Задача: 1302. Deepest Leaves Sum
Сложность: medium

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

Пример:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

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

1⃣Поместите корень в стек.

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

3⃣Верните deepest_sum.

😎 Решение:

class Solution {
    fun deepestLeavesSum(root: TreeNode?): Int {
        var deepestSum = 0
        var depth = 0
        val stack = ArrayDeque<Pair<TreeNode, Int>>()
        stack.push(Pair(root!!, 0))

        while (stack.isNotEmpty()) {
            val (node, currDepth) = stack.pop()

            if (node.left == null && node.right == null) {
                if (depth < currDepth) {
                    deepestSum = node.`val`
                    depth = currDepth
                } else if (depth == currDepth) {
                    deepestSum += node.`val`
                }
            } else {
                node.right?.let { stack.push(Pair(it, currDepth + 1)) }
                node.left?.let { stack.push(Pair(it, currDepth + 1)) }
            }
        }
        return deepestSum
    }
}

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

Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard

Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.

Пример:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

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

1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.

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

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

😎 Решение:

class Solution {
    fun minPushBox(grid: Array<CharArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
        
        fun isValid(x: Int, y: Int) = x in 0 until m && y in 0 until n && grid[x][y] != '#'
        
        var player = intArrayOf(0, 0)
        var box = intArrayOf(0, 0)
        var target = intArrayOf(0, 0)
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                when (grid[i][j]) {
                    'S' -> player = intArrayOf(i, j)
                    'B' -> box = intArrayOf(i, j)
                    'T' -> target = intArrayOf(i, j)
                }
            }
        }
        
        val queue = ArrayDeque<IntArray>()
        val visited = mutableSetOf<String>()
        
        queue.addLast(intArrayOf(player[0], player[1], box[0], box[1], 0))
        visited.add("${player[0]},${player[1]},${box[0]},${box[1]}")
        
        while (queue.isNotEmpty()) {
            val (px, py, bx, by, pushes) = queue.removeFirst()
            if (bx == target[0] && by == target[1]) {
                return pushes
            }
            for ((dx, dy) in directions) {
                val npx = px + dx
                val npy = py + dy
                if (isValid(npx, npy)) {
                    if (npx == bx && npy == by) {
                        val nbx = bx + dx
                        val nby = by + dy
                        if (isValid(nbx, nby) && visited.add("$npx,$npy,$nbx,$nby")) {
                            queue.addLast(intArrayOf(npx, npy, nbx, nby, pushes + 1))
                        }
                    } else if (visited.add("$npx,$npy,$bx,$by")) {
                        queue.addLast(intArrayOf(npx, npy, bx, by, pushes))
                    }
                }
            }
        }
        
        return -1
    }
}

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

Задача: 211. Design Add and Search Words Data Structure
Сложность: medium

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

Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

1⃣Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.

2⃣Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3⃣Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

class TrieNode {
    val children: MutableMap<Char, TrieNode> = HashMap()
    var isWord: Boolean = false
}

class WordDictionary {
    private val root: TrieNode = TrieNode()

    fun addWord(word: String) {
        var node = root
        for (ch in word) {
            node = node.children.computeIfAbsent(ch) { TrieNode() }
        }
        node.isWord = true
    }

    private fun searchInNode(word: String, node: TrieNode): Boolean {
        var node = node
        for (i in word.indices) {
            val ch = word[i]
            if (!node.children.containsKey(ch)) {
                if (ch == '.') {
                    for (child in node.children.values) {
                        if (searchInNode(word.substring(i + 1), child)) {
                            return true
                        }
                    }
                }
                return false
            } else {
                node = node.children[ch]!!
            }
        }
        return node.isWord
    }

    fun search(word: String): Boolean {
        return searchInNode(word, root)
    }
}

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

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

😎 Решение:

class Solution {
    fun minMalwareSpread(graph: Array<IntArray>, initial: IntArray): Int {
        val n = graph.size
        val visited = mutableSetOf<Int>()
        val components = mutableListOf<MutableSet<Int>>()
        
        fun dfs(node: Int) {
            val stack = mutableListOf(node)
            val component = mutableSetOf<Int>()
            while (stack.isNotEmpty()) {
                val u = stack.removeAt(stack.lastIndex)
                if (u !in visited) {
                    visited.add(u)
                    component.add(u)
                    for (v in 0 until n) {
                        if (graph[u][v] == 1 && v !in visited) {
                            stack.add(v)
                        }
                    }
                }
            }
            components.add(component)
        }
        
        for (i in 0 until n) {
            if (i !in visited) {
                dfs(i)
            }
        }
        
        val infectedInComponent = IntArray(components.size)
        val nodeToComponent = IntArray(n) { -1 }
        
        for ((idx, component) in components.withIndex()) {
            for (node in component) {
                nodeToComponent[node] = idx
                if (node in initial) {
                    infectedInComponent[idx]++
                }
            }
        }
        
        var minInfected = Int.MAX_VALUE
        var resultNode = initial.minOrNull()!!
        
        for (node in initial) {
            val componentIdx = nodeToComponent[node]
            if (infectedInComponent[componentIdx] == 1) {
                val componentSize = components[componentIdx].size
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize
                    resultNode = node
                }
            }
        }
        
        return resultNode
    }
}

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

Задача: 346. Moving Average from Data Stream
Сложность: easy

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

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

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

1⃣Инициализация:
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.

2⃣Добавление нового значения:
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.

3⃣Вычисление скользящего среднего:
Возвращайте текущее скользящее среднее как сумму значений в окне, деленную на количество значений в окне.

😎 Решение:

class MovingAverage(size: Int) {
    private val size = size
    private val queue: ArrayDeque<Int> = ArrayDeque()
    private var sum = 0
    
    fun next(`val`: Int): Double {
        queue.addLast(`val`)
        sum += `val`
        if (queue.size > size) {
            sum -= queue.removeFirst()
        }
        return sum.toDouble() / queue.size
    }
}

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

Задача: 625. Minimum Factorization
Сложность: medium

Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.

Пример:

Input: num = 48
Output: 68

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

1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.

2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.

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

😎 Решение:

fun smallestFactorization(num: Int): Int {
    if (num == 1) return 1
    
    var num = num
    val factors = mutableListOf<Int>()
    
    for (i in 9 downTo 2) {
        while (num % i == 0) {
            factors.add(i)
            num /= i
        }
    }
    
    if (num > 1) return 0
    
    var result: Long = 0
    for (factor in factors.asReversed()) {
        result = result * 10 + factor
        if (result > Int.MAX_VALUE) return 0
    }
    
    return result.toInt()
}

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

Задача: 900. RLE Iterator
Сложность: medium

Для кодирования последовательности целых чисел мы можем использовать кодирование по длине строки (т. е. RLE). В кодированном по длине пробега массиве четной длины (с индексацией 0) для всех четных i значение encoding[i] говорит нам о том, сколько раз неотрицательное целое значение encoding[i + 1] повторяется в последовательности.

Например, последовательность arr = [8,8,8,5,5] может быть закодирована как encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] и encoding = [2,8,1,8,2,5] также являются допустимыми RLE для arr.
Задав кодированный по длине пробега массив, разработайте итератор для его итерации. Реализуйте класс RLEIterator: RLEIterator(int[] encoded) Инициализирует объект с кодированным массивом encoded. int next(int n) Исчерпывает следующие n элементов и возвращает последний исчерпанный таким образом элемент. Если не осталось элементов для исчерпания, возвращает -1.

Пример:

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

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

1⃣Инициализировать итератор с закодированным массивом и индексом, указывающим на текущую позицию.

2⃣При вызове метода next(n), уменьшить текущий счетчик на n или перейти к следующему числу, если текущий счетчик равен нулю.

3⃣Возвращать текущий элемент или -1, если все элементы исчерпаны.

😎 Решение:

class RLEIterator(private val encoding: IntArray) {
    private var index = 0

    fun next(n: Int): Int {
        var n = n
        while (index < encoding.size) {
            if (n > encoding[index]) {
                n -= encoding[index]
                index += 2
            } else {
                encoding[index] -= n
                return encoding[index + 1]
            }
        }
        return -1
    }
}

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

Задача: 848. Shifting Letters
Сложность: medium

Вам дана строка s из строчных букв английского алфавита и целочисленный массив shifts такой же длины.

Назовем shift() буквы следующей буквой в алфавите (с переходом так, что 'z' становится 'a').
Например, shift('a') = 'b', shift('t') = 'u', и shift('z') = 'a'.
Теперь для каждого shifts[i] = x мы хотим сдвинуть первые i + 1 букв строки s на x раз.

Верните итоговую строку после применения всех таких сдвигов к s.

Пример:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

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

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

2⃣Пройдите по строке s и примените вычисленные сдвиги к каждому символу, начиная с первого и уменьшая количество сдвигов на текущем шаге.

3⃣Постройте и верните итоговую строку после всех сдвигов.

😎 Решение:

class Solution {
    fun shiftingLetters(s: String, shifts: IntArray): String {
        val sArray = s.toCharArray()
        var totalShifts = shifts.sum() % 26
        
        for (i in sArray.indices) {
            val newCharValue = (sArray[i] - 'a' + totalShifts) % 26
            sArray[i] = ('a' + newCharValue)
            totalShifts = (totalShifts - shifts[i]) % 26
        }
        
        return String(sArray)
    }
}

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

Задача: 353. Design Snake Game
Сложность: medium

Разработайте игру "Змейка", которая играется на устройстве с экраном размером height x width. Поиграйте в игру онлайн, если вы не знакомы с ней.

Змейка изначально находится в верхнем левом углу (0, 0) с длиной в 1 единицу.
Вам дан массив food, где food[i] = (ri, ci) представляет собой строку и столбец позиции пищи, которую змейка может съесть. Когда змейка съедает кусочек пищи, ее длина и очки игры увеличиваются на 1.
Каждый кусочек пищи появляется по очереди на экране, то есть второй кусочек пищи не появится, пока змейка не съест первый кусочек пищи.
Когда кусочек пищи появляется на экране, гарантируется, что он не появится на блоке, занятом змейкой.
Игра заканчивается, если змейка выходит за пределы экрана (врезается в стену) или если ее голова занимает пространство, которое занимает ее тело после движения (например, змейка длиной 4 не может врезаться в себя).

Реализуйте класс SnakeGame:
SnakeGame(int width, int height, int[][] food) Инициализирует объект с экраном размером height x width и позициями пищи.
int move(String direction) Возвращает счет игры после применения одного движения змейки в направлении. Если игра окончена, верните -1.

Пример:

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

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

1⃣Инициализируйте объекты игры, такие как экран, еда, положение змейки и счетчик, в конструкторе.

2⃣Реализуйте функцию для вычисления нового положения головы змейки на основе направления движения.

3⃣Обновите положение змейки и проверьте условия завершения игры. Верните текущий счет или -1, если игра закончена.

😎 Решение:

class SnakeGame(width: Int, height: Int, food: Array<IntArray>) {
    private val width = width
    private val height = height
    private val food = food
    private var score = 0
    private val snake = ArrayDeque(listOf(intArrayOf(0, 0)))
    private val snakeSet = mutableSetOf(Pair(0, 0))
    private var foodIndex = 0

    fun move(direction: String): Int {
        val head = snake.first()
        val newHead = head.copyOf()
        when (direction) {
            "U" -> newHead[0] -= 1
            "D" -> newHead[0] += 1
            "L" -> newHead[1] -= 1
            "R" -> newHead[1] += 1
        }

        if (newHead[0] < 0 || newHead[0] >= height || newHead[1] < 0 || newHead[1] >= width) {
            return -1
        }

        val newHeadPair = Pair(newHead[0], newHead[1])
        if (snakeSet.contains(newHeadPair) && newHeadPair != Pair(snake.last()[0], snake.last()[1])) {
            return -1
        }

        if (foodIndex < food.size && newHead[0] == food[foodIndex][0] && newHead[1] == food[foodIndex][1]) {
            foodIndex++
        } else {
            val tail = snake.removeLast()
            snakeSet.remove(Pair(tail[0], tail[1]))
        }

        snake.addFirst(newHead)
        snakeSet.add(newHeadPair)

        return snake.size - 1
    }
}

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