Задача: 936. Stamping The Sequence
Сложность: hard

Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив

Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

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

1⃣Инициализировать переменные:
s как массив символов '?', длиной target.length.
res как список для хранения результатов.
done как массив булевых значений для отслеживания того, какие позиции уже штампованы.
target как массив символов для удобства.

2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i.
Использовать функцию doStamp для штампования stamp в target начиная с индекса i.
Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length):
Перебрать все возможные начальные позиции для штампа.
Проверить, можно ли штамповать в текущей позиции.
Если можно, штамповать и добавить индекс в res.

3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив.

😎 Решение:

class Solution {
    fun movesToStamp(stamp: String, target: String): IntArray {
        val s = stamp.toCharArray()
        val t = target.toCharArray()
        val m = s.size
        val n = t.size
        val res = mutableListOf<Int>()
        val done = BooleanArray(n)
        
        fun canStamp(i: Int): Boolean {
            for (j in 0 until m) {
                if (t[i + j] != '?' && t[i + j] != s[j]) {
                    return false
                }
            }
            return true
        }
        
        fun doStamp(i: Int) {
            for (j in 0 until m) {
                t[i + j] = '?'
            }
            res.add(i)
            done[i] = true
        }
        
        var changed = true
        while (changed) {
            changed = false
            for (i in 0..(n - m)) {
                if (!done[i] && canStamp(i)) {
                    doStamp(i)
                    changed = true
                }
            }
        }
        
        return if (t.all { it == '?' }) res.reversed().toIntArray() else IntArray(0)
    }
}

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

Задача: 836. Rectangle Overlap
Сложность: easy

Прямоугольник, выровненный по осям, представляется в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2, y2) — координата его верхнего правого угла. Его верхняя и нижняя грани параллельны оси X, а левая и правая грани параллельны оси Y.

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

Даны два выровненных по осям прямоугольника rec1 и rec2, вернуть true, если они перекрываются, в противном случае вернуть false.

Пример:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

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

1⃣Рассчитайте ширину пересечения: пересечение по оси x положительно, если min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]).

2⃣Рассчитайте высоту пересечения: пересечение по оси y положительно, если min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]).

3⃣Если и ширина, и высота пересечения положительны, прямоугольники перекрываются.

😎 Решение:

class Solution {
    fun isRectangleOverlap(rec1: IntArray, rec2: IntArray): Boolean {
        return minOf(rec1[2], rec2[2]) > maxOf(rec1[0], rec2[0]) &&
               minOf(rec1[3], rec2[3]) > maxOf(rec1[1], rec2[1])
    }

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

Задача: 100. Same Tree
Сложность: easy

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.

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

Пример:

Input: p = [1,2,3], q = [1,2,3]  
Output: true  

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

1⃣Проверяем, равны ли оба узла null

2⃣Если только один из узлов null, деревья не равны

3⃣Сравниваем значения текущих узлов и рекурсивно проверяем дочерние узлы

😎 Решение:

class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        if (p == null && q == null) {
            return true
        }
        if (p == null || q == null) {
            return false
        }
        if (p.value != q.value) {
            return false
        }
        return isSameTree(p.right, q.right) && isSameTree(p.left, q.left)
    }
}

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

Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

2⃣Пройти по каждому слову в предложении и найти все возможные синонимы.
Сгенерировать все возможные комбинации предложений.

3⃣Отсортировать полученные предложения лексикографически.

😎 Решение:

class Solution {
    fun generateSentences(synonyms: List<List<String>>, text: String): List<String> {
        val graph = mutableMapOf<String, MutableSet<String>>()
        for (pair in synonyms) {
            graph.getOrPut(pair[0]) { mutableSetOf() }.add(pair[1])
            graph.getOrPut(pair[1]) { mutableSetOf() }.add(pair[0])
        }

        val words = text.split(" ")
        val synonymGroups = words.map { findSynonyms(graph, it) }

        val sentences = mutableListOf<String>()
        generate(sentences, synonymGroups, StringBuilder(), 0)
        return sentences.sorted()
    }

    private fun findSynonyms(graph: Map<String, Set<String>>, word: String): List<String> {
        val synonyms = mutableSetOf<String>()
        val stack = ArrayDeque<String>()
        stack.push(word)
        while (stack.isNotEmpty()) {
            val w = stack.pop()
            if (synonyms.add(w)) {
                stack.addAll(graph[w] ?: emptySet())
            }
        }
        return synonyms.toList().sorted()
    }

    private fun generate(sentences: MutableList<String>, groups: List<List<String>>, sentence: StringBuilder, index: Int) {
        if (index == groups.size) {
            sentences.add(sentence.toString().trim())
            return
        }
        val len = sentence.length
        for (word in groups[index]) {
            sentence.append(" ").append(word)
            generate(sentences, groups, sentence, index + 1)
            sentence.setLength(len)
        }
    }
}

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

Задача: 968. Binary Tree Cameras
Сложность: hard

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

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

Пример:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

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

1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.

2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.

3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.

😎 Решение:

class Solution {
    fun minCameraCover(root: TreeNode?): Int {
        val ans = solve(root)
        return minOf(ans[1], ans[2])
    }

    private fun solve(node: TreeNode?): IntArray {
        if (node == null) {
            return intArrayOf(0, 0, 99999)
        }

        val L = solve(node.left)
        val R = solve(node.right)
        val mL12 = minOf(L[1], L[2])
        val mR12 = minOf(R[1], R[2])

        val d0 = L[1] + R[1]
        val d1 = minOf(L[2] + mR12, R[2] + mL12)
        val d2 = 1 + minOf(L[0], mL12) + minOf(R[0], mR12)
        return intArrayOf(d0, d1, d2)
    }
}

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

Задача: 441. Arranging Coins
Сложность: easy

У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.

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

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

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

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

class Solution {
    fun arrangeCoins(n: Int): Int {
        return (Math.sqrt(2.0 * n + 0.25) - 0.5).toInt()
    }
}

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

Задача: 685. Redundant Connection II
Сложность: hard

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

Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.

Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.

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

Пример:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.

2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.

3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов.

😎 Решение:

class Solution {
    data class OrbitResult(val node: Int, val seen: Set<Int>)
    
    fun findRedundantDirectedConnection(edges: Array<IntArray>): IntArray {
        val N = edges.size
        val parent = mutableMapOf<Int, Int>()
        val candidates = mutableListOf<IntArray>()
        
        for (edge in edges) {
            if (parent.containsKey(edge[1])) {
                candidates.add(intArrayOf(parent[edge[1]]!!, edge[1]))
                candidates.add(edge)
            } else {
                parent[edge[1]] = edge[0]
            }
        }
        
        val root = orbit(1, parent).node
        if (candidates.isEmpty()) {
            val cycle = orbit(root, parent).seen
            var ans = intArrayOf(0, 0)
            for (edge in edges) {
                if (cycle.contains(edge[0]) && cycle.contains(edge[1])) {
                    ans = edge
                }
            }
            return ans
        }
        
        val children = mutableMapOf<Int, MutableList<Int>>()
        for ((v, pv) in parent) {
            children.computeIfAbsent(pv) { mutableListOf() }.add(v)
        }
        
        val seen = BooleanArray(N + 1)
        seen[0] = true
        val stack = ArrayDeque<Int>()
        stack.add(root)
        
        while (stack.isNotEmpty()) {
            val node = stack.removeLast()
            if (!seen[node]) {
                seen[node] = true
                children[node]?.let { stack.addAll(it) }
            }
        }
        
        for (b in seen) {
            if (!b) {
                return candidates[0]
            }
        }
        return candidates[1]
    }
    
    private fun orbit(node: Int, parent: Map<Int, Int>): OrbitResult {
        val seen = mutableSetOf<Int>()
        var node = node
        
        while (parent.containsKey(node) && !seen.contains(node)) {
            seen.add(node)
            node = parent[node]!!
        }
        
        return OrbitResult(node, seen)
    }
}

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

Задача: 482. License Key Formatting
Сложность: Easy

Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.

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

Верните переформатированный лицензионный ключ.

Пример:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

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

1⃣Инициализация
Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата.

2⃣Итерация по входной строке в обратном порядке
Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count.

3⃣Завершение
Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её.

😎 Решение:

class Solution {
    fun licenseKeyFormatting(s: String, k: Int): String {
        var count = 0
        val ans = StringBuilder()

        for (i in s.length - 1 downTo 0) {
            if (s[i] != '-') {
                ans.append(s[i].uppercaseChar())
                count++
                if (count == k) {
                    ans.append('-')
                    count = 0
                }
            }
        }

        if (ans.isNotEmpty() && ans.last() == '-') {
            ans.deleteCharAt(ans.length - 1)
        }

        return ans.reverse().toString()
    }
}

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

Задача: 314. Binary Tree Vertical Order Traversal
Сложность: medium

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

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

3⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам.

😎 Решение:

import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap

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

class Solution {
    fun verticalOrder(root: TreeNode?): List<List<Int>> {
        val columnTable = HashMap<Int, MutableList<Int>>()
        val queue: Queue<Pair<TreeNode?, Int>> = LinkedList()
        queue.add(Pair(root, 0))

        while (queue.isNotEmpty()) {
            val (node, column) = queue.poll()

            if (node != null) {
                if (!columnTable.containsKey(column)) {
                    columnTable[column] = ArrayList()
                }
                columnTable[column]?.add(node.`val`)

                queue.add(Pair(node.left, column - 1))
                queue.add(Pair(node.right, column + 1))
            }
        }

        return columnTable.keys.sorted().map { columnTable[it] ?: emptyList() }
    }
}

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

Задача: 508. Most Frequent Subtree Sum
Сложность: medium

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

Сумма поддерева узла определяется как сумма всех значений узлов, образованных поддеревом, укорененным в этом узле (включая сам узел).

Пример:

Input: root = [5,2,-3]
Output: [2,-3,4]

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

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

2⃣Обход дерева и вычисление сумм
Выполните обход дерева в порядке post-order. Используйте суммы поддеревьев левого и правого дочерних узлов для вычисления суммы текущего поддерева. Увеличьте частоту текущей суммы в sumFreq. Обновите maxFreq, если частота текущей суммы больше текущего maxFreq.

3⃣Сборка результата
Пройдитесь по sumFreq и добавьте все суммы с частотой, равной maxFreq, в массив maxFreqSums. Верните массив maxFreqSums.

😎 Решение:

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

class Solution {
    private val sumFreq = mutableMapOf<Int, Int>()
    private var maxFreq = 0
    
    private fun subtreeSum(root: TreeNode?): Int {
        if (root == null) return 0
        val leftSum = subtreeSum(root.left)
        val rightSum = subtreeSum(root.right)
        val currSum = root.`val` + leftSum + rightSum
        sumFreq[currSum] = sumFreq.getOrDefault(currSum, 0) + 1
        maxFreq = maxOf(maxFreq, sumFreq[currSum]!!)
        return currSum
    }
    
    fun findFrequentTreeSum(root: TreeNode?): IntArray {
        subtreeSum(root)
        return sumFreq.filter { it.value == maxFreq }.keys.toIntArray()
    }
}

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

Задача: 1319. Number of Operations to Make Network Connected
Сложность: medium

Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.

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

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

Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

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

1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1.

2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0.

3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:

Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.
Отметьте узел как посещенный.
Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.
Верните numberOfConnectedComponents - 1.

😎 Решение:

class Solution {
    private fun dfs(node: Int, adj: Map<Int, List<Int>>, visit: BooleanArray) {
        visit[node] = true
        adj[node]?.forEach { neighbor ->
            if (!visit[neighbor]) {
                visit[neighbor] = true
                dfs(neighbor, adj, visit)
            }
        }
    }

    fun makeConnected(n: Int, connections: Array<IntArray>): Int {
        if (connections.size < n - 1) {
            return -1
        }

        val adj = mutableMapOf<Int, MutableList<Int>>()
        connections.forEach { connection ->
            adj.computeIfAbsent(connection[0]) { mutableListOf() }.add(connection[1])
            adj.computeIfAbsent(connection[1]) { mutableListOf() }.add(connection[0])
        }

        var numberOfConnectedComponents = 0
        val visit = BooleanArray(n)
        for (i in 0 until n) {
            if (!visit[i]) {
                numberOfConnectedComponents++
                dfs(i, adj, visit)
            }
        }

        return numberOfConnectedComponents - 1
    }
}

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

Задача: 1365. How Many Numbers Are Smaller Than the Current Number
Сложность: easy

Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].

Верните ответ в виде массива.

Пример:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

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

1⃣Создание копии и сортировка массива:
Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего.

2⃣Поиск индекса каждого элемента:
Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i].

3⃣Формирование ответа:
Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего.

😎 Решение:

class Solution {
    fun smallerNumbersThanCurrent(nums: IntArray): IntArray {
        val sortedNums = nums.sorted()
        return nums.map { sortedNums.indexOf(it) }.toIntArray()
    }
}

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

Задача: 426. Convert Binary Search Tree to Sorted Doubly Linked List
Сложность: medium

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

Вы можете считать, что указатели "влево" и "вправо" аналогичны указателям на предшественника и последователя в двусвязном списке. Для кольцевого двусвязного списка предшественник первого элемента является последним элементом, а последователь последнего элемента является первым элементом.

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

Пример:

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

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

1⃣Инициализируйте первые и последние узлы как null.

2⃣Вызовите стандартную вспомогательную рекурсивную функцию helper(root):
Если узел не равен null:
Вызовите рекурсию для левого поддерева helper(node.left).
Если последний узел не равен null, свяжите последний узел и текущий узел.
Иначе инициализируйте первый узел.
Пометьте текущий узел как последний: last = node.
Вызовите рекурсию для правого поддерева helper(node.right).

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

😎 Решение:

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

class Solution {
    var first: Node? = null
    var last: Node? = null

    fun helper(node: Node?) {
        if (node != null) {
            helper(node.left)
            if (last != null) {
                last!!.right = node
                node.left = last
            } else {
                first = node
            }
            last = node
            helper(node.right)
        }
    }

    fun treeToDoublyList(root: Node?): Node? {
        if (root == null) return null
        helper(root)
        last!!.right = first
        first!!.left = last
        return first
    }
}

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

Задача: 273. Integer to English Words
Сложность: hard

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

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

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

1⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

2⃣Обработка сотен, тысяч, миллионов и миллиардов:
Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды).
Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999.

3⃣Формирование окончательного результата:
Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды).
Соединить все части в одну строку, удалив лишние пробелы.

😎 Решение:

class Solution {
    private val belowTwenty = arrayOf("", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen")
    private val tens = arrayOf("", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety")
    private val thousands = arrayOf("", "Thousand", "Million", "Billion")
    
    fun numberToWords(num: Int): String {
        if (num == 0) return "Zero"
        var num = num
        var result = ""
        var i = 0
        
        while (num > 0) {
            if (num % 1000 != 0) {
                result = helper(num % 1000) + thousands[i] + " " + result
            }
            num /= 1000
            i++
        }
        return result.trim()
    }
    
    private fun helper(num: Int): String {
        if (num == 0) return ""
        else if (num < 20) return belowTwenty[num] + " "
        else if (num < 100) return tens[num / 10] + " " + helper(num % 10)
        else return belowTwenty[num / 100] + " Hundred " + helper(num % 100)
    }
}

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

Задача: 126.Word Ladder II
Сложность: hard

Найдите все самые короткие последовательности преобразований от beginWord до endWord, такие что:

Каждое слово отличается ровно одной буквой от предыдущего.

Все промежуточные слова содержатся в wordList.

beginWord может отсутствовать в wordList.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

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

1⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS).

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

3⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths.

😎 Решение:

class Solution {
    private val adjList = mutableMapOf<String, MutableList<String>>()
    private val shortestPaths = mutableListOf<List<String>>()

    private fun findNeighbors(word: String, wordSet: Set<String>): List<String> {
        val neighbors = mutableListOf<String>()
        word.toCharArray().forEachIndexed { index, oldChar ->
            ('a'..'z').forEach { c ->
                if (c != oldChar) {
                    val newWord = StringBuilder(word).apply { setCharAt(index, c) }.toString()
                    if (newWord in wordSet) neighbors.add(newWord)
                }
            }
        }
        return neighbors
    }

    private fun backtrack(source: String, destination: String, currPath: MutableList<String>) {
        if (source == destination) {
            shortestPaths.add(currPath.reversed())
            return
        }
        adjList[source]?.forEach { neighbor ->
            currPath.add(neighbor)
            backtrack(neighbor, destination, currPath)
            currPath.removeAt(currPath.size - 1)
        }
    }

    private fun bfs(beginWord: String, wordSet: MutableSet<String>) {
        val queue = ArrayDeque<String>().apply { add(beginWord) }
        wordSet.remove(beginWord)

        while (queue.isNotEmpty()) {
            repeat(queue.size) {
                val currWord = queue.removeFirst()
                findNeighbors(currWord, wordSet).forEach { neighbor ->
                    if (!adjList.getOrPut(neighbor) { mutableListOf() }.contains(currWord)) {
                        queue.add(neighbor)
                        adjList[neighbor]!!.add(currWord)
                    }
                }
            }
           
            queue.forEach { wordSet.remove(it) }
        }
    }

    fun findLadders(beginWord: String, endWord: String, wordList: List<String>): List<List<String>> {
        val wordSet = wordList.toMutableSet()
        bfs(beginWord, wordSet)
        backtrack(endWord, beginWord, mutableListOf(endWord))
        return shortestPaths
    }
}

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

Задача: 976. Largest Perimeter Triangle
Сложность: easy

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

Пример:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

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

1⃣Отсортируйте массив nums в порядке возрастания.

2⃣Для каждого элемента c в массиве, начиная с конца: Выберите два наибольших возможных значения a и b, которые находятся перед c в отсортированном массиве (т.е. значения, смежные с c). Проверьте, образуют ли a, b и c треугольник (условие треугольника: a + b > c). Если образуют, верните их сумму как периметр треугольника.

3⃣Если не удалось найти такие значения, верните 0.

😎 Решение:

class Solution {
    fun largestPerimeter(A: IntArray): Int {
        A.sort()
        for (i in A.size - 3 downTo 0) {
            if (A[i] + A[i + 1] > A[i + 2]) {
                return A[i] + A[i + 1] + A[i + 2]
            }
        }
        return 0
    }
}

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

Задача: 222. Count Complete Tree Nodes
Сложность: easy

Учитывая корень полного двоичного дерева, верните количество узлов в дереве. Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n. Разработайте алгоритм, который выполняется за время, меньшее, чем O(n).

Пример:

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

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

1⃣Инициализация и проверка пустоты дерева
Если дерево пустое, вернуть 0.
Рассчитать глубину дерева d.

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

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

😎 Решение:

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

class Solution {
    fun computeDepth(node: TreeNode?): Int {
        var node = node
        var d = 0
        while (node?.left != null) {
            node = node.left
            d++
        }
        return d
    }

    fun exists(idx: Int, d: Int, node: TreeNode?): Boolean {
        var left = 0
        var right = Math.pow(2.0, d.toDouble()).toInt() - 1
        var node = node
        for (i in 0 until d) {
            val pivot = left + (right - left) / 2
            if (idx <= pivot) {
                node = node?.left
                right = pivot
            } else {
                node = node?.right
                left = pivot + 1
            }
        }
        return node != null
    }

    fun countNodes(root: TreeNode?): Int {
        if (root == null) return 0
        val d = computeDepth(root)
        if (d == 0) return 1

        var left = 1
        var right = Math.pow(2.0, d.toDouble()).toInt() - 1
        while (left <= right) {
            val pivot = left + (right - left) / 2
            if (exists(pivot, d, root)) left = pivot + 1
            else right = pivot - 1
        }

        return Math.pow(2.0, d.toDouble()).toInt() - 1 + left
    }
}

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

Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
Сложность: hard

Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:

maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
      if (maximum_value  < arr[i]){
           maximum_value  = arr[i]
           maximum_index = i
           search_cost = search_cost + 1
      }
}
return maximum_index

Вам необходимо построить массив arr, который имеет следующие свойства:
arr содержит ровно n целых чисел.
1 <= arr[i] <= m, где (0 <= i < n).
После применения указанного алгоритма к arr, значение search_cost равно k.
Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7.

Пример:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

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

1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1.

2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений.

3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи.

😎 Решение:

class Solution {
    fun numOfArrays(n: Int, m: Int, k: Int): Int {
        val MOD = 1_000_000_007
        val dp = Array(n + 1) { Array(m + 1) { IntArray(k + 1) } }
        
        for (num in 0..m) {
            dp[n][num][0] = 1
        }
        
        for (i in n - 1 downTo 0) {
            for (maxSoFar in m downTo 0) {
                for (remain in 0..k) {
                    var ans = 0
                    for (num in 1..maxSoFar) {
                        ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD
                    }
                    
                    if (remain > 0) {
                        for (num in (maxSoFar + 1)..m) {
                            ans = (ans + dp[i + 1][num][remain - 1]) % MOD
                        }
                    }
                    
                    dp[i][maxSoFar][remain] = ans
                }
            }
        }
        
        return dp[0][0][k]
    }
}

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

Задача: 1248. Count Number of Nice Subarrays
Сложность: medium

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

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

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

1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.

2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.

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

😎 Решение:

class Solution {
    fun numberOfSubarrays(nums: IntArray, k: Int): Int {
        return atMost(nums, k) - atMost(nums, k - 1)
    }

    private fun atMost(nums: IntArray, k: Int): Int {
        var res = 0
        var left = 0
        var count = 0
        for (right in nums.indices) {
            if (nums[right] % 2 == 1) count++
            while (count > k) {
                if (nums[left++] % 2 == 1) count--
            }
            res += right - left + 1
        }
        return res
    }
}

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

Задача: 949. Largest Time for Given Digits
Сложность: medium

Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка.

Пример:

Input: arr = [1,2,3,4]
Output: "23:41"

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

1⃣Перебрать все возможные перестановки массива arr.

2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.

3⃣Алгоритм
Перебрать все возможные перестановки массива arr.
Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.
Вернуть найденное время в формате "HH
". Если допустимое время не найдено, вернуть пустую строку.

😎 Решение:

class Solution {
    fun largestTimeFromDigits(arr: IntArray): String {
        arr.sort()
        var maxTime = -1
        do {
            val hours = arr[0] * 10 + arr[1]
            val minutes = arr[2] * 10 + arr[3]
            if (hours < 24 && minutes < 60) {
                maxTime = maxOf(maxTime, hours * 60 + minutes)
            }
        } while (nextPermutation(arr))
        
        if (maxTime == -1) {
            return ""
        }
        
        return String.format("%02d:%02d", maxTime / 60, maxTime % 60)
    }
    
    private fun nextPermutation(arr: IntArray): Boolean {
        val n = arr.size
        var i = n - 2
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--
        }
        if (i < 0) {
            return false
        }
        var j = n - 1
        while (arr[j] <= arr[i]) {
            j--
        }
        arr[i] = arr[j].also { arr[j] = arr[i] }
        arr.reverse(i + 1, n)
        return true
    }
}

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