Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: root = [4,2,6,1,3]
Output: 1

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

1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.

2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.

3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.

😎 Решение:

class Solution {
    private val inorderNodes = mutableListOf<Int>()
    
    private fun inorderTraversal(root: TreeNode?) {
        if (root == null) return
        
        inorderTraversal(root.left)
        inorderNodes.add(root.`val`)
        inorderTraversal(root.right)
    }
    
    fun minDiffInBST(root: TreeNode?): Int {
        inorderTraversal(root)
        
        var minDistance = Int.MAX_VALUE
        for (i in 1 until inorderNodes.size) {
            minDistance = minOf(minDistance, inorderNodes[i] - inorderNodes[i - 1])
        }
        
        return minDistance
    }
}

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

Задача: 666. Path Sum IV
Сложность: medium

Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве:

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

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

1⃣Создание структуры дерева:
Пройдите по массиву nums и для каждого элемента создайте узел дерева.
Сохраните узлы в словаре для удобного доступа по их позиции.

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

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

class Solution {
    fun pathSum(nums: IntArray): Int {
        val tree = mutableMapOf<Pair<Int, Int>, Int>()
        
        for (num in nums) {
            val depth = num / 100
            val pos = (num / 10) % 10
            val val = num % 10
            tree[depth to pos] = val
        }
        
        var totalSum = 0
        
        fun dfs(depth: Int, pos: Int, currentSum: Int) {
            val node = tree[depth to pos] ?: return
            val newSum = currentSum + node
            val leftChild = depth + 1 to 2 * pos - 1
            val rightChild = depth + 1 to 2 * pos
            
            if (tree[leftChild] == null && tree[rightChild] == null) {
                totalSum += newSum
            } else {
                dfs(depth + 1, 2 * pos - 1, newSum)
                dfs(depth + 1, 2 * pos, newSum)
            }
        }
        
        dfs(1, 1, 0)
        return totalSum
    }
}

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

Задача: 310. Minimum Height Trees
Сложность: medium

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

Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT).

Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке.

Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом.

Пример:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

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

1⃣Создание списка смежности
Создайте список смежности, представляющий граф.

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

3⃣Повторение процесса
Повторяйте процесс до тех пор, пока не останется два или менее узлов. Эти узлы будут корнями деревьев с минимальной высотой (MHT).

😎 Решение:

class Solution {
    fun findMinHeightTrees(n: Int, edges: Array<IntArray>): List<Int> {
        if (n == 1) return listOf(0)
        
        val adj = Array(n) { mutableListOf<Int>() }
        for (edge in edges) {
            adj[edge[0]].add(edge[1])
            adj[edge[1]].add(edge[0])
        }
        
        val leaves = mutableListOf<Int>()
        for (i in 0 until n) {
            if (adj[i].size == 1) {
                leaves.add(i)
            }
        }
        
        var remainingNodes = n
        while (remainingNodes > 2) {
            remainingNodes -= leaves.size
            val newLeaves = mutableListOf<Int>()
            for (leaf in leaves) {
                val neighbor = adj[leaf].removeAt(0)
                adj[neighbor].remove(leaf)
                if (adj[neighbor].size == 1) {
                    newLeaves.add(neighbor)
                }
            }
            leaves.clear()
            leaves.addAll(newLeaves)
        }
        
        return leaves
    }
}

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

Задача: 216. Combination Sum III
Сложность: medium

Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:

Используются только числа от 1 до 9.
Каждое число используется не более одного раза.
Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке.

Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

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

1⃣Запускаем backtrack: передаем оставшуюся величину, размер k, текущую зависимость и следующий индекс.

2⃣Если длина 0 и размер = k — добавьте соединение. Иначе пробуем числа от текущего до 9.

3⃣После каждого рекурсивного вызова откатываем последнее добавление.

😎 Решение:

class Solution {
    fun backtrack(remain: Int, k: Int, comb: MutableList<Int>, nextStart: Int, results: MutableList<MutableList<Int>>) {
        if (remain == 0 && comb.size == k) {
            results.add(ArrayList(comb))
            return
        } else if (remain < 0 || comb.size == k) {
            return
        }

        for (i in nextStart until 9) {
            comb.add(i + 1)
            backtrack(remain - i - 1, k, comb, i + 1, results)
            comb.removeAt(comb.size - 1)
        }
    }

    fun combinationSum3(k: Int, n: Int): List<List<Int>> {
        val results = mutableListOf<MutableList<Int>>()
        val comb = mutableListOf<Int>()
        backtrack(n, k, comb, 0, results)
        return results
    }
}

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

Задача: 1019. Next Greater Node In Linked List
Сложность: medium

Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.

Пример:

Input: head = [2,1,5]
Output: [5,5,0]

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

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

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

3⃣Заполнение оставшихся значений:
Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента.

😎 Решение:

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

class Solution {
    fun nextLargerNodes(head: ListNode?): IntArray {
        val values = mutableListOf<Int>()
        var current = head
        while (current != null) {
            values.add(current.`val`)
            current = current.next
        }
        
        val answer = IntArray(values.size)
        val stack = mutableListOf<Int>()
        
        for (i in values.indices) {
            while (stack.isNotEmpty() && values[stack.last()] < values[i]) {
                answer[stack.removeAt(stack.size - 1)] = values[i]
            }
            stack.add(i)
        }
        
        return answer
    }
}

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

Задача: 25. Reverse Nodes in k-Group
Сложность: hard

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

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

1⃣ Проверяем, хватает ли элементов в текущей группе (не менее k узлов).

2⃣ Если хватает, переворачиваем узлы в группе, используя указатели.

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

😎 Решение:

class Solution {
    fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        var count = 0
        var cur = head
        while (count < k && cur != null) {
            cur = cur.next
            count++
        }
        if (count < k) return head

        var prev: ListNode? = null
        cur = head
        repeat(k) {
            val next = cur?.next
            cur?.next = prev
            prev = cur
            cur = next
        }

        head?.next = reverseKGroup(cur, k)
        return prev
    }
}

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

Задача: 622. Design Circular Queue
Сложность: medium

Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.

Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

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

1⃣Используйте массив фиксированного размера для хранения элементов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди.

2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу.

3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди.

😎 Решение:

class MyCircularQueue(k: Int) {
    private val queue: IntArray = IntArray(k) { -1 }
    private var front: Int = 0
    private var rear: Int = -1
    private var size: Int = 0
    private val capacity: Int = k
    
    fun enQueue(value: Int): Boolean {
        if (isFull()) {
            return false
        }
        rear = (rear + 1) % capacity
        queue[rear] = value
        size++
        return true
    }
    
    fun deQueue(): Boolean {
        if (isEmpty()) {
            return false
        }
        front = (front + 1) % capacity
        size--
        return true
    }
    
    fun Front(): Int {
        return if (isEmpty()) -1 else queue[front]
    }
    
    fun Rear(): Int {
        return if (isEmpty()) -1 else queue[rear]
    }
    
    fun isEmpty(): Boolean {
        return size == 0
    }
    
    fun isFull(): Boolean {
        return size == capacity
    }
}

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

Задача: 1272. Remove Interval
Сложность: medium

Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.

Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

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

1⃣Итерируйтесь по каждому интервалу в списке intervals.

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

3⃣Добавляйте непересекающиеся части текущего интервала в результат.

😎 Решение:

class Solution {
    fun removeInterval(intervals: List<List<Double>>, toBeRemoved: List<Double>): List<List<Double>> {
        val result = mutableListOf<List<Double>>()
        for (interval in intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.add(listOf(interval[0], minOf(interval[1], toBeRemoved[0])))
            }
            if (interval[1] > toBeRemoved[1]) {
                result.add(listOf(maxOf(interval[0], toBeRemoved[1]), interval[1]))
            }
        }
        return result
    }
}

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

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

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

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

😎 Решение:

fun longestWord(words: Array<String>): String {
    words.sort()
    val validWords = mutableSetOf("")
    var longest = ""
    for (word in words) {
        if (validWords.contains(word.dropLast(1))) {
            validWords.add(word)
            if (word.length > longest.length) {
                longest = word
            }
        }
    }
    return longest
}

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
    fun minArea(image: Array<CharArray>, x: Int, y: Int): Int {
        val m = image.size
        val n = image[0].size
        val left = searchColumns(image, 0, y, 0, m, true)
        val right = searchColumns(image, y + 1, n, 0, m, false)
        val top = searchRows(image, 0, x, left, right, true)
        val bottom = searchRows(image, x + 1, m, left, right, false)
        return (right - left) * (bottom - top)
    }

    private fun searchColumns(image: Array<CharArray>, i: Int, j: Int, top: Int, bottom: Int, whiteToBlack: Boolean): Int {
        var i = i
        var j = j
        while (i != j) {
            var k = top
            val mid = (i + j) / 2
            while (k < bottom && image[k][mid] == '0') {
                k++
            }
            if ((k < bottom) == whiteToBlack) {
                j = mid
            } else {
                i = mid + 1
            }
        }
        return i
    }

    private fun searchRows(image: Array<CharArray>, i: Int, j: Int, left: Int, right: Int, whiteToBlack: Boolean): Int {
        var i = i
        var j = j
        while (i != j) {
            var k = left
            val mid = (i + j) / 2
            while (k < right && image[mid][k] == '0') {
                k++
            }
            if ((k < right) == whiteToBlack) {
                j = mid
            } else {
                i = mid + 1
            }
        }
        return i
    }
}

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy

Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.

Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.

Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

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

2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.

3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.

😎 Решение:

class Solution {
    fun isMajorityElement(nums: IntArray, target: Int): Boolean {
        var count = 0
        for (num in nums) {
            if (num == target) {
                count++
            }
        }
        return count > nums.size / 2
    }
}

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

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

Напишите алгоритм для определения, является ли число n счастливым.

Счастливое число определяется следующим процессом:

Начиная с любого положительного целого числа, замените число суммой квадратов его цифр.
Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1.
Те числа, для которых этот процесс завершается 1, являются счастливыми.
Верните true, если n является счастливым числом, и false, если нет.

Пример:

Input: n = 2
Output: false

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

1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач.

2⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet.

3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач.

😎 Решение:

class Solution {
    private fun getNext(n: Int): Int {
        var n = n
        var totalSum = 0
        while (n > 0) {
            val digit = n % 10
            n /= 10
            totalSum += digit * digit
        }
        return totalSum
    }

    fun isHappy(n: Int): Boolean {
        var n = n
        val seen = mutableSetOf<Int>()
        while (n != 1 && n !in seen) {
            seen.add(n)
            n = getNext(n)
        }
        return n == 1
    }
}

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

Задача: 147. Insertion Sort List
Сложность: medium

Дан односвязный список.
Нужно отсортировать его с помощью сортировки вставками и вернуть новую голову списка.

Пример:

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

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

1⃣Создайте фиктивный узел dummy, указывающий на начало нового отсортированного списка. Он упростит вставку элементов, в том числе в начало.

2⃣Для каждого узла curr из оригинального списка найдите место в отсортированной части (dummy), где он должен стоять, и вставьте его туда.

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

😎 Решение:

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

class Solution {
    fun insertionSortList(head: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var curr = head

        while (curr != null) {
            var prev = dummy
            while (prev.next != null && prev.next!!.`val` <= curr.`val`) {
                prev = prev.next!!
            }
            val next = curr.next
            curr.next = prev.next
            prev.next = curr
            curr = next
        }
        return dummy.next
    }
}

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

Задача: 446. Arithmetic Slices II - Subsequence
Сложность: hard

Дан целочисленный массив nums, вернуть количество всех арифметических подпоследовательностей nums.

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

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.

2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

3⃣Возвращаем количество всех арифметических подпоследовательностей.

😎 Решение:

class Solution {
    private var n = 0
    private var ans = 0

    private fun dfs(dep: Int, A: IntArray, cur: MutableList<Long>) {
        if (dep == n) {
            if (cur.size < 3) return
            for (i in 1 until cur.size) {
                if (cur[i] - cur[i - 1] != cur[1] - cur[0]) return
            }
            ans++
            return
        }
        dfs(dep + 1, A, cur)
        cur.add(A[dep].toLong())
        dfs(dep + 1, A, cur)
        cur.removeAt(cur.size - 1)
    }

    fun numberOfArithmeticSlices(A: IntArray): Int {
        n = A.size
        ans = 0
        dfs(0, A, mutableListOf())
        return ans
    }
}

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

Задача: 272. Closest Binary Search Tree Value II
Сложность: hard

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

Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.

Пример:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

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

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

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

3⃣Вернуть первые k значений из отсортированного массива:
Извлечь первые k элементов из отсортированного массива и вернуть их.

😎 Решение:

class Solution {
    fun closestKValues(root: TreeNode?, target: Double, k: Int): List<Int> {
        val arr = mutableListOf<Int>()
        dfs(root, arr)
        arr.sortBy { Math.abs(it - target) }
        return arr.take(k)
    }
    
    private fun dfs(node: TreeNode?, arr: MutableList<Int>) {
        if (node == null) return
        arr.add(node.`val`)
        dfs(node.left, arr)
        dfs(node.right, arr)
    }
}

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

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

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.

😎 Решение:

class Solution {
    fun minCostToMoveChips(position: IntArray): Int {
        var evenCount = 0
        var oddCount = 0
        
        for (pos in position) {
            if (pos % 2 == 0) {
                evenCount++
            } else {
                oddCount++
            }
        }
        
        return minOf(evenCount, oddCount)
    }
}

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

Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed
Сложность: hard

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

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

RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.
bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.
bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.
int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.
Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.

Пример:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

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

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

2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае.
Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае.

3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента.

😎 Решение:

import kotlin.random.Random

class RandomizedCollection {
    private val dict = mutableMapOf<Int, MutableSet<Int>>()
    private val list = mutableListOf<Int>()

    fun insert(val: Int): Boolean {
        val exists = dict.containsKey(val)
        if (!exists) {
            dict[val] = mutableSetOf()
        }
        dict[val]?.add(list.size)
        list.add(val)
        return !exists
    }

    fun remove(val: Int): Boolean {
        val indices = dict[val] ?: return false
        val index = indices.first()
        indices.remove(index)
        val lastElement = list.removeAt(list.size - 1)
        if (index < list.size) {
            list[index] = lastElement
            dict[lastElement]?.remove(list.size)
            dict[lastElement]?.add(index)
        }
        if (indices.isEmpty()) {
            dict.remove(val)
        }
        return true
    }

    fun getRandom(): Int {
        return list[Random.nextInt(list.size)]
    }
}

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

Задача: 267. Palindrome Permutation II
Сложность: medium

Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.

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

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

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

2⃣Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.

3⃣Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private HashSet<string> set;

    public Solution() {
        set = new HashSet<string>();
    }

    public IList<string> GeneratePalindromes(string s) {
        int[] map = new int[128];
        char[] st = new char[s.Length / 2];
        if (!CanPermutePalindrome(s, map)) {
            return new List<string>();
        }

        char ch = '\0';
        int k = 0;
        for (int i = 0; i < map.Length; i++) {
            if (map[i] % 2 == 1) {
                ch = (char)i;
            }
            for (int j = 0; j < map[i] / 2; j++) {
                st[k++] = (char)i;
            }
        }
        Permute(st, 0, ch);
        return new List<string>(set);
    }

    private bool CanPermutePalindrome(string s, int[] map) {
        int count = 0;
        foreach (char c in s) {
            int index = (int)c;
            map[index]++;
            if (map[index] % 2 == 0) {
                count--;
            } else {
                count++;
            }
        }
        return count <= 1;
    }

    private void Swap(ref char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    private void Permute(char[] s, int l, char ch) {
        if (l == s.Length) {
            StringBuilder sb = new StringBuilder();
            sb.Append(s);
            if (ch != '\0') {
                sb.Append(ch);
            }
            Array.Reverse(s);
            sb.Append(s);
            set.Add(sb.ToString());
            Array.Reverse(s);
        } else {
            for (int i = l; i < s.Length; i++) {
                if (s[l] != s[i] || l == i) {
                    Swap(ref s, l, i);
                    Permute(s, l + 1, ch);
                    Swap(ref s, l, i);
                }
            }
        }
    }
}

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

Задача: 1801. Number of Orders in the Backlog
Сложность: medium

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:

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

Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.

Пример:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

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

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

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

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

class Solution {
    fun getNumberOfBacklogOrders(orders: Array<IntArray>): Int {
        val MOD = 1_000_000_007
        val buyOrders = PriorityQueue(compareByDescending<Pair<Int, Int>> { it.first })
        val sellOrders = PriorityQueue(compareBy<Pair<Int, Int>> { it.first })

        orders.forEach { (price, amount, orderType) ->
            var remainingAmount = amount
            if (orderType == 0) {
                while (remainingAmount > 0 && sellOrders.isNotEmpty() && sellOrders.peek().first <= price) {
                    val (sellPrice, sellAmount) = sellOrders.poll()
                    val executedAmount = minOf(remainingAmount, sellAmount)
                    remainingAmount -= executedAmount
                    if (sellAmount > executedAmount) sellOrders.add(sellPrice to sellAmount - executedAmount)
                }
                if (remainingAmount > 0) buyOrders.add(price to remainingAmount)
            } else {
                while (remainingAmount > 0 && buyOrders.isNotEmpty() && buyOrders.peek().first >= price) {
                    val (buyPrice, buyAmount) = buyOrders.poll()
                    val executedAmount = minOf(remainingAmount, buyAmount)
                    remainingAmount -= executedAmount
                    if (buyAmount > executedAmount) buyOrders.add(buyPrice to buyAmount - executedAmount)
                }
                if (remainingAmount > 0) sellOrders.add(price to remainingAmount)
            }
        }

        return (buyOrders.sumOf { it.second } + sellOrders.sumOf { it.second }) % MOD
    }
}

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

Задача: 1406. Stone Game III
Сложность: hard

Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.

Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.

Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.

Пример:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

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

1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0.

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

3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья.

😎 Решение:

class Solution {
    fun stoneGameIII(stoneValue: IntArray): String {
        val n = stoneValue.size
        val dp = IntArray(n + 1)
        for (i in n - 1 downTo 0) {
            dp[i] = stoneValue[i] - dp[i + 1]
            if (i + 2 <= n) {
                dp[i] = maxOf(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2])
            }
            if (i + 3 <= n) {
                dp[i] = maxOf(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3])
            }
        }
        return when {
            dp[0] > 0 -> "Alice"
            dp[0] < 0 -> "Bob"
            else -> "Tie"
        }
    }
}

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