Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter(words: Array<String>) {
    private val prefixSuffixMap = mutableMapOf<String, Int>()
    
    init {
        for ((index, word) in words.withIndex()) {
            val length = word.length
            for (prefixLength in 1..length) {
                for (suffixLength in 1..length) {
                    val prefix = word.substring(0, prefixLength)
                    val suffix = word.substring(length - suffixLength)
                    val key = "$prefix#$suffix"
                    prefixSuffixMap[key] = index
                }
            }
        }
    }
    
    fun f(pref: String, suff: String): Int {
        val key = "$pref#$suff"
        return prefixSuffixMap[key] ?: -1
    }
}

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

Задача: 1029. Two City Scheduling
Сложность: medium

Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

1⃣Вычислить разницу стоимости:
Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B.

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

3⃣Назначить города:
Первые n человек из отсортированного списка отправьте в город A.
Оставшихся n человек отправьте в город B.

😎 Решение:

class Solution {
    fun twoCitySchedCost(costs: Array<IntArray>): Int {
        costs.sortBy { it[0] - it[1] }
        var totalCost = 0
        val n = costs.size / 2
        for (i in 0 until n) {
            totalCost += costs[i][0]
            totalCost += costs[i + n][1]
        }
        return totalCost
    }
}

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

Задача: 128. Longest Consecutive Sequence
Сложность: Medium

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

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

Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

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

2⃣Обработка чисел в массиве:
Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).
Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.
Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3⃣Завершение обработки и возврат результата:
В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).
Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎 Решение:

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        var longestStreak = 0
        val numSet = nums.toSet()

        for (num in numSet) {
            if (num - 1 !in numSet) {
                var currentNum = num
                var currentStreak = 1

                while (currentNum + 1 in numSet) {
                    currentNum += 1
                    currentStreak += 1
                }

                longestStreak = maxOf(longestStreak, currentStreak)
            }
        }
        return longestStreak
    }
}

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

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

Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.

На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.

Верните количество лампочек, которые будут включены после n раундов.

Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

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

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

3⃣Подсчет включенных лампочек
Количество лампочек, которые будут включены после n раундов.

😎 Решение:

class Solution {
    fun bulbSwitch(n: Int): Int {
        return kotlin.math.sqrt(n.toDouble()).toInt()
    }
}

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

Задача: 842. Split Array into Fibonacci Sequence
Сложность: medium

Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.

Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.

Пример:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

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

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

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

3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор.

😎 Решение:

class Solution {
    fun splitIntoFibonacci(S: String): List<Int> {
        val N = S.length
        for (i in 0 until minOf(10, N)) {
            if (S[0] == '0' && i > 0) break
            val a = S.substring(0, i + 1).toLong()
            if (a >= Int.MAX_VALUE) break

            for (j in i + 1 until minOf(i + 10, N)) {
                if (S[i + 1] == '0' && j > i + 1) break
                val b = S.substring(i + 1, j + 1).toLong()
                if (b >= Int.MAX_VALUE) break

                val fib = mutableListOf(a.toInt(), b.toInt())
                var k = j + 1
                while (k < N) {
                    val nxt = fib[fib.size - 2] + fib[fib.size - 1]
                    if (nxt > Int.MAX_VALUE) break
                    val nxtS = nxt.toString()
                    if (S.substring(k).startsWith(nxtS)) {
                        k += nxtS.length
                        fib.add(nxt.toInt())
                    } else {
                        break
                    }
                }
                if (fib.size >= 3) return fib
            }
        }
        return emptyList()
    }
}

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

Задача: 129. Sum Root to Leaf Numbers
Сложность: Medium

Вам дан корень бинарного дерева, содержащего только цифры от 0 до 9.

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

Например, путь от корня до листа 1 -> 2 -> 3 представляет число 123.
Верните общую сумму всех чисел от корня до листа. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Листовой узел — это узел без детей.

Пример:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

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

1⃣Создайте переменные для хранения суммы чисел (rootToLeaf) и текущего числа (currNumber), а также стек для обхода дерева, начиная с корневого узла.

2⃣Используйте стек для глубинного обхода дерева (DFS), обновляя currNumber путём умножения на 10 и добавления значения узла. Для каждого листа добавляйте currNumber к rootToLeaf.

3⃣По завершении обхода всех узлов возвращайте rootToLeaf, содержащую сумму всех чисел от корня до листьев дерева.

😎 Решение:

class Solution {
    fun sumNumbers(root: TreeNode?): Int {
        var rootToLeaf = 0
        var currNumber = 0
        var node = root

        while (node != null) {
            if (node.left != null) {
                var (predecessor, steps) = findPredecessor(node)
                if (predecessor.right == null) {
                    currNumber = currNumber * 10 + node.`val`
                    predecessor.right = node
                    node = node.left
                } else {
                    if (predecessor.left == null) rootToLeaf += currNumber
                    currNumber /= Math.pow(10.0, steps.toDouble()).toInt()
                    predecessor.right = null
                    node = node.right
                }
            } else {
                currNumber = currNumber * 10 + node.`val`
                if (node.right == null) rootToLeaf += currNumber
                node = node.right
            }
        }
        return rootToLeaf
    }

    private fun findPredecessor(node: TreeNode): Pair<TreeNode, Int> {
        var predecessor = node.left
        var steps = 1
        while (predecessor!!.right != null && predecessor.right !== node) {
            predecessor = predecessor.right
            steps++
        }
        return Pair(predecessor, steps)
    }
}

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

Задача: 398. Random Pick Index
Сложность: medium

Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.

Пример:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

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

1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования.

2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным.

3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса.

😎 Решение:

class Solution(private val nums: IntArray) {
    fun pick(target: Int): Int {
        var count = 0
        var result = -1
        for (i in nums.indices) {
            if (nums[i] == target) {
                count++
                if ((1..count).random() == count) {
                    result = i
                }
            }
        }
        return result
    }
}

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

Задача: 224. Basic Calculator
Сложность: hard

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

Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

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

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

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

😎 Решение:

class Solution {

    fun evaluateExpr(stack: MutableList<Any>): Int {
        if (stack.isEmpty() || stack.last() !is Int) {
            stack.add(0)
        }

        var res = stack.removeAt(stack.size - 1) as Int

        while (stack.isNotEmpty() && stack.last() != ')') {
            val sign = stack.removeAt(stack.size - 1) as Char
            if (sign == '+') {
                res += stack.removeAt(stack.size - 1) as Int
            } else {
                res -= stack.removeAt(stack.size - 1) as Int
            }
        }
        return res
    }

    fun calculate(s: String): Int {
        var operand = 0
        var n = 0
        val stack = mutableListOf<Any>()

        for (i in s.length - 1 downTo 0) {
            val ch = s[i]

            if (ch.isDigit()) {
                operand = Math.pow(10.0, n.toDouble()).toInt() * (ch - '0') + operand
                n += 1
            } else if (ch != ' ') {
                if (n != 0) {
                    stack.add(operand)
                    n = 0
                    operand = 0
                }
                if (ch == '(') {
                    val res = evaluateExpr(stack)
                    stack.removeAt(stack.size - 1)
                    stack.add(res)
                } else {
                    stack.add(ch)
                }
            }
        }

        if (n != 0) {
            stack.add(operand)
        }

        return evaluateExpr(stack)
    }
}

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

Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium

У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.

Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

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

1⃣Начните с:

Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент.
Сумма чисел на предыдущих кубиках currSum равна 0.
Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию.

2⃣Базовые случаи:

Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target.

3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum.

😎 Решение:

class Solution {
    val MOD = 1_000_000_007

    fun waysToTarget(memo: Array<IntArray>, diceIndex: Int, n: Int, currSum: Int, target: Int, k: Int): Int {
        if (diceIndex == n) {
            return if (currSum == target) 1 else 0
        }
        if (memo[diceIndex][currSum] != -1) {
            return memo[diceIndex][currSum]
        }

        var ways = 0
        for (i in 1..minOf(k, target - currSum)) {
            ways = (ways + waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % MOD
        }
        memo[diceIndex][currSum] = ways
        return ways
    }

    fun numRollsToTarget(n: Int, k: Int, target: Int): Int {
        val memo = Array(n + 1) { IntArray(target + 1) { -1 } }
        return waysToTarget(memo, 0, n, 0, target, k)
    }
}

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

Задача: 758. Bold Words in String
Сложность: medium

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

1⃣Создайте массив для хранения флагов, указывающих, какие символы в строке a должны быть выделены жирным шрифтом.

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

fun addBoldTags(keywords: Array<String>, s: String): String {
    val n = s.length
    val bold = BooleanArray(n)
    
    for (word in keywords) {
        var start = s.indexOf(word)
        while (start != -1) {
            for (i in start until start + word.length) {
                bold[i] = true
            }
            start = s.indexOf(word, start + 1)
        }
    }
    
    val result = StringBuilder()
    var i = 0
    while (i < n) {
        if (bold[i]) {
            result.append("<b>")
            while (i < n && bold[i]) {
                result.append(s[i])
                i++
            }
            result.append("</b>")
        } else {
            result.append(s[i])
            i++
        }
    }
    
    return result.toString()
}

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

Задача: 1024. Video Stitching
Сложность: medium

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.

Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

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

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

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

😎 Решение:

class Solution {
    fun videoStitching(clips: Array<IntArray>, T: Int): Int {
        clips.sortWith(compareBy({ it[0] }, { -it[1] }))
        var end = -1
        var end2 = 0
        var res = 0
        
        for (clip in clips) {
            if (end2 >= T || clip[0] > end2) break
            if (end < clip[0] && clip[0] <= end2) {
                res++
                end = end2
            }
            end2 = maxOf(end2, clip[1])
        }
        return if (end2 >= T) res else -1
    }
}

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

Задача: 1035. Uncrossed Lines
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.

Пример:

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2

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

1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS):
Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2.

2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.

3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].

😎 Решение:

class Solution {
    fun maxUncrossedLines(nums1: IntArray, nums2: IntArray): Int {
        val m = nums1.size
        val n = nums2.size
        val dp = Array(m + 1) { IntArray(n + 1) }

        for (i in 1..m) {
            for (j in 1..n) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }

        return dp[m][n]
    }
}

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

Задача: 728. Self Dividing Numbers
Сложность: hard

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

1⃣Переберите все числа в диапазоне от left до right.

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

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

😎 Решение:

fun selfDividingNumbers(left: Int, right: Int): List<Int> {
    fun isSelfDividing(num: Int): Boolean {
        var n = num
        while (n > 0) {
            val digit = n % 10
            if (digit == 0 || num % digit != 0) {
                return false
            }
            n /= 10
        }
        return true
    }
    
    val result = mutableListOf<Int>()
    for (num in left..right) {
        if (isSelfDividing(num)) {
            result.add(num)
        }
    }
    return result
}

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

Задача: 103. Binary Tree Zigzag Level Order Traversal
Сложность: medium

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

Пример:

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

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

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

2⃣Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди).

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

😎 Решение:

import java.util.*

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

class Solution {
    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        if (root == null) {
            return result
        }

        val nodeQueue = ArrayDeque<TreeNode?>()
        nodeQueue.add(root)
        nodeQueue.add(null)
        var isOrderLeft = true
        val levelList = ArrayDeque<Int>()

        while (nodeQueue.isNotEmpty()) {
            val currentNode = nodeQueue.poll()

            if (currentNode != null) {
                if (isOrderLeft) {
                    levelList.add(currentNode.value)
                } else {
                    levelList.addFirst(currentNode.value)
                }

                currentNode.left?.let {
                    nodeQueue.add(it)
                }
                currentNode.right?.let {
                    nodeQueue.add(it)
                }
            } else {
                result.add(ArrayList(levelList))
                if (nodeQueue.isNotEmpty()) {
                    nodeQueue.add(null)
                }
                levelList.clear()
                isOrderLeft = !isOrderLeft
            }
        }

        return result
    }
}

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

Задача: 415. Add Strings
Сложность: easy

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

Input: num1 = "11", num2 = "123"
Output: "134"

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

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

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

3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число.

😎 Решение:

fun thirdMax(nums: IntArray): Int {
    var first: Int? = null
    var second: Int? = null
    var third: Int? = null
    
    for (num in nums) {
        if (num == first || num == second || num == third) {
            continue
        }
        when {
            first == null || num > first -> {
                third = second
                second = first
                first = num
            }
            second == null || num > second -> {
                third = second
                second = num
            }
            third == null || num > third -> {
                third = num
            }
        }
    }
    
    return third ?: first!!
}

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

Задача: 820. Short Encoding of Words
Сложность: medium

Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:

words.length == indices.length
Опорная строка s заканчивается символом '#'.
Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].
Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.

Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

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

1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.

2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.

3⃣В конце вернем длину полученной опорной строки.

😎 Решение:

class Solution {
    fun minimumLengthEncoding(words: Array<String>): Int {
        val good = words.toMutableSet()
        for (word in words) {
            for (k in 1 until word.length) {
                good.remove(word.substring(k))
            }
        }
        return good.sumOf { it.length + 1 }
    }

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

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

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