Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

fun minSubsequences(source: String, target: String): Int {
    var subsequencesCount = 0
    var targetIndex = 0

    while (targetIndex < target.length) {
        var sourceIndex = 0
        subsequencesCount++
        val startIndex = targetIndex

        while (sourceIndex < source.length && targetIndex < target.length) {
            if (source[sourceIndex] == target[targetIndex]) {
                targetIndex++
            }
            sourceIndex++
        }

        if (targetIndex == startIndex) {
            return -1
        }
    }

    return subsequencesCount
}

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

Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

1⃣Создайте функцию для вычисления оценки слова.

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

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

😎 Решение:

class Solution {
    fun maxScoreWords(words: Array<String>, letters: CharArray, score: IntArray): Int {
        val letterCount = mutableMapOf<Char, Int>()
        letters.forEach { letterCount[it] = letterCount.getOrDefault(it, 0) + 1 }

        fun wordScore(word: String): Int {
            var total = 0
            for (ch in word) {
                total += score[ch - 'a']
            }
            return total
        }

        fun canFormWord(word: String, letterCount: Map<Char, Int>): Boolean {
            val count = mutableMapOf<Char, Int>()
            for (ch in word) {
                count[ch] = count.getOrDefault(ch, 0) + 1
                if (count[ch]!! > letterCount.getOrDefault(ch, 0)) {
                    return false
                }
            }
            return true
        }

        var maxScore = 0
        val n = words.size
        for (i in 1 until (1 shl n)) {
            var currScore = 0
            val usedLetters = mutableMapOf<Char, Int>()
            var valid = true
            for (j in 0 until n) {
                if (i and (1 shl j) != 0) {
                    val word = words[j]
                    if (canFormWord(word, letterCount)) {
                        currScore += wordScore(word)
                        for (ch in word) {
                            usedLetters[ch] = usedLetters.getOrDefault(ch, 0) + 1
                        }
                    } else {
                        valid = false
                        break
                    }
                }
            }
            if (valid) {
                maxScore = maxOf(maxScore, currScore)
            }
        }

        return maxScore
    }
}

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

Задача: 846. Hand of Straights
Сложность: medium

У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.

Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.

Пример:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

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

1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.

2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.

3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.

😎 Решение:

class Solution {
    fun isNStraightHand(hand: IntArray, groupSize: Int): Boolean {
        if (hand.size % groupSize != 0) {
            return false
        }

        val cardCount = hand.groupingBy { it }.eachCount().toMutableMap()
        val sortedHand = hand.sorted()

        for (card in sortedHand) {
            if (cardCount[card] == 0) continue

            for (nextCard in card until card + groupSize) {
                if (cardCount[nextCard] ?: 0 == 0) return false
                cardCount[nextCard] = cardCount[nextCard]!! - 1
            }
        }

        return true
    }
}

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

Задача: 1358. Number of Substrings Containing All Three Characters
Сложность: medium

Дана строка s, состоящая только из символов a, b и c.

Верните количество подстрок, содержащих хотя бы одно вхождение всех этих символов a, b и c.

Пример:

Input: s = "abc"
Output: 1

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

1⃣Инициализация указателей и счетчиков:
Создайте три указателя i, j, и count для отслеживания текущего положения в строке и подсчета подстрок. Используйте словарь для подсчета вхождений символов a, b, и c.

2⃣Расширение окна:
Перемещайте правый указатель j по строке и увеличивайте счетчики символов в словаре. Как только все три символа (a, b, и c) присутствуют в текущем окне, начинайте уменьшать левый указатель i.

3⃣Уменьшение окна и подсчет подстрок:
Для каждого сдвига i вправо, проверяйте наличие всех символов в текущем окне. Если все символы присутствуют, добавьте количество подстрок, заканчивающихся в позиции j, к общему счету. Сдвигайте i вправо до тех пор, пока условие выполнения не нарушится.
Верните итоговое количество подстрок.

😎 Решение:

class Solution {
    fun numberOfSubstrings(s: String): Int {
        val charCount = mutableMapOf('a' to 0, 'b' to 0, 'c' to 0)
        var count = 0
        var i = 0
        
        for (j in s.indices) {
            charCount[s[j]] = charCount.getOrDefault(s[j], 0) + 1
            
            while (charCount['a']!! > 0 && charCount['b']!! > 0 && charCount['c']!! > 0) {
                count += s.length - j
                charCount[s[i]] = charCount[s[i]]!! - 1
                i++
            }
        }
        
        return count
    }
}

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

Задача: 73. Set Matrix Zeroes
Сложность: medium

Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца.

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

Пример:

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

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

1⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0.

2⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки.

3⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми.

😎 Решение:

class Solution {
    fun setZeroes(matrix: Array<IntArray>) {
        var isCol = false
        val R = matrix.size
        val C = matrix[0].size
        
        for (i in 0 until R) {
            if (matrix[i][0] == 0) {
                isCol = true
            }
            for (j in 1 until C) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0
                    matrix[i][0] = 0
                }
            }
        }
        
        for (i in 1 until R) {
            for (j in 1 until C) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0
                }
            }
        }
        
        if (matrix[0][0] == 0) {
            for (j in 0 until C) {
                matrix[0][j] = 0
            }
        }
        
        if (isCol) {
            for (i in 0 until R) {
                matrix[i][0] = 0
            }
        }
    }
}

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

Задача: 658. Find K Closest Elements
Сложность: easy

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

Целое число a ближе к x, чем целое число b, если:

|a - x| < |b - x|, или
|a - x| == |b - x| и a < b.

Пример:

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

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

1⃣Бинарный поиск:
Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска.

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

3⃣Сортировка:
Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован).

😎 Решение:

class Solution {
    fun findClosestElements(arr: List<Int>, k: Int, x: Int): List<Int> {
        var left = 0
        var right = arr.size - k

        while (left < right) {
            val mid = (left + right) / 2
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1
            } else {
                right = mid
            }
        }

        return arr.subList(left, left + k)
    }
}

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

Задача: 786. K-th Smallest Prime Fraction
Сложность: medium

Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k.

Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j].

Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

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

1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей.

2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью.

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

😎 Решение:

import java.util.PriorityQueue

class Solution {
    fun kthSmallestPrimeFraction(arr: IntArray, k: Int): IntArray {
        val pq = PriorityQueue(compareBy<Pair<Double, IntArray>> { it.first })

        for (i in 0 until arr.size - 1) {
            pq.add(Pair(arr[i].toDouble() / arr[arr.size - 1], intArrayOf(i, arr.size - 1)))
        }

        repeat(k - 1) {
            val (_, indices) = pq.poll()
            val (numeratorIndex, denominatorIndex) = indices
            val newDenominatorIndex = denominatorIndex - 1
            if (newDenominatorIndex > numeratorIndex) {
                pq.add(Pair(arr[numeratorIndex].toDouble() / arr[newDenominatorIndex], intArrayOf(numeratorIndex, newDenominatorIndex)))
            }
        }

        val (_, result) = pq.poll()
        return intArrayOf(arr[result[0]], arr[result[1]])
    }
}

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

Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.

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

😎 Решение:

class Solution {
    fun sortItems(n: Int, m: Int, group: IntArray, beforeItems: List<List<Int>>): IntArray {
        var groupId = m
        for (i in 0 until n) if (group[i] == -1) group[i] = groupId++

        val itemGraph = mutableMapOf<Int, MutableList<Int>>()
        val groupGraph = mutableMapOf<Int, MutableList<Int>>()
        val itemIndegree = IntArray(n)
        val groupIndegree = IntArray(groupId)
        for (i in 0 until n) itemGraph[i] = mutableListOf()
        for (i in 0 until groupId) groupGraph[i] = mutableListOf()

        for (curr in 0 until n) {
            for (prev in beforeItems[curr]) {
                itemGraph[prev]!!.add(curr)
                itemIndegree[curr]++
                if (group[curr] != group[prev]) {
                    groupGraph[group[prev]]!!.add(group[curr])
                    groupIndegree[group[curr]]++
                }
            }
        }

        val itemOrder = topologicalSort(itemGraph, itemIndegree)
        val groupOrder = topologicalSort(groupGraph, groupIndegree)
        if (itemOrder.isEmpty() || groupOrder.isEmpty()) return intArrayOf()

        val orderedGroups = mutableMapOf<Int, MutableList<Int>>()
        for (item in itemOrder) orderedGroups.computeIfAbsent(group[item]) { mutableListOf() }.add(item)

        val answerList = mutableListOf<Int>()
        for (groupIndex in groupOrder) answerList.addAll(orderedGroups.getOrDefault(groupIndex, mutableListOf()))

        return answerList.toIntArray()
    }

    private fun topologicalSort(graph: Map<Int, List<Int>>, indegree: IntArray): List<Int> {
        val visited = mutableListOf<Int>()
        val stack = ArrayDeque<Int>()
        for (key in graph.keys) if (indegree[key] == 0) stack.add(key)

        while (stack.isNotEmpty()) {
            val curr = stack.removeLast()
            visited.add(curr)
            for (next in graph[curr]!!) if (--indegree[next] == 0) stack.add(next)
        }

        return if (visited.size == graph.size) visited else emptyList()
    }
}

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

Задача: 1235. Maximum Profit in Job Scheduling
Сложность: hard

У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X.

Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

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

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

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

😎 Решение:

class Solution {
    fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
        val jobs = startTime.indices.map { Triple(endTime[it], startTime[it], profit[it]) }.sortedBy { it.first }

        val dp = mutableListOf(Pair(0, 0))

        for ((e, s, p) in jobs) {
            val i = dp.binarySearch { if (it.first <= s) -1 else 1 }
            val newProfit = dp[if (i < 0) -i - 2 else i].second + p
            if (newProfit > dp.last().second) {
                dp.add(Pair(e, newProfit))
            }
        }

        return dp.last().second
    }
}

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

Задача: 81. Search in Rotated Sorted Array II
Сложность: medium

В массиве целых чисел nums, отсортированном в неубывающем порядке (не обязательно содержащем уникальные значения), произведена ротация в неизвестном индексе поворота k (0 <= k < nums.length). В результате массив принимает вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (нумерация с 0). Например, массив [0,1,2,4,4,4,5,6,6,7] может быть повернут в индексе 5 и превратиться в [4,5,6,6,7,0,1,2,4,4].

Для данного массива nums после ротации и целого числа target необходимо вернуть true, если target присутствует в nums, и false в противном случае.

Необходимо сократить количество операций поиска настолько, насколько это возможно.

Пример:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

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

1⃣Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска.

2⃣Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске:
Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end].
Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid).
Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска.
Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска.

3⃣Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно.

😎 Решение:

class Solution {
    fun search(nums: IntArray, target: Int): Boolean {
        val n = nums.size
        if (n == 0) return false
        var end = n - 1
        var start = 0

        while (start <= end) {
            val mid = start + (end - start) / 2
            if (nums[mid] == target) return true

            if (!isBinarySearchHelpful(nums, start, nums[mid])) {
                start += 1
                continue
            }

            val pivotArray = existsInFirst(nums, start, nums[mid])
            val targetArray = existsInFirst(nums, start, target)

            if (pivotArray xor targetArray) {
                if (pivotArray) {
                    start = mid + 1
                } else {
                    end = mid - 1
                }
            } else {
                if (nums[mid] < target) {
                    start = mid + 1
                } else {
                    end = mid - 1
                }
            }
        }
        return false
    }

    private fun isBinarySearchHelpful(nums: IntArray, start: Int, element: Int): Boolean {
        return nums[start] != element
    }

    private fun existsInFirst(nums: IntArray, start: Int, element: Int): Boolean {
        return nums[start] <= element
    }
}

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

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

Дано целое число n, верните true, если и только если оно является числом Армстронга.

k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.

Пример:

Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.

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

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

2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n.
Инициализируйте переменную result для хранения результата.
Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру.

3⃣Верните true, если результат равен исходному числу n.

😎 Решение:

class Solution {
    fun getSumOfKthPowerOfDigits(n: Int, k: Int): Int {
        var result = 0
        var number = n
        while (number != 0) {
            val digit = number % 10
            result += Math.pow(digit.toDouble(), k.toDouble()).toInt()
            number /= 10
        }
        return result
    }

    fun isArmstrong(n: Int): Boolean {
        val length = n.toString().length
        return getSumOfKthPowerOfDigits(n, length) == n
    }
}

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

Задача: 155. Min Stack
Сложность: medium

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

Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.

Вы должны реализовать решение с временной сложностью O(1) для каждой функции.

Пример:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

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

1⃣Создайте структуру данных, которая будет использоваться для хранения элементов стека. Эта структура должна поддерживать не только обычные операции стека, но и быстрый доступ к минимальному элементу.
Инициализируйте стек с помощью конструктора MinStack(), который подготовит все необходимые структуры данных для дальнейшей работы.

2⃣Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.

3⃣Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.

😎 Решение:

class MinStack() {
    private val stack = mutableListOf<Pair<Int, Int>>()

    fun push(x: Int) {
        val currentMin = stack.lastOrNull()?.second ?: x
        stack.add(Pair(x, kotlin.math.min(x, currentMin)))
    }

    fun pop() {
        if (stack.isNotEmpty()) {
            stack.removeAt(stack.lastIndex)
        }
    }

    fun top(): Int? {
        return stack.lastOrNull()?.first
    }

    fun getMin(): Int? {
        return stack.lastOrNull()?.second
    }
}

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

Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

class Solution {
    fun fixedPoint(arr: IntArray): Int {
        var left = 0
        var right = arr.size - 1
        var answer = -1
        
        while (left <= right) {
            val mid = (left + right) / 2
            
            if (arr[mid] == mid) {
                answer = mid
                right = mid - 1
            } else if (arr[mid] < mid) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return answer
    }
}

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

Задача: 926. Flip String to Monotone Increasing
Сложность: medium

Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.

Пример:

Input: s = "00110"
Output: 1

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

1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0).

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

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

😎 Решение:

class Solution {
    fun minFlipsMonoIncr(s: String): Int {
        val n = s.length
        val left = IntArray(n + 1)
        val right = IntArray(n + 1)
        
        for (i in 0 until n) {
            left[i + 1] = left[i] + if (s[i] == '1') 1 else 0
        }
        
        for (i in n - 1 downTo 0) {
            right[i] = right[i + 1] + if (s[i] == '0') 1 else 0
        }
        
        var result = Int.MAX_VALUE
        for (i in 0..n) {
            result = minOf(result, left[i] + right[i])
        }
        return result
    }
}

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

Задача: 1302. Deepest Leaves Sum
Сложность: medium

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

Пример:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

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

1⃣Поместите корень в стек.

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

3⃣Верните deepest_sum.

😎 Решение:

class Solution {
    fun deepestLeavesSum(root: TreeNode?): Int {
        var deepestSum = 0
        var depth = 0
        val stack = ArrayDeque<Pair<TreeNode, Int>>()
        stack.push(Pair(root!!, 0))

        while (stack.isNotEmpty()) {
            val (node, currDepth) = stack.pop()

            if (node.left == null && node.right == null) {
                if (depth < currDepth) {
                    deepestSum = node.`val`
                    depth = currDepth
                } else if (depth == currDepth) {
                    deepestSum += node.`val`
                }
            } else {
                node.right?.let { stack.push(Pair(it, currDepth + 1)) }
                node.left?.let { stack.push(Pair(it, currDepth + 1)) }
            }
        }
        return deepestSum
    }
}

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

Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard

Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.

Пример:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

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

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

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

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

😎 Решение:

class Solution {
    fun minPushBox(grid: Array<CharArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
        
        fun isValid(x: Int, y: Int) = x in 0 until m && y in 0 until n && grid[x][y] != '#'
        
        var player = intArrayOf(0, 0)
        var box = intArrayOf(0, 0)
        var target = intArrayOf(0, 0)
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                when (grid[i][j]) {
                    'S' -> player = intArrayOf(i, j)
                    'B' -> box = intArrayOf(i, j)
                    'T' -> target = intArrayOf(i, j)
                }
            }
        }
        
        val queue = ArrayDeque<IntArray>()
        val visited = mutableSetOf<String>()
        
        queue.addLast(intArrayOf(player[0], player[1], box[0], box[1], 0))
        visited.add("${player[0]},${player[1]},${box[0]},${box[1]}")
        
        while (queue.isNotEmpty()) {
            val (px, py, bx, by, pushes) = queue.removeFirst()
            if (bx == target[0] && by == target[1]) {
                return pushes
            }
            for ((dx, dy) in directions) {
                val npx = px + dx
                val npy = py + dy
                if (isValid(npx, npy)) {
                    if (npx == bx && npy == by) {
                        val nbx = bx + dx
                        val nby = by + dy
                        if (isValid(nbx, nby) && visited.add("$npx,$npy,$nbx,$nby")) {
                            queue.addLast(intArrayOf(npx, npy, nbx, nby, pushes + 1))
                        }
                    } else if (visited.add("$npx,$npy,$bx,$by")) {
                        queue.addLast(intArrayOf(npx, npy, bx, by, pushes))
                    }
                }
            }
        }
        
        return -1
    }
}

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

Задача: 211. Design Add and Search Words Data Structure
Сложность: medium

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

Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

1⃣Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.

2⃣Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3⃣Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

class TrieNode {
    val children: MutableMap<Char, TrieNode> = HashMap()
    var isWord: Boolean = false
}

class WordDictionary {
    private val root: TrieNode = TrieNode()

    fun addWord(word: String) {
        var node = root
        for (ch in word) {
            node = node.children.computeIfAbsent(ch) { TrieNode() }
        }
        node.isWord = true
    }

    private fun searchInNode(word: String, node: TrieNode): Boolean {
        var node = node
        for (i in word.indices) {
            val ch = word[i]
            if (!node.children.containsKey(ch)) {
                if (ch == '.') {
                    for (child in node.children.values) {
                        if (searchInNode(word.substring(i + 1), child)) {
                            return true
                        }
                    }
                }
                return false
            } else {
                node = node.children[ch]!!
            }
        }
        return node.isWord
    }

    fun search(word: String): Boolean {
        return searchInNode(word, root)
    }
}

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

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

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

😎 Решение:

class Solution {
    fun minMalwareSpread(graph: Array<IntArray>, initial: IntArray): Int {
        val n = graph.size
        val visited = mutableSetOf<Int>()
        val components = mutableListOf<MutableSet<Int>>()
        
        fun dfs(node: Int) {
            val stack = mutableListOf(node)
            val component = mutableSetOf<Int>()
            while (stack.isNotEmpty()) {
                val u = stack.removeAt(stack.lastIndex)
                if (u !in visited) {
                    visited.add(u)
                    component.add(u)
                    for (v in 0 until n) {
                        if (graph[u][v] == 1 && v !in visited) {
                            stack.add(v)
                        }
                    }
                }
            }
            components.add(component)
        }
        
        for (i in 0 until n) {
            if (i !in visited) {
                dfs(i)
            }
        }
        
        val infectedInComponent = IntArray(components.size)
        val nodeToComponent = IntArray(n) { -1 }
        
        for ((idx, component) in components.withIndex()) {
            for (node in component) {
                nodeToComponent[node] = idx
                if (node in initial) {
                    infectedInComponent[idx]++
                }
            }
        }
        
        var minInfected = Int.MAX_VALUE
        var resultNode = initial.minOrNull()!!
        
        for (node in initial) {
            val componentIdx = nodeToComponent[node]
            if (infectedInComponent[componentIdx] == 1) {
                val componentSize = components[componentIdx].size
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize
                    resultNode = node
                }
            }
        }
        
        return resultNode
    }
}

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

Задача: 346. Moving Average from Data Stream
Сложность: easy

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

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

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

1⃣Инициализация:
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.

2⃣Добавление нового значения:
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.

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

😎 Решение:

class MovingAverage(size: Int) {
    private val size = size
    private val queue: ArrayDeque<Int> = ArrayDeque()
    private var sum = 0
    
    fun next(`val`: Int): Double {
        queue.addLast(`val`)
        sum += `val`
        if (queue.size > size) {
            sum -= queue.removeFirst()
        }
        return sum.toDouble() / queue.size
    }
}

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