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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium

Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.

Пример:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

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

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

2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.

3⃣Вернуть первые j символов строки.

😎 Решение:

class Solution {
    fun removeDuplicates(s: String, k: Int): String {
        val counts = mutableListOf<Int>()
        val sa = s.toCharArray()
        var j = 0
        
        for (i in sa.indices) {
            sa[j] = sa[i]
            if (j == 0 || sa[j] != sa[j - 1]) {
                counts.add(1)
            } else {
                val incremented = counts.removeAt(counts.size - 1) + 1
                if (incremented == k) {
                    j -= k
                } else {
                    counts.add(incremented)
                }
            }
            j++
        }
        return String(sa, 0, j)
    }
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

using System.Collections.Generic;

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

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

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

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

    public TreeNode Get_root() {
        return root;
    }
}

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

class Solution {
    private var maxLength = 0

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

    var lastIdx = 1
    var curVal = nums[0]

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

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

Задача: 1522. Diameter of N-Ary Tree
Сложность: medium

Дано корневое дерево N-арности, нужно вычислить длину диаметра дерева.

Диаметр N-арного дерева - это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.

(Входная сериализация N-арного дерева представлена их обходом в порядке уровней, каждая группа дочерних узлов разделена значением null.)

Пример:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

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

1⃣Определите функцию height(node), которая возвращает высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один.

2⃣Внутри функции height(node) выберите две наибольшие высоты среди дочерних узлов. Эти два значения помогут вычислить длину пути, которая будет кандидатом на диаметр всего дерева.

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

😎 Решение:

class Solution {
    var diameter = 0

    fun height(node: Node?): Int {
        if (node == null || node.children.isEmpty()) return 0

        var maxHeight1 = 0
        var maxHeight2 = 0
        for (child in node.children) {
            val parentHeight = height(child) + 1
            if (parentHeight > maxHeight1) {
                maxHeight2 = maxHeight1
                maxHeight1 = parentHeight
            } else if (parentHeight > maxHeight2) {
                maxHeight2 = parentHeight
            }
            val distance = maxHeight1 + maxHeight2
            diameter = maxOf(diameter, distance)
        }
        return maxHeight1
    }

    fun diameter(root: Node?): Int {
        diameter = 0
        height(root)
        return diameter
    }
}

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

Задача: 360. Sort Transformed Array
Сложность: medium

Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.

Пример:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

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

1⃣Преобразование и сортировка
Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed.

2⃣Поразрядная сортировка
Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed.

3⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

class Solution {
    fun sortTransformedArray(nums: IntArray, a: Int, b: Int, c: Int): IntArray {
        val transformed = nums.map { a * it * it + b * it + c }.toIntArray()
        radixSort(transformed)
        return transformed
    }

    private fun radixSort(array: IntArray) {
        val maxElement = array.map { Math.abs(it) }.maxOrNull() ?: 0
        var placeValue = 1

        while (maxElement / placeValue > 0) {
            countingSortByDigit(array, placeValue)
            placeValue *= 10
        }

        val negatives = array.filter { it < 0 }.sorted()
        val positives = array.filter { it >= 0 }.sorted()

        array.indices.forEach { index ->
            array[index] = if (index < negatives.size) {
                negatives[index]
            } else {
                positives[index - negatives.size]
            }
        }
    }

    private fun countingSortByDigit(array: IntArray, placeValue: Int) {
        val output = IntArray(array.size)
        val count = IntArray(10)

        array.forEach {
            val digit = (Math.abs(it) / placeValue) % 10
            count[digit]++
        }

        for (i in 1 until 10) {
            count[i] += count[i - 1]
        }

        for (i in array.indices.reversed()) {
            val digit = (Math.abs(array[i]) / placeValue) % 10
            output[count[digit] - 1] = array[i]
            count[digit]--
        }

        output.indices.forEach { array[it] = output[it] }
    }
}

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

Задача: 225. Implement Stack using Queues
Сложность: easy

Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).

Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.

Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.

Пример:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

1⃣Реализация методов push и pop:
Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.
Метод pop удаляет элемент из q1 и обновляет значение top.

2⃣Реализация методов top и empty:
Метод top возвращает верхний элемент стека.
Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.

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

😎 Решение:

import java.util.LinkedList
import java.util.Queue

class MyStack {
    private var q1: Queue<Int> = LinkedList()
    private var q2: Queue<Int> = LinkedList()
    private var topElement: Int = 0

    fun push(x: Int) {
        q2.add(x)
        topElement = x
        while (q1.isNotEmpty()) {
            q2.add(q1.remove())
        }
        val temp = q1
        q1 = q2
        q2 = temp
    }

    fun pop(): Int {
        val result = q1.remove()
        if (q1.isNotEmpty()) {
            topElement = q1.peek()
        }
        return result
    }

    fun empty(): Boolean {
        return q1.isEmpty()
    }

    fun top(): Int {
        return topElement
    }
}

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

Задача: 289. Game of Life
Сложность: medium

Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году."

Доска состоит из сетки клеток размером m x n, где каждая клетка имеет начальное состояние: живая (представляется числом 1) или мёртвая (представляется числом 0). Каждая клетка взаимодействует с восемью соседями (по горизонтали, вертикали и диагоналям) согласно следующим четырём правилам (взято из вышеупомянутой статьи Википедии):

Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения.
Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения.
Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения.
Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения.
Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние.

Пример:

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

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

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

2⃣Применение правил:
На основе количества живых соседей и текущего состояния клетки примените правила игры:
Любая живая клетка с менее чем двумя живыми соседями умирает (становится -1).
Любая живая клетка с двумя или тремя живыми соседями остаётся живой (без изменений).
Любая живая клетка с более чем тремя живыми соседями умирает (становится -1).
Любая мёртвая клетка с ровно тремя живыми соседями становится живой (становится 2).

3⃣Обновление доски:
Пройдите через доску ещё раз и обновите состояния клеток:
Если значение клетки больше 0, установите её в 1 (живая).
Если значение клетки меньше или равно 0, установите её в 0 (мёртвая).

😎 Решение:

class Solution {
    fun gameOfLife(board: Array<IntArray>) {
        val neighbors = intArrayOf(0, 1, -1)
        val rows = board.size
        val cols = board[0].size

        for (row in 0 until rows) {
            for (col in 0 until cols) {
                var liveNeighbors = 0
                for (i in neighbors) {
                    for (j in neighbors) {
                        if (!(i == 0 && j == 0)) {
                            val r = row + i
                            val c = col + j
                            if (r in 0 until rows && c in 0 until cols && Math.abs(board[r][c]) == 1) {
                                liveNeighbors++
                            }
                        }
                    }
                }

                if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = -1
                }
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 2
                }
            }
        }

        for (row in 0 until rows) {
            for (col in 0 until cols) {
                board[row][col] = if (board[row][col] > 0) 1 else 0
            }
        }
    }
}

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

Задача: 392. Is Subsequence
Сложность: easy

Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.

Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).

Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

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

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

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

😎 Решение:

class Solution {
    fun isSubsequence(s: String, t: String): Boolean {
        val leftBound = s.length
        val rightBound = t.length
        var pLeft = 0
        var pRight = 0

        while (pLeft < leftBound && pRight < rightBound) {
            if (s[pLeft] == t[pRight]) {
                pLeft++
            }
            pRight++
        }
        return pLeft == leftBound
    }
}

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:

Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.

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

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

class Solution {
    fun flipLights(n: Int, m: Int): Int {
        val seen = mutableSetOf<Int>()
        val n = minOf(n, 6)
        val shift = maxOf(0, 6 - n)
        for (cand in 0 until 16) {
            val bcount = Integer.bitCount(cand)
            if (bcount % 2 == m % 2 && bcount <= m) {
                var lights = 0
                if ((cand shr 0 and 1) > 0) lights = lights xor (0b111111 shr shift)
                if ((cand shr 1 and 1) > 0) lights = lights xor (0b010101 shr shift)
                if ((cand shr 2 and 1) > 0) lights = lights xor (0b101010 shr shift)
                if ((cand shr 3 and 1) > 0) lights = lights xor (0b100100 shr shift)
                seen.add(lights)
            }
        }
        return seen.size
    }
}

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

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

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

class Solution {
    fun balanceBST(root: TreeNode?): TreeNode? {
        if (root == null) return null

        val vineHead = TreeNode(0)
        vineHead.right = root
        var current: TreeNode? = vineHead

        while (current?.right != null) {
            if (current.right!!.left != null) {
                rightRotate(current, current.right)
            } else {
                current = current.right
            }
        }

        var nodeCount = 0
        current = vineHead.right
        while (current != null) {
            nodeCount++
            current = current.right
        }

        var m = Math.pow(2.0, Math.floor(Math.log((nodeCount + 1).toDouble()) / Math.log(2.0))).toInt() - 1
        makeRotations(vineHead, nodeCount - m)
        while (m > 1) {
            m /= 2
            makeRotations(vineHead, m)
        }

        return vineHead.right
    }

    private fun rightRotate(parent: TreeNode?, node: TreeNode?) {
        val tmp = node!!.left
        node.left = tmp!!.right
        tmp.right = node
        parent!!.right = tmp
    }

    private fun leftRotate(parent: TreeNode?, node: TreeNode?) {
        val tmp = node!!.right
        node.right = tmp!!.left
        tmp.left = node
        parent!!.right = tmp
    }

    private fun makeRotations(vineHead: TreeNode?, count: Int) {
        var current = vineHead
        for (i in 0 until count) {
            val tmp = current!!.right
            leftRotate(current, tmp)
            current = current.right
        }
    }
}

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

Задача: 605. Can Place Flowers
Сложность: Easy

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

Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        var count = 0
        for (i in flowerbed.indices) {
            if (flowerbed[i] == 0) {
                val emptyLeft = i == 0 || flowerbed[i - 1] == 0
                val emptyRight = i == flowerbed.size - 1 || flowerbed[i + 1] == 0
                if (emptyLeft && emptyRight) {
                    flowerbed[i] = 1
                    count++
                }
            }
        }
        return count >= n
    }
}

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

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

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

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

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

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

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

😎 Решение:

class Solution {
    fun minMalwareSpread(graph: Array<IntArray>, initial: IntArray): Int {
        val n = graph.size
        val initialSet = initial.toHashSet()
        initial.sort()
        var minInfected = Int.MAX_VALUE
        var bestNode = initial[0]
        
        for (node in initial) {
            val infected = initialSet.toHashSet()
            infected.remove(node)
            for (i in initialSet) {
                if (i != node) {
                    dfs(graph, i, infected)
                }
            }
            if (infected.size < minInfected) {
                minInfected = infected.size
                bestNode = node
            }
        }
        
        return bestNode
    }
    
    private fun dfs(graph: Array<IntArray>, node: Int, infected: MutableSet<Int>) {
        for (neighbor in graph.indices) {
            if (graph[node][neighbor] == 1 && neighbor !in infected) {
                infected.add(neighbor)
                dfs(graph, neighbor, infected)
            }
        }
    }
}

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

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

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

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

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

3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.

😎 Решение:

class Solution {
    private val directions = arrayOf(
        intArrayOf(-1, -1), intArrayOf(-1, 0), intArrayOf(-1, 1), 
        intArrayOf(0, -1), intArrayOf(0, 1), 
        intArrayOf(1, -1), intArrayOf(1, 0), intArrayOf(1, 1)
    )

    fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
        if (grid[0][0] != 0 || grid[grid.size - 1][grid[0].size - 1] != 0) {
            return -1
        }

        val queue: Queue<Pair<Int, Int>> = LinkedList()
        queue.add(Pair(0, 0))
        grid[0][0] = 1

        while (queue.isNotEmpty()) {
            val (row, col) = queue.poll()
            val distance = grid[row][col]
            if (row == grid.size - 1 && col == grid[0].size - 1) {
                return distance
            }
            for (direction in directions) {
                val newRow = row + direction[0]
                val newCol = col + direction[1]
                if (newRow in 0 until grid.size && newCol in 0 until grid[0].size && grid[newRow][newCol] == 0) {
                    queue.add(Pair(newRow, newCol))
                    grid[newRow][newCol] = distance + 1
                }
            }
        }
        return -1
    }
}

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