#medium
Задача: 723. Candy Crush

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

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

2⃣Удалите отмеченные конфеты, установив их значение в 0.

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

😎 Решение:

class Solution {
    fun candyCrush(board: Array<IntArray>): Array<IntArray> {
        val m = board.size
        val n = board[0].size
        var stable = false

        while (!stable) {
            stable = true
            val crush = Array(m) { BooleanArray(n) }

            for (i in 0 until m) {
                for (j in 0 until n - 2) {
                    val v = Math.abs(board[i][j])
                    if (v != 0 && v == Math.abs(board[i][j + 1]) && v == Math.abs(board[i][j + 2])) {
                        stable = false
                        crush[i][j] = true
                        crush[i][j + 1] = true
                        crush[i][j + 2] = true
                    }
                }
            }

            for (i in 0 until m - 2) {
                for (j in 0 until n) {
                    val v = Math.abs(board[i][j])
                    if (v != 0 && v == Math.abs(board[i + 1][j]) && v == Math.abs(board[i + 2][j])) {
                        stable = false
                        crush[i][j] = true
                        crush[i + 1][j] = true
                        crush[i + 2][j] = true
                    }
                }
            }

            for (i in 0 until m) {
                for (j in 0 until n) {
                    if (crush[i][j]) {
                        board[i][j] = 0
                    }
                }
            }

            for (j in 0 until n) {
                var idx = m - 1
                for (i in m - 1 downTo 0) {
                    if (board[i][j] != 0) {
                        board[idx][j] = board[i][j]
                        idx--
                    }
                }
                for (i in idx downTo 0) {
                    board[i][j] = 0
                }
            }
        }

        return board
    }
}

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

#medium
Задача: 340. Longest Substring with At Most K Distinct Characters

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

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

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

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

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

😎 Решение:

class Solution {
    fun lengthOfLongestSubstringKDistinct(s: String, k: Int): Int {
        var left = 0
        var right = 0
        val charCount = mutableMapOf<Char, Int>()
        var maxLength = 0
        
        while (right < s.length) {
            charCount[s[right]] = charCount.getOrDefault(s[right], 0) + 1
            while (charCount.size > k) {
                charCount[s[left]] = charCount[s[left]]!! - 1
                if (charCount[s[left]] == 0) {
                    charCount.remove(s[left])
                }
                left++
            }
            maxLength = maxOf(maxLength, right - left + 1)
            right++
        }
        
        return maxLength
    }
}

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

#medium
Задача: 510. Inorder Successor in BST II

Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null.

Последующий узла — это узел с наименьшим ключом, большим, чем node.val.

Вы будете иметь прямой доступ к узлу, но не к корню дерева. Каждый узел будет иметь ссылку на своего родителя. Ниже приведено определение для Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Пример:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

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

1⃣Проверка правого поддерева
Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order.

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

3⃣Возвращение результата
Верните найденный узел или null, если следующий узел не найден.

😎 Решение:

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

class Solution {
    fun inorderSuccessor(x: Node?): Node? {
        var node = x
        if (node?.right != null) {
            node = node.right
            while (node?.left != null) {
                node = node.left
            }
            return node
        }

        while (node?.parent != null && node == node.parent?.right) {
            node = node.parent
        }
        return node?.parent
    }
}

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

#medium
Задача: 725. Split Linked List in Parts

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

Пример:

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

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

1⃣Определите общую длину связного списка.

2⃣Вычислите базовый размер каждой части и количество частей, которые должны быть на одну единицу длиннее.

3⃣Разделите список на части, присваивая каждую часть в массив результатов.

😎 Решение:

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

fun splitListToParts(root: ListNode?, k: Int): Array<ListNode?> {
    var length = 0
    var node = root
    while (node != null) {
        length++
        node = node.next
    }

    val partLength = length / k
    val extraParts = length % k

    val parts = Array<ListNode?>(k) { null }
    node = root
    for (i in 0 until k) {
        val partHead = node
        val partSize = partLength + if (i < extraParts) 1 else 0
        for (j in 0 until partSize - 1) {
            if (node != null) node = node.next
        }
        if (node != null) {
            val nextPart = node.next
            node.next = null
            node = nextPart
        }
        parts[i] = partHead
    }

    return parts
}

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

#medium
Задача: 341. Flatten Nested List Iterator

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

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

NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList.
int next() Возвращает следующий целый элемент вложенного списка.
boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

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

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

2⃣Метод next()
Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек.

3⃣Метод hasNext()
Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент.

😎 Решение:

class NestedIterator(nestedList: List<NestedInteger>) : Iterator<Int> {
    private val stack: Deque<NestedInteger> = ArrayDeque()
    
    init {
        flatten(nestedList)
    }
    
    private fun flatten(nestedList: List<NestedInteger>) {
        for (ni in nestedList.reversed()) {
            stack.push(ni)
        }
    }
    
    override fun next(): Int {
        return stack.pop().getInteger()
    }
    
    override fun hasNext(): Boolean {
        while (stack.isNotEmpty() && !stack.peek().isInteger()) {
            flatten(stack.pop().getList())
        }
        return stack.isNotEmpty()
    }
}

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

#medium
Задача: 729. My Calendar I

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

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

1⃣Создайте класс MyCalendar с инициализатором для хранения списка событий.

2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями.

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

😎 Решение:

class MyCalendar() {
    private val events = mutableListOf<Pair<Int, Int>>()

    fun book(start: Int, end: Int): Boolean {
        for ((s, e) in events) {
            if (start < e && end > s) {
                return false
            }
        }
        events.add(Pair(start, end))
        return true
    }
}

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

#medium
Задача: 731. My Calendar II

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

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

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

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

😎 Решение:

class MyCalendarTwo {
    private val events = mutableListOf<Pair<Int, Int>>()
    private val overlaps = mutableListOf<Pair<Int, Int>>()
    
    fun book(start: Int, end: Int): Boolean {
        for ((os, oe) in overlaps) {
            if (start < oe && end > os) {
                return false
            }
        }
        for ((es, ee) in events) {
            if (start < ee && end > es) {
                overlaps.add(Pair(maxOf(start, es), minOf(end, ee)))
            }
        }
        events.add(Pair(start, end))
        return true
    }
}

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

#medium
Задача: 737. Sentence Similarity II

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

fun areSentencesSimilar(sentence1: Array<String>, sentence2: Array<String>, similarPairs: List<List<String>>): Boolean {
    if (sentence1.size != sentence2.size) {
        return false
    }
    
    val graph = mutableMapOf<String, MutableList<String>>()
    for (pair in similarPairs) {
        val (x, y) = pair
        graph.computeIfAbsent(x) { mutableListOf() }.add(y)
        graph.computeIfAbsent(y) { mutableListOf() }.add(x)
    }
    
    fun dfs(word1: String, word2: String, visited: MutableSet<String>): Boolean {
        if (word1 == word2) {
            return true
        }
        visited.add(word1)
        for (neighbor in graph[word1].orEmpty()) {
            if (neighbor !in visited && dfs(neighbor, word2, visited)) {
                return true
            }
        }
        return false
    }
    
    for (i in sentence1.indices) {
        if (sentence1[i] != sentence2[i]) {
            if (!dfs(sentence1[i], sentence2[i], mutableSetOf())) {
                return false
            }
        }
    }
    
    return true
}

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

#medium
Задача: 738. Monotone Increasing Digits

Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами.

Пример:

Input: n = 10
Output: 9

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

1⃣Преобразуйте число в строку для удобства обработки.

2⃣Найдите позицию, где последовательность перестает быть монотонной.

3⃣Уменьшите соответствующую цифру и установите все последующие цифры в 9.

😎 Решение:

fun monotoneIncreasingDigits(N: Int): Int {
    val digits = N.toString().toCharArray()
    var marker = digits.size
    
    for (i in digits.size - 1 downTo 1) {
        if (digits[i] < digits[i - 1]) {
            marker = i
            digits[i - 1] = (digits[i - 1] - '0' - 1 + '0'.toInt()).toChar()
        }
    }
    
    for (i in marker until digits.size) {
        digits[i] = '9'
    }
    
    return String(digits).toInt()
}

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

#medium
Задача: 739. Daily Temperatures

Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

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

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

3⃣Возвращайте массив ответов.

😎 Решение:

fun dailyTemperatures(T: IntArray): IntArray {
    val answer = IntArray(T.size)
    val stack = mutableListOf<Int>()
    
    for (i in T.indices) {
        while (stack.isNotEmpty() && T[i] > T[stack.last()]) {
            val j = stack.removeAt(stack.size - 1)
            answer[j] = i - j
        }
        stack.add(i)
    }
    
    return answer
}

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

#medium
Задача: 740. Delete and Earn

Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.

Пример:

Input: nums = [3,4,2]
Output: 6

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

1⃣Подсчитайте количество каждого числа в массиве nums.

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

3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки.

😎 Решение:

fun deleteAndEarn(nums: IntArray): Int {
    val count = mutableMapOf<Int, Int>()
    for (num in nums) {
        count[num] = count.getOrDefault(num, 0) + 1
    }
    
    var avoid = 0
    var using = 0
    var prev = -1
    
    for (num in count.keys.sorted()) {
        if (num - 1 != prev) {
            val newAvoid = maxOf(avoid, using)
            using = num * count[num]!! + maxOf(avoid, using)
            avoid = newAvoid
        } else {
            val newAvoid = maxOf(avoid, using)
            using = num * count[num]!! + avoid
            avoid = newAvoid
        }
        prev = num
    }
    
    return maxOf(avoid, using)
}

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

#medium
Задача: 742. Closest Leaf in a Binary Tree

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

Пример:

Input: root = [1,3,2], k = 1
Output: 2

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

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

2⃣Найдите все листья и минимальное расстояние до них, используя BFS, начиная с найденного узла k.

3⃣Верните значение ближайшего листа.

😎 Решение:

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

fun findClosestLeaf(root: TreeNode?, k: Int): Int {
    val path = mutableListOf<TreeNode>()
    val leaves = mutableMapOf<TreeNode, Int>()
    
    fun findPath(node: TreeNode?, k: Int): Boolean {
        if (node == null) return false
        path.add(node)
        if (node.`val` == k) return true
        if (findPath(node.left, k) || findPath(node.right, k)) return true
        path.removeAt(path.size - 1)
        return false
    }
    
    fun findLeaves(node: TreeNode?) {
        if (node == null) return
        if (node.left == null && node.right == null) leaves[node] = 0
        findLeaves(node.left)
        findLeaves(node.right)
    }
    
    findPath(root, k)
    findLeaves(root)
    
    val queue = mutableListOf<Pair<TreeNode, Int>>()
    queue.add(Pair(path.last(), 0))
    val visited = mutableSetOf<TreeNode>()
    
    while (queue.isNotEmpty()) {
        val (node, dist) = queue.removeAt(0)
        if (leaves.containsKey(node)) return node.`val`
        visited.add(node)
        node.left?.let {
            if (!visited.contains(it)) queue.add(Pair(it, dist + 1))
        }
        node.right?.let {
            if (!visited.contains(it)) queue.add(Pair(it, dist + 1))
        }
        if (path.size > 1) {
            queue.add(Pair(path.removeAt(path.size - 1), dist + 1))
        }
    }
    return -1
}

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

#medium
Задача: 743. Network Delay Time

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

1⃣Представьте граф в виде списка смежности.

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

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

😎 Решение:

import java.util.*

fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
    val graph = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()
    for (i in 1..n) {
        graph[i] = mutableListOf()
    }
    for (time in times) {
        graph[time[0]]?.add(Pair(time[1], time[2]))
    }

    val minHeap = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    minHeap.add(Pair(0, k))
    val minTime = mutableMapOf<Int, Int>()
    for (i in 1..n) {
        minTime[i] = Int.MAX_VALUE
    }
    minTime[k] = 0

    while (minHeap.isNotEmpty()) {
        val (time, node) = minHeap.poll()
        graph[node]?.forEach { (neighbor, t) ->
            val newTime = time + t
            if (newTime < minTime[neighbor]!!) {
                minTime[neighbor] = newTime
                minHeap.add(Pair(newTime, neighbor))
            }
        }
    }

    val maxTime = minTime.values.maxOrNull()!!
    return if (maxTime == Int.MAX_VALUE) -1 else maxTime
}

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

#medium
Задача: 1530. Number of Good Leaf Nodes Pairs

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

Верните количество хороших пар листовых узлов в дереве.

Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

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

1⃣ Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла.

2⃣ Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS.

3⃣ Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.

😎 Решение:

class Solution {
    fun countPairs(root: TreeNode?, distance: Int): Int {
        val graph = mutableMapOf<TreeNode, MutableList<TreeNode>>()
        val leafNodes = mutableSetOf<TreeNode>()
        traverseTree(root, null, graph, leafNodes)
        var ans = 0
        for (leaf in leafNodes) {
            val bfsQueue: Queue<TreeNode> = LinkedList()
            val seen = mutableSetOf<TreeNode>()
            bfsQueue.add(leaf)
            seen.add(leaf)
            for (i in 0..distance) {
                val size = bfsQueue.size
                for (j in 0 until size) {
                    val currNode = bfsQueue.poll()
                    if (leafNodes.contains(currNode) && currNode != leaf) {
                        ans++
                    }
                    graph[currNode]?.let {
                        for (neighbor in it) {
                            if (!seen.contains(neighbor)) {
                                bfsQueue.add(neighbor)
                                seen.add(neighbor)
                            }
                        }
                    }
                }
            }
        }
        return ans / 2
    }

    private fun traverseTree(currNode: TreeNode?, prevNode: TreeNode?,
                             graph: MutableMap<TreeNode, MutableList<TreeNode>>, leafNodes: MutableSet<TreeNode>) {
        if (currNode == null) {
            return
        }
        if (currNode.left == null && currNode.right == null) {
            leafNodes.add(currNode)
        }
        if (prevNode != null) {
            graph.computeIfAbsent(prevNode) { mutableListOf() }.add(currNode)
            graph.computeIfAbsent(currNode) { mutableListOf() }.add(prevNode)
        }
        traverseTree(currNode.left, currNode, graph, leafNodes)
        traverseTree(currNode.right, currNode, graph, leafNodes)
    }
}

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

#medium
Задача: 750. Number Of Corner Rectangles

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

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

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

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

😎 Решение:

fun countCornerRectangles(grid: Array<IntArray>): Int {
    var count = 0
    for (i in grid.indices) {
        for (j in i + 1 until grid.size) {
            var numPairs = 0
            for (k in grid[0].indices) {
                if (grid[i][k] == 1 && grid[j][k] == 1) {
                    numPairs++
                }
            }
            if (numPairs > 1) {
                count += numPairs * (numPairs - 1) / 2
            }
        }
    }
    return count
}

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

#medium
Задача: 751. IP to CIDR

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

fun ipToInt(ip: String): Int {
    val parts = ip.split(".").map { it.toInt() }
    return (parts[0] shl 24) + (parts[1] shl 16) + (parts[2] shl 8) + parts[3]
}

fun intToIp(num: Int): String {
    return "${(num shr 24) and 255}.${(num shr 16) and 255}.${(num shr 8) and 255}.${num and 255}"
}

fun cidr(ip: String, prefixLength: Int): String {
    return "$ip/$prefixLength"
}

fun findCidrBlocks(startIp: String, n: Int): List<String> {
    var start = ipToInt(startIp)
    val result = mutableListOf<String>()
    var remaining = n
    
    while (remaining > 0) {
        var maxSize = 1
        while (maxSize <= start && maxSize <= remaining) {
            maxSize = maxSize shl 1
        }
        maxSize = maxSize shr 1
        
        while (start % maxSize != 0) {
            maxSize = maxSize shr 1
        }
        
        result.add(cidr(intToIp(start), 32 - Integer.bitCount(maxSize - 1) + 1))
        start += maxSize
        remaining -= maxSize
    }
    
    return result
}

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