Задача: 771. Jewels and Stones
Сложность: medium

Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.

Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".

Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

1⃣Создайте множество из строки jewels для быстрой проверки, является ли камень драгоценностью. Это позволит эффективно проверять принадлежность каждого камня к драгоценностям.

2⃣Инициализируйте счетчик для подсчета количества камней, которые являются драгоценностями. Пройдите по каждому символу в строке stones и проверьте, содержится ли этот символ в множестве jewels.

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

😎 Решение:

class Solution {
    fun numJewelsInStones(J: String, S: String): Int {
        var ans = 0
        for (s in S) {
            for (j in J) {
                if (j == s) {
                    ans++
                    break
                }
            }
        }
        return ans
    }
}

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

Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy

Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.

Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

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

1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.

2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.

3⃣Верните список answer.

😎 Решение:

class Solution {
    fun kidsWithCandies(candies: IntArray, extraCandies: Int): List<Boolean> {
        val maxCandies = candies.maxOrNull() ?: 0
        return candies.map { it + extraCandies >= maxCandies }
    }
}

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

Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

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

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

class Solution {
    fun numBusesToDestination(routes: Array<IntArray>, source: Int, target: Int): Int {
        if (source == target) return 0
        
        val adjList = mutableMapOf<Int, MutableList<Int>>()
        for (route in routes.indices) {
            for (stop in routes[route]) {
                adjList.computeIfAbsent(stop) { mutableListOf() }.add(route)
            }
        }
        
        val q = ArrayDeque<Int>()
        val vis = mutableSetOf<Int>()
        adjList[source]?.forEach { route ->
            q.add(route)
            vis.add(route)
        }
        
        var busCount = 1
        while (q.isNotEmpty()) {
            repeat(q.size) {
                val route = q.removeFirst()
                for (stop in routes[route]) {
                    if (stop == target) return busCount
                    adjList[stop]?.forEach { nextRoute ->
                        if (!vis.contains(nextRoute)) {
                            vis.add(nextRoute)
                            q.add(nextRoute)
                        }
                    }
                }
            }
            busCount++
        }
        return -1
    }
}

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

Задача: 472. Concatenated Words
Сложность: hard

Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.

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

Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

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

2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе.

3⃣Если узел word.length достижим от узла 0, добавить слово в ответ.

😎 Решение:

class Solution {
    private fun dfs(word: String, length: Int, visited: BooleanArray, dictionary: Set<String>): Boolean {
        if (length == word.length) return true
        if (visited[length]) return false
        visited[length] = true
        for (i in word.length - if (length == 0) 1 else 0 downTo length + 1) {
            if (dictionary.contains(word.substring(length, i)) && dfs(word, i, visited, dictionary)) {
                return true
            }
        }
        return false
    }

    fun findAllConcatenatedWordsInADict(words: List<String>): List<String> {
        val dictionary = words.toSet()
        val answer = mutableListOf<String>()
        for (word in words) {
            val visited = BooleanArray(word.length)
            if (dfs(word, 0, visited, dictionary)) {
                answer.add(word)
            }
        }
        return answer
    }
}

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

Задача: 1274. Number of Ships in a Rectangle
Сложность: hard

(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

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

1⃣Разделите текущий прямоугольник на четыре меньших прямоугольника

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

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

😎 Решение:

class Solution {
    fun countShips(sea: Sea, topRight: Point, bottomLeft: Point): Int {
        if (!sea.hasShips(topRight, bottomLeft)) {
            return 0
        }
        if (topRight.x == bottomLeft.x && topRight.y == bottomLeft.y) {
            return 1
        }
        val midX = (topRight.x + bottomLeft.x) / 2
        val midY = (topRight.y + bottomLeft.y) / 2
        return countShips(sea, Point(midX, midY), bottomLeft) +
               countShips(sea, topRight, Point(midX + 1, midY + 1)) +
               countShips(sea, Point(midX, topRight.y), Point(bottomLeft.x, midY + 1)) +
               countShips(sea, Point(topRight.x, midY), Point(midX + 1, bottomLeft.y))
    }
}

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

Задача: 277. Find the Celebrity
Сложность: medium

Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них.
Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1.

Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

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

1⃣Найти потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.

2⃣Реализовать функцию isCelebrity(candidate):
Проверить, знает ли кандидат кого-либо из людей (исключая самих себя).
Проверить, знают ли все остальные кандидата (исключая самого кандидата).
Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью.

3⃣Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.

😎 Решение:

class Solution {
    private var n = 0

    fun findCelebrity(n: Int): Int {
        this.n = n
        var celebrityCandidate = 0
        for (i in 1 until n) {
            if (cachedKnows(celebrityCandidate, i)) {
                celebrityCandidate = i
            }
        }
        return if (isCelebrity(celebrityCandidate)) celebrityCandidate else -1
    }

    private fun isCelebrity(i: Int): Boolean {
        for (j in 0 until n) {
            if (i == j) continue
            if (cachedKnows(i, j) || !cachedKnows(j, i)) {
                return false
            }
        }
        return true
    }

    private fun cachedKnows(a: Int, b: Int): Boolean {
        // Вспомогательная функция knows
        return false
    }
}

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

Задача: 944. Delete Columns to Make Sorted
Сложность: easy

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

Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

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

2⃣Пройти по каждому столбцу от 0 до длины строки.
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.

3⃣Вернуть count.

😎 Решение:

class Solution {
    fun minDeletionSize(strs: Array<String>): Int {
        var count = 0
        val rows = strs.size
        val cols = strs[0].length
        for (col in 0 until cols) {
            for (row in 1 until rows) {
                if (strs[row][col] < strs[row - 1][col]) {
                    count++
                    break
                }
            }
        }
        return count
    }
}

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

Задача: 364. Nested List Weight Sum II
Сложность: medium

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

Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа.
Вес целого числа определяется как maxDepth - (глубина целого числа) + 1.

Верните сумму каждого целого числа в nestedList, умноженную на его вес.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

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

1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.

2⃣Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts.

3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.

😎 Решение:

class Solution {
    fun depthSumInverse(nestedList: List<NestedInteger>): Int {
        val queue: Queue<NestedInteger> = LinkedList(nestedList)
        var depth = 1
        var maxDepth = 0
        var sumOfElements = 0
        var sumOfProducts = 0

        while (queue.isNotEmpty()) {
            val size = queue.size
            maxDepth = maxOf(maxDepth, depth)

            repeat(size) {
                val nested = queue.poll()

                if (nested.isInteger()) {
                    val value = nested.getInteger()
                    sumOfElements += value
                    sumOfProducts += value * depth
                } else {
                    queue.addAll(nested.getList())
                }
            }
            depth++
        }
        return (maxDepth + 1) * sumOfElements - sumOfProducts
    }
}

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

Задача: 823. Binary Trees With Factors
Сложность: medium

Дан массив уникальных целых чисел arr, где каждое целое число arr[i] строго больше 1.

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

Верните количество бинарных деревьев, которые мы можем создать. Ответ может быть слишком большим, поэтому верните ответ по модулю 10^9 + 7.

Пример:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

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

1⃣Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование.

2⃣Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k.

3⃣После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением.

😎 Решение:

class Solution {
    fun numFactoredBinaryTrees(A: IntArray): Int {
        val MOD = 1_000_000_007
        A.sort()
        val dp = IntArray(A.size) { 1 }
        val index = mutableMapOf<Int, Int>()
        
        for ((i, x) in A.withIndex()) {
            index[x] = i
        }
        
        for (i in A.indices) {
            for (j in 0 until i) {
                if (A[i] % A[j] == 0) {
                    val right = A[i] / A[j]
                    if (index.containsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index[right]!!]) % MOD
                    }
                }
            }
        }
        
        return dp.sum() % MOD
    }

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

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

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

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

😎 Решение:

class Solution {
    fun longestMountain(arr: IntArray): Int {
        val n = arr.size
        var ans = 0
        var base = 0

        while (base < n) {
            var end = base
            if (end + 1 < n && arr[end] < arr[end + 1]) {
                while (end + 1 < n && arr[end] < arr[end + 1]) {
                    end++
                }
                if (end + 1 < n && arr[end] > arr[end + 1]) {
                    while (end + 1 < n && arr[end] > arr[end + 1]) {
                        end++
                    }
                    ans = maxOf(ans, end - base + 1)
                }
            }
            base = maxOf(end, base + 1)
        }

        return ans
    }
}

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

Задача: 723. Candy Crush
Сложность: medium

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

        return board
    }
}

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

Задача: 739. Daily Temperatures
Сложность: medium

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

Задача: 967. Numbers With Same Consecutive Differences
Сложность: medium

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

Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.

Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

1⃣Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.

2⃣Инициализируйте список очередей начальными цифрами от 1 до 9.

3⃣Для каждого уровня (от 1 до n-1) создайте новый список очередей, добавляя к каждому числу в текущей очереди допустимые цифры, которые удовлетворяют условию разницы k.

😎 Решение:

class Solution {
    fun numsSameConsecDiff(N: Int, K: Int): IntArray {
        if (N == 1) return IntArray(10) { it }
        
        var queue = (1..9).toList()
        for (level in 1 until N) {
            val nextQueue = mutableListOf<Int>()
            for (num in queue) {
                val tailDigit = num % 10
                val nextDigits = listOf(tailDigit + K, tailDigit - K)
                
                for (nextDigit in nextDigits) {
                    if (nextDigit in 0..9) {
                        nextQueue.add(num * 10 + nextDigit)
                    }
                }
            }
            queue = nextQueue
        }
        
        return queue.toIntArray()
    }
}

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

Задача: 1490. Clone N-ary Tree
Сложность: medium

Дан корень N-арного дерева, верните глубокую копию (клон) дерева.
Каждый узел в N-арном дереве содержит значение (val) типа int и список (List[Node]) его детей.

class Node {
    public int val;
    public List<Node> children;
}

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

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

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

1⃣Базовый случай:
Проверить, является ли входной узел null. Если да, вернуть null.

2⃣Копирование узла:
Создать новый узел с таким же значением, как у входного узла.

3⃣Рекурсивное клонирование детей:
Рекурсивно клонировать каждого ребёнка входного узла и добавить клонированных детей в список детей нового узла.
Вернуть клонированный узел.

😎 Решение:

class Node(var `val`: Int) {
    var children: List<Node?> = ArrayList()
}

class Solution {
    fun cloneTree(root: Node?): Node? {
        root ?: return null

        val nodeCopy = Node(root.`val`)
        for (child in root.children) {
            nodeCopy.children = nodeCopy.children + cloneTree(child)
        }
        return nodeCopy
    }
}

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

Задача: 688. Knight Probability in Chessboard
Сложность: medium

На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1).

Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении.

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

Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски.

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

Пример:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

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

1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня.

2⃣Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j].

3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность.

😎 Решение:

class Solution {
    fun knightProbability(n: Int, k: Int, row: Int, column: Int): Double {
        val directions = arrayOf(
            1 to 2, 1 to -2, -1 to 2, -1 to -2,
            2 to 1, 2 to -1, -2 to 1, -2 to -1
        )
        val dp = Array(k + 1) { Array(n) { DoubleArray(n) } }
        dp[0][row][column] = 1.0

        for (moves in 1..k) {
            for (i in 0 until n) {
                for (j in 0 until n) {
                    for (direction in directions) {
                        val prevI = i - direction.first
                        val prevJ = j - direction.second
                        if (prevI in 0 until n && prevJ in 0 until n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8
                        }
                    }
                }
            }
        }

        return dp[k].sumOf { it.sum() }
    }
}

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

Задача: 369. Plus One Linked List
Сложность: hard

Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу.

Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

Input: head = [1,2,3]
Output: [1,2,4]

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

1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.

2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).

😎 Решение:

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

class Solution {
    fun plusOne(head: ListNode?): ListNode? {
        val sentinel = ListNode(0)
        sentinel.next = head
        var notNine = sentinel

        var current = head
        while (current != null) {
            if (current.`val` != 9) {
                notNine = current
            }
            current = current.next
        }

        notNine.`val` += 1
        notNine = notNine.next

        while (notNine != null) {
            notNine.`val` = 0
            notNine = notNine.next
        }

        return if (sentinel.`val` == 0) sentinel.next else sentinel
    }
}

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

Задача: 501. Find Mode in Binary Search Tree
Сложность: easy

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

Предположим, что BST определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла.
Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла.
Оба поддерева также должны быть бинарными деревьями поиска.

Пример:

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

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

1⃣Обход дерева
Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values.

2⃣Поиск мод
Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans.

3⃣Возврат результата
Верните список ans.

😎 Решение:

class Solution {
    fun findMode(root: TreeNode?): IntArray {
        val values = mutableListOf<Int>()
        dfs(root, values)
        
        var maxStreak = 0
        var currStreak = 0
        var currNum = 0
        val ans = mutableListOf<Int>()
        
        for (num in values) {
            if (num == currNum) {
                currStreak++
            } else {
                currStreak = 1
                currNum = num
            }
            
            if (currStreak > maxStreak) {
                ans.clear()
                ans.add(num)
                maxStreak = currStreak
            } else if (currStreak == maxStreak) {
                ans.add(num)
            }
        }
        
        return ans.toIntArray()
    }
    
    private fun dfs(node: TreeNode?, values: MutableList<Int>) {
        if (node == null) return
        dfs(node.left, values)
        values.add(node.val)
        dfs(node.right, values)
    }
}

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

Задача: 765. Couples Holding Hands
Сложность: hard

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

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

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

😎 Решение:

class Solution {
    private var N = 0
    private lateinit var pairs: Array<IntArray>
    
    fun minSwapsCouples(row: IntArray): Int {
        N = row.size / 2
        pairs = Array(N) { IntArray(2) }
        for (i in 0 until N) {
            pairs[i][0] = row[2 * i] / 2
            pairs[i][1] = row[2 * i + 1] / 2
        }
        return solve(0)
    }
    
    private fun swap(a: Int, b: Int, c: Int, d: Int) {
        val t = pairs[a][b]
        pairs[a][b] = pairs[c][d]
        pairs[c][d] = t
    }
    
    private fun solve(i: Int): Int {
        if (i == N) return 0
        val x = pairs[i][0]
        val y = pairs[i][1]
        if (x == y) return solve(i + 1)
        
        var jx = 0
        var kx = 0
        var jy = 0
        var ky = 0
        for (j in i + 1 until N) {
            for (k in 0..1) {
                if (pairs[j][k] == x) { jx = j; kx = k }
                if (pairs[j][k] == y) { jy = j; ky = k }
            }
        }
        
        swap(i, 1, jx, kx)
        val ans1 = 1 + solve(i + 1)
        swap(i, 1, jx, kx)
        
        swap(i, 0, jy, ky)
        val ans2 = 1 + solve(i + 1)
        swap(i, 0, jy, ky)
        
        return minOf(ans1, ans2)
    }
}

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

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

fun assignBikes(workers: Array<IntArray>, bikes: Array<IntArray>): IntArray {
    val pairs = mutableListOf<Triple<Int, Int, Int>>()
    
    for (i in workers.indices) {
        for (j in bikes.indices) {
            val distance = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1])
            pairs.add(Triple(distance, i, j))
        }
    }
    
    pairs.sortWith(compareBy({ it.first }, { it.second }, { it.third }))
    
    val result = IntArray(workers.size) { -1 }
    val bikeTaken = BooleanArray(bikes.size)
    val workerAssigned = BooleanArray(workers.size)
    
    for ((distance, workerIdx, bikeIdx) in pairs) {
        if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
            result[workerIdx] = bikeIdx
            bikeTaken[bikeIdx] = true
            workerAssigned[workerIdx] = true
        }
    }
    
    return result
}

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

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.

Напоминаю, что в честь релиза запускаем акцию.

Первые 500 покупателей получат:

🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал

🔔 Подпишитесь на этот канал: https://t.iss.one/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь