Kotlin | LeetCode

Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy

Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.

Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

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

1⃣Создать словарь для подсчета частоты каждого числа в массиве deck.

2⃣Найти наибольший общий делитель (НОД) всех частот.

3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы.

😎 Решение:

class Solution {
    fun hasGroupsSizeX(deck: IntArray): Boolean {
        val count = deck.groupBy { it }.mapValues { it.value.size }
        val freqValues = count.values.toIntArray()
        val g = freqValues.reduce(::gcd)
        return g > 1
    }

    private fun gcd(a: Int, b: Int): Int {
        var a = a
        var b = b
        while (b != 0) {
            val temp = a % b
            a = b
            b = temp
        }
        return a
    }
}

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

Задача: 785. Is Graph Bipartite?
Сложность: medium

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).
Нет параллельных ребер (graph[u] не содержит дублирующихся значений).
Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).
Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.
Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

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

1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

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

3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎 Решение:

class Solution {
    fun isBipartite(graph: Array<IntArray>): Boolean {
        val color = mutableMapOf<Int, Int>()
        for (node in graph.indices) {
            if (node !in color) {
                val stack = mutableListOf(node)
                color[node] = 0
                while (stack.isNotEmpty()) {
                    val node = stack.removeAt(stack.size - 1)
                    for (nei in graph[node]) {
                        if (nei !in color) {
                            stack.add(nei)
                            color[nei] = color[node]!! xor 1
                        } else if (color[nei] == color[node]) {
                            return false
                        }
                    }
                }
            }
        }
        return true
    }
}

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

Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy

Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).

Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, 
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

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

1⃣Инициализируйте biggest = 0 и secondBiggest = 0.

2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.

3⃣Верните (biggest - 1) * (secondBiggest - 1).

😎 Решение:

class Solution {
    fun maxProduct(nums: IntArray): Int {
        var biggest = 0
        var secondBiggest = 0
        for (num in nums) {
            if (num > biggest) {
                secondBiggest = biggest
                biggest = num
            } else if (num > secondBiggest) {
                secondBiggest = num
            }
        }
        return (biggest - 1) * (secondBiggest - 1)
    }
}

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

Задача: 994. Rotting Oranges
Сложность: medium

Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:

0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.

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

Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

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

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

3⃣Проверка оставшихся свежих апельсинов:
Если после завершения BFS все еще остаются свежие апельсины, верните -1.

😎 Решение:

class Solution {
    fun orangesRotting(grid: Array<IntArray>): Int {
        val queue = ArrayDeque<Pair<Int, Int>>()
        var freshCount = 0
        val directions = arrayOf(Pair(0, 1), Pair(1, 0), Pair(0, -1), Pair(-1, 0))
        
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                when (grid[i][j]) {
                    2 -> queue.add(Pair(i, j))
                    1 -> freshCount++
                }
            }
        }
        
        if (freshCount == 0) return 0
        
        var minutes = 0
        while (queue.isNotEmpty()) {
            repeat(queue.size) {
                val (i, j) = queue.removeFirst()
                for ((di, dj) in directions) {
                    val ni = i + di
                    val nj = j + dj
                    if (ni in grid.indices && nj in grid[0].indices && grid[ni][nj] == 1) {
                        grid[ni][nj] = 2
                        freshCount--
                        queue.add(Pair(ni, nj))
                    }
                }
            }
            if (queue.isNotEmpty()) {
                minutes++
            }
        }
        
        return if (freshCount == 0) minutes else -1
    }
}

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

Задача: 988. Smallest String Starting From Leaf
Сложность: medium

Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.

Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.

Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.

Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.

Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

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

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

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

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

😎 Решение:

class Solution {
    var ans = "~"
    
    fun smallestFromLeaf(root: TreeNode?): String {
        dfs(root, "")
        return ans
    }
    
    private fun dfs(node: TreeNode?, path: String) {
        if (node == null) return
        val currentPath = (node.`val` + 'a'.toInt()).toChar() + path
        if (node.left == null && node.right == null) {
            ans = minOf(ans, currentPath)
        }
        dfs(node.left, currentPath)
        dfs(node.right, currentPath)
    }
}

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

Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium

В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.

Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.

Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.

Пример:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

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

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

2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.

3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.

😎 Решение:

class UnionFind(n: Int) {
    private val parent = IntArray(n) { it }
    private val rank = IntArray(n) { 1 }

    fun find(x: Int): Int {
        if (parent[x] != x) {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    fun union(x: Int, y: Int): Boolean {
        val rootX = find(x)
        val rootY = find(y)
        
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY
            } else {
                parent[rootY] = rootX
                rank[rootX] += 1
            }
            return true
        }
        return false
    }
}

class Solution {
    fun earliestAcq(logs: Array<IntArray>, n: Int): Int {
        logs.sortBy { it[0] }
        val uf = UnionFind(n)
        var groupCount = n
        
        for (log in logs) {
            val (timestamp, friendA, friendB) = log
            if (uf.union(friendA, friendB)) {
                groupCount--
            }
            if (groupCount == 1) {
                return timestamp
            }
        }
        
        return -1
    }
}

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

Задача: 1347. Minimum Number of Steps to Make Two Strings Anagram
Сложность: medium

Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом.

Вернуть минимальное количество шагов, чтобы сделать t анаграммой строки s.

Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке.

Пример:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

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

1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count.

2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count.

3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s.

😎 Решение:

class Solution {
    fun minSteps(s: String, t: String): Int {
        val count = IntArray(26)
        
        for (i in s.indices) {
            count[t[i] - 'a']++
            count[s[i] - 'a']--
        }

        var ans = 0
        for (i in 0..25) {
            ans += maxOf(0, count[i])
        }

        return ans
    }
}

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

Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

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

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

class MaxStack {

    private val stack = mutableListOf<Int>()
    private val maxStack = mutableListOf<Int>()

    fun push(x: Int) {
        stack.add(x)
        if (maxStack.isEmpty() || x >= maxStack.last()) {
            maxStack.add(x)
        }
    }

    fun pop(): Int {
        val x = stack.removeAt(stack.size - 1)
        if (x == maxStack.last()) {
            maxStack.removeAt(maxStack.size - 1)
        }
        return x
    }

    fun top(): Int {
        return stack.last()
    }

    fun peekMax(): Int {
        return maxStack.last()
    }

    fun popMax(): Int {
        val maxVal = maxStack.removeAt(maxStack.size - 1)
        val buffer = mutableListOf<Int>()
        while (stack.last() != maxVal) {
            buffer.add(stack.removeAt(stack.size - 1))
        }
        stack.removeAt(stack.size - 1)
        while (buffer.isNotEmpty()) {
            push(buffer.removeAt(buffer.size - 1))
        }
        return maxVal
    }
}       }
        stack.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return maxVal;
    }

private:
    stack<int> stack;
    stack<int> maxStack;
};

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

Задача: 38. Count and Say
Сложность medium

Последовательность "считай и скажи" определяется рекурсивно:
- countAndSay(1) = "1"
- countAndSay(n) — это кодирование длин серий (RLE) из countAndSay(n - 1).

Пример:

Input: n = 4  
Output: "1211"  

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

1⃣Начинаем с "1" и итеративно строим последовательность до n.

2⃣Используем Regex для поиска повторяющихся символов ((.)\1*).

3⃣Формируем новую строку, записывая длину каждой группы символов и сам символ.

😎 Решение:

class Solution {
    fun countAndSay(n: Int): String {
        var s = "1"
        for (i in 2..n) {
            var t = ""
            val regex = Regex("(.)\\1*")
            regex.findAll(s).forEach { match ->
                t += "${match.value.length}${match.value[0]}"
            }
            s = t
        }
        return s
    }
}

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

Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium

Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.

Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:

Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.

Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].

Пример:

Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

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

1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].

2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.

3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.

😎 Решение:

class Solution {
    var flipped = mutableListOf<Int>()
    var index = 0
    lateinit var voyage: IntArray

    fun flipMatchVoyage(root: TreeNode?, voyage: IntArray): List<Int> {
        flipped = mutableListOf()
        index = 0
        this.voyage = voyage

        dfs(root)
        if (flipped.isNotEmpty() && flipped[0] == -1) {
            return listOf(-1)
        }

        return flipped
    }

    fun dfs(node: TreeNode?) {
        if (node != null) {
            if (node.`val` != voyage[index++]) {
                flipped.clear()
                flipped.add(-1)
                return
            }

            if (index < voyage.size && node.left != null && node.left.`val` != voyage[index]) {
                flipped.add(node.`val`)
                dfs(node.right)
                dfs(node.left)
            } else {
                dfs(node.left)
                dfs(node.right)
            }
        }
    }
}

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

Задача: 827. Making A Large Island
Сложность: hard

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

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

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

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

😎 Решение:

class Solution {
    private val directions = arrayOf(
        intArrayOf(-1, 0), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(0, 1)
    )
    private lateinit var grid: Array<IntArray>
    private var N = 0

    fun largestIsland(grid: Array<IntArray>): Int {
        this.grid = grid
        N = grid.size

        var index = 2
        val area = IntArray(N * N + 2)
        for (r in 0 until N) {
            for (c in 0 until N) {
                if (grid[r][c] == 1) {
                    area[index] = dfs(r, c, index)
                    index++
                }
            }
        }

        var ans = area.maxOrNull() ?: 0
        for (r in 0 until N) {
            for (c in 0 until N) {
                if (grid[r][c] == 0) {
                    val seen = mutableSetOf<Int>()
                    for ((nr, nc) in neighbors(r, c)) {
                        if (grid[nr][nc] > 1) {
                            seen.add(grid[nr][nc])
                        }
                    }
                    ans = maxOf(ans, 1 + seen.sumOf { area[it] })
                }
            }
        }
        return ans
    }

    private fun dfs(r: Int, c: Int, index: Int): Int {
        var ans = 1
        grid[r][c] = index
        for ((nr, nc) in neighbors(r, c)) {
            if (grid[nr][nc] == 1) {
                grid[nr][nc] = index
                ans += dfs(nr, nc, index)
            }
        }
        return ans
    }

    private fun neighbors(r: Int, c: Int): List<Pair<Int, Int>> {
        val result = mutableListOf<Pair<Int, Int>>()
        for (dir in directions) {
            val nr = r + dir[0]
            val nc = c + dir[1]
            if (nr in 0 until N && nc in 0 until N) {
                result.add(nr to nc)
            }
        }
        return result
    }

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

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

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

Задача: 1260. Shift 2D Grid
Сложность: easy

Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз.

Пример:

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

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

1⃣Преобразовать двумерную сетку в одномерный массив.

2⃣Выполнить сдвиг элементов в одномерном массиве.

3⃣Преобразовать одномерный массив обратно в двумерную сетку.

😎 Решение:

class Solution {
    fun shiftGrid(grid: Array<Array<Int>>, k: Int): Array<Array<Int>> {
        val m = grid.size
        val n = grid[0].size
        val total = m * n
        var k = k % total

        if (k == 0) {
            return grid
        }

        val flatArray = IntArray(total)
        for (i in 0 until total) {
            flatArray[i] = grid[i / n][i % n]
        }

        val newArray = IntArray(total)
        for (i in 0 until total) {
            newArray[(i + k) % total] = flatArray[i]
        }

        val newGrid = Array(m) { Array(n) { 0 } }
        for (i in 0 until m) {
            for (j in 0 until n) {
                newGrid[i][j] = newArray[i * n + j]
            }
        }

        return newGrid
    }
}

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

Задача: 1095. Find in Mountain Array
Сложность: hard

Массив arr является горным массивом тогда и только тогда, когда:

Длина массива arr >= 3.
Существует некоторое i с 0 < i < arr.length - 1 такое, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1.

Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray:

MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0).
MountainArray.length() возвращает длину массива.
Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы.

Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

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

1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика.

2⃣Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем.

3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1.

😎 Решение:

class Solution {
    fun findInMountainArray(target: Int, mountainArr: MountainArray): Int {
        val length = mountainArr.length()

        var low = 1
        var high = length - 2
        while (low != high) {
            val mid = (low + high) / 2
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        val peak = low

        low = 0
        high = peak
        while (low < high) {
            val mid = (low + high) / 2
            if (mountainArr.get(mid) < target) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        if (mountainArr.get(low) == target) {
            return low
        }

        low = peak + 1
        high = length - 1
        while (low < high) {
            val mid = (low + high) / 2
            if (mountainArr.get(mid) > target) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        if (mountainArr.get(low) == target) {
            return low
        }

        return -1
    }
}

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

Задача: 657. Robot Return to Origin
Сложность: easy

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

Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз).

Верните true, если робот возвращается в исходную точку после завершения всех своих движений, или false в противном случае.

Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода.

Пример:

Input: moves = "UD"
Output: true

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

1⃣Инициализация координат:
Начните с координат (0, 0).

2⃣Обработка движений:
Пройдите по строке moves и обновляйте координаты в зависимости от движения:
'R' увеличивает координату x на 1.
'L' уменьшает координату x на 1.
'U' увеличивает координату y на 1.
'D' уменьшает координату y на 1.

3⃣Проверка конечных координат:
Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    fun judgeCircle(moves: String): Boolean {
        var x = 0
        var y = 0
        for (move in moves) {
            when (move) {
                'R' -> x++
                'L' -> x--
                'U' -> y++
                'D' -> y--
            }
        }
        return x == 0 && y == 0
    }
}

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

Задача: 993. Cousins in Binary Tree
Сложность: easy

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

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

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

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

1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.

2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

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

😎 Решение:

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

class Solution {
    private var parentX: TreeNode? = null
    private var parentY: TreeNode? = null
    private var depthX = -1
    private var depthY = -1
    
    fun isCousins(root: TreeNode?, x: Int, y: Int): Boolean {
        dfs(root, null, 0, x, y)
        return depthX == depthY && parentX != parentY
    }
    
    private fun dfs(node: TreeNode?, parent: TreeNode?, depth: Int, x: Int, y: Int) {
        if (node == null) return
        if (node.`val` == x) {
            parentX = parent
            depthX = depth
        } else if (node.`val` == y) {
            parentY = parent
            depthY = depth
        } else {
            dfs(node.left, node, depth + 1, x, y)
            dfs(node.right, node, depth + 1, x, y)
        }
    }
}

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

Задача: 1518. Water Bottles
Сложность: easy

Есть numBottles бутылок с водой, которые изначально наполнены водой. Вы можете обменять numExchange пустых бутылок на одну полную бутылку воды на рынке.

Операция питья полной бутылки воды превращает её в пустую бутылку.

Даны два целых числа numBottles и numExchange. Верните максимальное количество бутылок с водой, которые вы можете выпить.

Пример:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

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

1⃣Инициализируйте переменную ответа consumedBottles значением 0.

2⃣Продолжайте выполнять следующие действия, пока количество numBottles больше или равно numExchange:
— Выпейте numExchange количество полных бутылок, т.е. добавьте numExchange к consumedBottles.
— Уменьшите numExchange от доступных полных бутылок numBottles.
— Обменяйте пустые бутылки на одну полную бутылку, т.е. увеличьте numBottles на одну.

3⃣Верните consumedBottles + numBottles.

😎 Решение:

class Solution {
    fun numWaterBottles(numBottles: Int, numExchange: Int): Int {
        var numBottles = numBottles
        var consumedBottles = 0

        while (numBottles >= numExchange) {
            consumedBottles += numExchange
            numBottles -= numExchange
            numBottles++
        }

        return consumedBottles + numBottles
    }
}

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

Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium

Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.

Пример:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false

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

1⃣Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.

2⃣Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.

3⃣Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.

😎 Решение:

class Solution {
    fun leadsToDestination(n: Int, edges: Array<IntArray>, source: Int, destination: Int): Boolean {
        val graph = mutableMapOf<Int, MutableList<Int>>()
        for (edge in edges) {
            graph.computeIfAbsent(edge[0]) { mutableListOf() }.add(edge[1])
        }
        
        val visited = IntArray(n)
        
        return dfs(graph, visited, source, destination)
    }
    
    private fun dfs(graph: MutableMap<Int, MutableList<Int>>, visited: IntArray, node: Int, destination: Int): Boolean {
        if (visited[node] != 0) return visited[node] == 2
        if (!graph.containsKey(node)) return node == destination
        visited[node] = 1
        for (neighbor in graph[node]!!) {
            if (!dfs(graph, visited, neighbor, destination)) return false
        }
        visited[node] = 2
        return true
    }
}

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

Задача: 647. Palindromic Substrings
Сложность: medium

Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "abc"
Output: 3

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

1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.

2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.

3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.

😎 Решение:

fun countSubstrings(s: String): Int {
    var totalCount = 0
    
    fun expandAroundCenter(left: Int, right: Int): Int {
        var left = left
        var right = right
        var count = 0
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            count++
            left--
            right++
        }
        return count
    }
    
    for (i in s.indices) {
        totalCount += expandAroundCenter(i, i)
        totalCount += expandAroundCenter(i, i + 1)
    }
    return totalCount
}

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

Задача: 28. Find the Index of the First Occurrence in a String
Сложность: easy

Учитывая две строки, needle и haystack, верните индекс первого вхождения needle в haystack или -1, если needle не является частью haystack.

Пример:

Input: haystack = "sadbutsad", needle = "sad"  
Output: 0  

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

1⃣ Используем встроенную функцию indexOf для поиска подстроки.

2⃣ Если подстрока найдена, возвращаем индекс ее первого вхождения.

3⃣ Если подстрока отсутствует, метод indexOf вернет -1.

😎 Решение:

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        return haystack.indexOf(needle)
    }
}

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