Задача: 400. Nth Digit
Сложность: medium

Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Пример:

Input: n = 3
Output: 3

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

1⃣Определение диапазона:
Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.).
Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра.

2⃣Нахождение конкретного числа:
Когда определите диапазон, найдите точное число, содержащее n-ю цифру.
Определите индекс цифры в этом числе.

3⃣Возвращение n-й цифры:
Извлеките и верните n-ю цифру из найденного числа.

😎 Решение:

class Solution {
    fun findNthDigit(n: Int): Int {
        var n = n
        var length = 1
        var count = 9
        var start = 1
        
        while (n > length * count) {
            n -= length * count
            length++
            count *= 10
            start *= 10
        }
        
        start += (n - 1) / length
        val s = start.toString()
        return s[(n - 1) % length] - '0'
    }
}

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

Задача: 164. Maximum Gap
Сложность: medium

Дан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0.

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

Пример:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

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

1⃣Инициализация:
Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве.
Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1).

2⃣Размещение элементов в ведрах:
Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения.
Игнорируйте пустые ведра при расчете максимального интервала.

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

😎 Решение:

class Solution {
    fun maximumGap(nums: IntArray): Int {
        if (nums.isEmpty() || nums.size < 2) {
            return 0
        }

        val sortedNums = nums.sorted()
        var maxGap = 0

        for (i in 0 until sortedNums.size - 1) {
            maxGap = maxOf(sortedNums[i + 1] - sortedNums[i], maxGap)
        }

        return maxGap
    }
}

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

Задача: 1267. Count Servers that Communicate
Сложность: medium

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:

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

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

1⃣Подсчитайте количество серверов в каждой строке и каждом столбце.

2⃣Пройдите по каждой ячейке и определите, взаимодействует ли сервер с другими серверами в той же строке или столбце.

3⃣Подсчитайте и верните количество взаимодействующих серверов.

😎 Решение:

class Solution {
    fun countServers(grid: Array<IntArray>): Int {
        val rows = IntArray(grid.size)
        val cols = IntArray(grid[0].size)

        for (i in grid.indices) {
            for (j in grid[0].indices) {
                if (grid[i][j] == 1) {
                    rows[i]++
                    cols[j]++
                }
            }
        }

        var count = 0
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
                    count++
                }
            }
        }

        return count
    }
}

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

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

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

Задача: 652. Find Duplicate Subtrees
Сложность: medium

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

Пример:

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

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

1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева.

2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.

3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.

😎 Решение:

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

fun findDuplicateSubtrees(root: TreeNode?): List<TreeNode?> {
    val count = mutableMapOf<String, Int>()
    val result = mutableListOf<TreeNode?>()
    
    fun serialize(node: TreeNode?): String {
        if (node == null) return "#"
        val serial = "${node.`val`},${serialize(node.left)},${serialize(node.right)}"
        count[serial] = count.getOrDefault(serial, 0) + 1
        if (count[serial] == 2) {
            result.add(node)
        }
        return serial
    }
    
    serialize(root)
    return result
}

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

Задача: 261. Graph Valid Tree
Сложность: medium

У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.

Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.

Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

1⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false.

2⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.

3⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    fun validTree(n: Int, edges: Array<IntArray>): Boolean {
        if (edges.size != n - 1) {
            return false
        }
        
        val adjList = Array(n) { mutableListOf<Int>() }
        for (edge in edges) {
            adjList[edge[0]].add(edge[1])
            adjList[edge[1]].add(edge[0])
        }
        
        val parent = mutableMapOf(0 to -1)
        val queue = ArrayDeque<Int>()
        queue.add(0)
        
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            for (neighbor in adjList[node]) {
                if (neighbor == parent[node]) {
                    continue
                }
                if (neighbor in parent) {
                    return false
                }
                parent[neighbor] = node
                queue.add(neighbor)
            }
        }
        
        return parent.size == n
    }
}

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

Задача: 1535. Find the Winner of an Array Game
Сложность: medium

Дан целочисленный массив arr из различных целых чисел и целое число k.

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

Верните число, которое выиграет игру.

Гарантируется, что у игры будет победитель.

Пример:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

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

1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.

2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.

3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.

😎 Решение:

class Solution {
    fun getWinner(arr: IntArray, k: Int): Int {
        var maxElement = arr[0]
        val queue = ArrayDeque<Int>()
        
        for (i in 1 until arr.size) {
            maxElement = kotlin.math.max(maxElement, arr[i])
            queue.add(arr[i])
        }
        
        var curr = arr[0]
        var winstreak = 0
        
        while (queue.isNotEmpty()) {
            val opponent = queue.poll()
            
            if (curr > opponent) {
                queue.add(opponent)
                winstreak++
            } else {
                queue.add(curr)
                curr = opponent
                winstreak = 1
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr
            }
        }
        
        return -1
    }
}

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

Задача: 218. The Skyline Problem
Сложность: hard

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

Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:

lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.

Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

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

1⃣Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights.

2⃣Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex).

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

😎 Решение:

class Solution {
    fun getSkyline(buildings: Array<IntArray>): List<List<Int>> {
        val edgeSet = TreeSet<Int>()
        for (building in buildings) {
            edgeSet.add(building[0])
            edgeSet.add(building[1])
        }
        val edges = edgeSet.toList()
        val edgeIndexMap = mutableMapOf<Int, Int>()
        for (i in edges.indices) {
            edgeIndexMap[edges[i]] = i
        }
        val heights = IntArray(edges.size)
        for (building in buildings) {
            val left = building[0]
            val right = building[1]
            val height = building[2]
            val leftIndex = edgeIndexMap[left]!!
            val rightIndex = edgeIndexMap[right]!!
            for (idx in leftIndex until rightIndex) {
                heights[idx] = maxOf(heights[idx], height)
            }
        }
        val answer = mutableListOf<List<Int>>()
        for (i in heights.indices) {
            val currHeight = heights[i]
            val currPos = edges[i]
            if (answer.isEmpty() || answer.last()[1] != currHeight) {
                answer.add(listOf(currPos, currHeight))
            }
        }
        return answer
    }
}

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

Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium

Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.

Пример:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

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

1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2.

2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов.

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

😎 Решение:

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

class FindElements(root: TreeNode?) {
    private val values = mutableSetOf<Int>()
    
    init {
        root?.`val` = 0
        values.add(0)
        recover(root)
    }
    
    private fun recover(node: TreeNode?) {
        node?.left?.let {
            it.`val` = 2 * node.`val` + 1
            values.add(it.`val`)
            recover(it)
        }
        node?.right?.let {
            it.`val` = 2 * node.`val` + 2
            values.add(it.`val`)
            recover(it)
        }
    }
    
    fun find(target: Int): Boolean {
        return values.contains(target)
    }
}

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

Задача: 766. Toeplitz Matrix
Сложность: easy

Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.

Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.

Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

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

1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м

2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.

3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true.

😎 Решение:

class Solution {
    fun isToeplitzMatrix(matrix: Array<IntArray>): Boolean {
        val groups = mutableMapOf<Int, Int>()
        for (r in matrix.indices) {
            for (c in matrix[0].indices) {
                if (groups[r - c] == null) {
                    groups[r - c] = matrix[r][c]
                } else if (groups[r - c] != matrix[r][c]) {
                    return false
                }
            }
        }
        return true
    }
}

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

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

Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно.
При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае.

Пример:

Input: n = 6
Output: true

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

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

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

3⃣Проверь, что перевернутая строка отличается от исходной.

😎 Решение:

fun isConfusingNumber(n: Int): Boolean {
    val rotationMap = mapOf('0' to '0', '1' to '1', '6' to '9', '8' to '8', '9' to '6')
    val nStr = n.toString()
    var rotatedStr = ""

    for (char in nStr) {
        if (char !in rotationMap) {
            return false
        }
        rotatedStr = rotationMap[char] + rotatedStr
    }

    return rotatedStr != nStr
}

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

Задача: 1473. Paint House III
Сложность: hard

Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.

Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.

Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.

Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

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

1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.

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

3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.

😎 Решение:

class Solution {
    private val MAX_COST = 1000001
    private val memo = Array(100) { Array(100) { arrayOfNulls<Int>(22) } }

    private fun findMinCost(houses: IntArray, cost: Array<IntArray>, targetCount: Int, currIndex: Int, neighborhoodCount: Int, prevHouseColor: Int): Int {
        if (currIndex == houses.size) {
            return if (neighborhoodCount == targetCount) 0 else MAX_COST
        }
        
        if (neighborhoodCount > targetCount) {
            return MAX_COST
        }

        memo[currIndex][neighborhoodCount][prevHouseColor]?.let {
            return it
        }
        
        var minCost = MAX_COST

        if (houses[currIndex] != 0) {
            val newNeighborhoodCount = neighborhoodCount + if (houses[currIndex] != prevHouseColor) 1 else 0
            minCost = findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
        } else {
            for (color in 1..cost[0].size) {
                val newNeighborhoodCount = neighborhoodCount + if (color != prevHouseColor) 1 else 0
                val currCost = cost[currIndex][color - 1] + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
                minCost = kotlin.math.min(minCost, currCost)
            }
        }
        
        memo[currIndex][neighborhoodCount][prevHouseColor] = minCost
        return minCost
    }

    fun minCost(houses: IntArray, cost: Array<IntArray>, m: Int, n: Int, target: Int): Int {
        val answer = findMinCost(houses, cost, target, 0, 0, 0)
        return if (answer == MAX_COST) -1 else answer
    }
}

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

Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]

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

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

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

3⃣Создание нового дерева:
После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева.

😎 Решение:

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

class Solution {
    fun insertIntoMaxTree(root: TreeNode?, `val`: Int): TreeNode? {
        if (root == null || `val` > root.`val`) {
            val newNode = TreeNode(`val`)
            newNode.left = root
            return newNode
        }
        root.right = insertIntoMaxTree(root.right, `val`)
        return root
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Используем хеш-таблицу map для хранения ключей и двусвязный список для отслеживания порядка использования. Самый недавно использованный узел — в хвосте, наименее — в голове.

2⃣При get(key) проверяем наличие ключа в map. Если найден — перемещаем узел в конец списка и возвращаем значение. Иначе возвращаем -1.

3⃣При put(key, value) — если ключ уже есть, удаляем старый узел. Добавляем новый узел в конец списка и map. Если размер превышает capacity, удаляем узел из головы и из map.

😎 Решение:

class ListNode(val key: Int, var value: Int) {
    var next: ListNode? = null
    var prev: ListNode? = null
}

class LRUCache(private val capacity: Int) {
    private val map = mutableMapOf<Int, ListNode>()
    private val head = ListNode(-1, -1)
    private val tail = ListNode(-1, -1)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: Int): Int {
        val node = map[key] ?: return -1
        remove(node)
        add(node)
        return node.value
    }

    fun put(key: Int, value: Int) {
        if (map.containsKey(key)) {
            remove(map[key]!!)
        }
        val newNode = ListNode(key, value)
        map[key] = newNode
        add(newNode)
        if (map.size > capacity) {
            map.remove(head.next!!.key)?.also { remove(it) }
        }
    }

    private fun add(node: ListNode) {
        val prev = tail.prev
        node.prev = prev
        node.next = tail
        prev?.next = node
        tail.prev = node
    }

    private fun remove(node: ListNode) {
        val prev = node.prev
        val next = node.next
        prev?.next = next
        next?.prev = prev
    }
}

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

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

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