Задача: 1801. Number of Orders in the Backlog
Сложность: medium

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:

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

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

Пример:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

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

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

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

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

class Solution {
    fun getNumberOfBacklogOrders(orders: Array<IntArray>): Int {
        val MOD = 1_000_000_007
        val buyOrders = PriorityQueue(compareByDescending<Pair<Int, Int>> { it.first })
        val sellOrders = PriorityQueue(compareBy<Pair<Int, Int>> { it.first })

        orders.forEach { (price, amount, orderType) ->
            var remainingAmount = amount
            if (orderType == 0) {
                while (remainingAmount > 0 && sellOrders.isNotEmpty() && sellOrders.peek().first <= price) {
                    val (sellPrice, sellAmount) = sellOrders.poll()
                    val executedAmount = minOf(remainingAmount, sellAmount)
                    remainingAmount -= executedAmount
                    if (sellAmount > executedAmount) sellOrders.add(sellPrice to sellAmount - executedAmount)
                }
                if (remainingAmount > 0) buyOrders.add(price to remainingAmount)
            } else {
                while (remainingAmount > 0 && buyOrders.isNotEmpty() && buyOrders.peek().first >= price) {
                    val (buyPrice, buyAmount) = buyOrders.poll()
                    val executedAmount = minOf(remainingAmount, buyAmount)
                    remainingAmount -= executedAmount
                    if (buyAmount > executedAmount) buyOrders.add(buyPrice to buyAmount - executedAmount)
                }
                if (remainingAmount > 0) sellOrders.add(price to remainingAmount)
            }
        }

        return (buyOrders.sumOf { it.second } + sellOrders.sumOf { it.second }) % MOD
    }
}

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

Задача: 1406. Stone Game III
Сложность: hard

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

Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.

Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.

Пример:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

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

1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0.

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

3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья.

😎 Решение:

class Solution {
    fun stoneGameIII(stoneValue: IntArray): String {
        val n = stoneValue.size
        val dp = IntArray(n + 1)
        for (i in n - 1 downTo 0) {
            dp[i] = stoneValue[i] - dp[i + 1]
            if (i + 2 <= n) {
                dp[i] = maxOf(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2])
            }
            if (i + 3 <= n) {
                dp[i] = maxOf(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3])
            }
        }
        return when {
            dp[0] > 0 -> "Alice"
            dp[0] < 0 -> "Bob"
            else -> "Tie"
        }
    }
}

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

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

Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело.

Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false.

Пример:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

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

1⃣Инициализация
Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0.

2⃣Поиск делителей и вычисление суммы
Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель.

3⃣Проверка на совершенное число
Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false.

😎 Решение:

  class Solution {
    fun checkPerfectNumber(num: Int): Boolean {
        if (num <= 0) return false
        var sum = 0
        for (i in 1..Math.sqrt(num.toDouble()).toInt()) {
            if (num % i == 0) {
                sum += i
                if (i * i != num) {
                    sum += num / i
                }
            }
        }
        return sum - num == num
    }
}

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

Задача: 375. Guess Number Higher or Lower II
Сложность: easy

Мы играем в угадайку. Правила игры следующие:

Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.
Пример:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

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

1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента.

2⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость.

3⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы.

😎 Решение:

class Solution {
    fun calculate(low: Int, high: Int): Int {
        if (low >= high) return 0
        var minres = Int.MAX_VALUE
        for (i in low..high) {
            val res = i + maxOf(calculate(i + 1, high), calculate(low, i - 1))
            minres = minOf(res, minres)
        }
        return minres
    }

    fun getMoneyAmount(n: Int): Int {
        return calculate(1, n)
    }
}

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

Задача: 31. Next Permutation
Сложность: medium

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

Пример:

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

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

1⃣ Найти первый элемент справа, который меньше следующего (nums[i] < nums[i+1]).

2⃣ Найти наименьший элемент справа, который больше nums[i], и поменять их местами.

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

😎 Решение:

class Solution {
    fun nextPermutation(nums: IntArray) {
        var i = nums.size - 2
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--
        }
        if (i >= 0) {
            var j = nums.size - 1
            while (nums[j] <= nums[i]) {
                j--
            }
            swap(nums, i, j)
        }
        reverse(nums, i + 1)
    }

    private fun reverse(nums: IntArray, start: Int) {
        var i = start
        var j = nums.size - 1
        while (i < j) {
            swap(nums, i, j)
            i++
            j--
        }
    }

    private fun swap(nums: IntArray, i: Int, j: Int) {
        val temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp
    }
}

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

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

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

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution {
    fun maxSumTwoNoOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
        fun maxSumNonOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
            val n = nums.size
            val prefix = IntArray(n + 1)
            for (i in 0 until n) {
                prefix[i + 1] = prefix[i] + nums[i]
            }
            
            val maxFirst = IntArray(n)
            for (i in firstLen - 1 until n) {
                maxFirst[i] = maxOf(if (i > 0) maxFirst[i - 1] else 0, prefix[i + 1] - prefix[i + 1 - firstLen])
            }
            
            val maxSecond = IntArray(n)
            for (i in secondLen - 1 until n) {
                maxSecond[i] = maxOf(if (i > 0) maxSecond[i - 1] else 0, prefix[i + 1] - prefix[i + 1 - secondLen])
            }
            
            var maxSum = 0
            for (i in firstLen + secondLen - 1 until n) {
                maxSum = maxOf(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]))
            }
            
            return maxSum
        }
        
        return maxOf(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reversedArray(), secondLen, firstLen))
    }
}

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

Задача: 1198. Find Smallest Common Element in All Rows
Сложность: medium

Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.

Если общего элемента нет, верните -1.

Пример:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

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

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

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

3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.

😎 Решение:

class Solution {
    fun smallestCommonElement(mat: Array<IntArray>): Int {
        val n = mat.size
        val m = mat[0].size
        val pos = IntArray(n) { 0 }
        var curMax = 0
        var cnt = 0

        while (true) {
            for (i in 0 until n) {
                while (pos[i] < m && mat[i][pos[i]] < curMax) {
                    pos[i]++
                }
                if (pos[i] >= m) {
                    return -1
                }
                if (mat[i][pos[i]] != curMax) {
                    cnt = 1
                    curMax = mat[i][pos[i]]
                } else {
                    cnt++
                    if (cnt == n) {
                        return curMax
                    }
                }
            }
        }
    }
}

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

Задача: 1329. Sort the Matrix Diagonally
Сложность: medium

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

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

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

1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

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

3⃣Извлеките значения из хеш-карты и обновите матрицу, заполняя ее отсортированными значениями диагоналей. Верните отсортированную матрицу.

😎 Решение:

class Solution {
    fun diagonalSort(mat: Array<IntArray>): Array<IntArray> {
        val m = mat.size
        val n = mat[0].size
        val diagonals = mutableMapOf<Int, PriorityQueue<Int>>()
        
        for (row in 0 until m) {
            for (col in 0 until n) {
                val key = row - col
                if (diagonals[key] == null) {
                    diagonals[key] = PriorityQueue()
                }
                diagonals[key]?.add(mat[row][col])
            }
        }
        
        for (row in 0 until m) {
            for (col in 0 until n) {
                val key = row - col
                mat[row][col] = diagonals[key]?.poll() ?: 0
            }
        }
        
        return mat
    }
}

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

Задача: 650. 2 Keys Keyboard
Сложность: medium

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Пример:

Input: n = 3
Output: 3

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

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

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

3⃣Возвращайте значение из таблицы динамического программирования для n.

😎 Решение:

fun minSteps(n: Int): Int {
    if (n == 1) return 0
    val dp = IntArray(n + 1)
    for (i in 2..n) {
        dp[i] = i
        for (j in 1..(i / 2)) {
            if (i % j == 0) {
                dp[i] = kotlin.math.min(dp[i], dp[j] + i / j)
            }
        }
    }
    return dp[n]
}

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

Задача: 954. Array of Doubled Pairs
Сложность: medium

Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.

Пример:

Input: arr = [3,1,3,6]
Output: false

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

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

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

3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.

😎 Решение:

class Solution {
    fun canReorderDoubled(arr: IntArray): Boolean {
        val count = mutableMapOf<Int, Int>()
        for (num in arr) {
            count[num] = count.getOrDefault(num, 0) + 1
        }
        arr.sortBy { Math.abs(it) }
        for (num in arr) {
            if (count[num] == 0) continue
            if (count.getOrDefault(2 * num, 0) == 0) return false
            count[num] = count[num]!! - 1
            count[2 * num] = count[2 * num]!! - 1
        }
        return true
    }
}

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

Задача: 785. Is Graph Bipartite?
Сложность: medium

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).
Нет параллельных ребер (graph[u] не содержит дублирующихся значений).
Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).
Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.
Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

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

1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

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

3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎 Решение:

class Solution {
    fun isBipartite(graph: Array<IntArray>): Boolean {
        val color = mutableMapOf<Int, Int>()
        for (node in graph.indices) {
            if (node !in color) {
                val stack = mutableListOf(node)
                color[node] = 0
                while (stack.isNotEmpty()) {
                    val node = stack.removeAt(stack.size - 1)
                    for (nei in graph[node]) {
                        if (nei !in color) {
                            stack.add(nei)
                            color[nei] = color[node]!! xor 1
                        } else if (color[nei] == color[node]) {
                            return false
                        }
                    }
                }
            }
        }
        return true
    }
}

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

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

Даны две двоичные строки a и b. Верните их сумму в виде двоичной строки.

Пример:

Input: a = "11", b = "1"
Output: "100"

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

1⃣Начните с переноса carry = 0. Если в числе a наименьший бит равен 1, добавьте 1 к carry. То же самое относится к числу b: если в числе b наименьший бит равен 1, добавьте 1 к carry. В этот момент carry для наименьшего бита может быть равен 0 (00), 1 (01) или 2 (10).

2⃣Теперь добавьте наименьший бит carry к ответу и перенесите старший бит carry на следующий порядковый бит.

3⃣Повторяйте те же шаги снова и снова, пока не будут использованы все биты в a и b. Если остаётся ненулевой carry, добавьте его. Теперь переверните строку ответа, и задача выполнена.

😎 Решение:

class Solution {
    fun addBinary(a: String, b: String): String {
        val n = maxOf(a.length, b.length)
        val aPadded = a.padStart(n, '0')
        val bPadded = b.padStart(n, '0')

        var carry = 0
        val answer = StringBuilder()
        for (i in n - 1 downTo 0) {
            if (aPadded[i] == '1') {
                carry += 1
            }
            if (bPadded[i] == '1') {
                carry += 1
            }

            answer.append(if (carry % 2 == 1) "1" else "0")
            carry /= 2
        }

        if (carry == 1) {
            answer.append("1")
        }
        return answer.reverse().toString()
    }
}

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

Задача: 655. Print Binary Tree
Сложность: medium

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

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

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

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

fun findHeight(root: TreeNode?): Int {
    if (root == null) return -1
    return 1 + maxOf(findHeight(root.left), findHeight(root.right))
}

fun fill(res: Array<Array<String>>, root: TreeNode?, r: Int, c: Int, height: Int) {
    if (root == null) return
    res[r][c] = root.`val`.toString()
    if (root.left != null) {
        fill(res, root.left, r + 1, c - (1 shl (height - r - 1)), height)
    }
    if (root.right != null) {
        fill(res, root.right, r + 1, c + (1 shl (height - r - 1)), height)
    }
}

fun printTree(root: TreeNode?): Array<Array<String>> {
    val height = findHeight(root)
    val m = height + 1
    val n = (1 shl (height + 1)) - 1
    val res = Array(m) { Array(n) { "" } }
    fill(res, root, 0, (n - 1) / 2, height)
    return res
}

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

Задача: 350. Intersection of Two Arrays II
Сложность: easy

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

Пример:

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

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

1⃣Подсчет частоты элементов:
Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в nums1.

2⃣Нахождение пересечения:
Пройдите по элементам nums2, и если элемент присутствует в хеш-таблице из шага 1 и его счетчик больше нуля, добавьте этот элемент в результат и уменьшите счетчик.

3⃣Возврат результата:
Верните массив пересечения.

😎 Решение:

class Solution {
    fun intersect(nums1: IntArray, nums2: IntArray): IntArray {
        val counts = mutableMapOf<Int, Int>()
        val result = mutableListOf<Int>()
        
        for (num in nums1) {
            counts[num] = counts.getOrDefault(num, 0) + 1
        }
        
        for (num in nums2) {
            if (counts.getOrDefault(num, 0) > 0) {
                result.add(num)
                counts[num] = counts[num]!! - 1
            }
        }
        
        return result.toIntArray()
    }
}

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

Задача: 257. Binary Tree Paths
Сложность: easy

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

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

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2⃣Начните с корневого узла, пустого пути и пустого списка путей.

3⃣Верните список всех путей от корня до листа.

😎 Решение:

class Solution {
    fun construct_paths(root: TreeNode?, path: String, paths: MutableList<String>) {
        if (root != null) {
            var path = path + root.`val`
            if (root.left == null && root.right == null) {
                paths.add(path)
            } else {
                path += "->"
                construct_paths(root.left, path, paths)
                construct_paths(root.right, path, paths)
            }
        }
    }

    fun binaryTreePaths(root: TreeNode?): List<String> {
        val paths = mutableListOf<String>()
        construct_paths(root, "", paths)
        return paths
    }
}

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

Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

class NumArray(nums: IntArray) {
    private val sum: IntArray = IntArray(nums.size + 1)

    init {
        for (i in nums.indices) {
            sum[i + 1] = sum[i] + nums[i]
        }
    }

    fun sumRange(i: Int, j: Int): Int {
        return sum[j + 1] - sum[i]
    }
}

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

Задача: 869. Reordered Power of 2
Сложность: medium

Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем.

Верните true, если и только если мы можем сделать это так, чтобы полученное число было степенью двойки.

Пример:

Input: n = 1
Output: true

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

1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.

2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.

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

😎 Решение:

class Solution {
    fun reorderedPowerOf2(N: Int): Boolean {
        val A = N.toString().map { it - '0' }.toIntArray()
        return permutations(A, 0)
    }

    private fun isPowerOfTwo(A: IntArray): Boolean {
        if (A[0] == 0) return false
        var N = A.joinToString("").toInt()
        while (N > 0 && (N and 1) == 0) N = N shr 1
        return N == 1
    }

    private fun permutations(A: IntArray, start: Int): Boolean {
        if (start == A.size) return isPowerOfTwo(A)
        for (i in start until A.size) {
            A.swap(start, i)
            if (permutations(A, start + 1)) return true
            A.swap(start, i)
        }
        return false
    }

    private fun IntArray.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

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

Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

Input: nums = [1,3,1], k = 1
Output: 0

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

1⃣Отсортируйте массив nums.

2⃣Определите минимальное и максимальное возможные расстояния.

3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.

😎 Решение:

fun countPairs(nums: IntArray, mid: Int): Int {
    var count = 0
    var j = 0
    for (i in nums.indices) {
        while (j < nums.size && nums[j] - nums[i] <= mid) {
            j++
        }
        count += j - i - 1
    }
    return count
}

fun smallestDistancePair(nums: IntArray, k: Int): Int {
    nums.sort()
    var left = 0
    var right = nums.last() - nums.first()
    while (left < right) {
        val mid = (left + right) / 2
        if (countPairs(nums, mid) < k) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

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

Задача: 1531. String Compression II
Сложность: hard

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

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

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

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

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

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение:

class Solution {
    private val memo = mutableMapOf<Int, Int>()
    private val add = setOf(1, 9, 99)

    fun getLengthOfOptimalCompression(s: String, k: Int): Int {
        return dp(s, 0, ('a' + 26), 0, k)
    }

    private fun dp(s: String, idx: Int, lastChar: Char, lastCharCount: Int, k: Int): Int {
        if (k < 0) return Int.MAX_VALUE / 2

        if (idx == s.length) return 0

        val key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k

        if (memo.containsKey(key)) return memo[key]!!

        val deleteChar = dp(s, idx + 1, lastChar, lastCharCount, k - 1)
        val keepChar = if (s[idx] == lastChar) {
            dp(s, idx + 1, lastChar, lastCharCount + 1, k) + if (add.contains(lastCharCount)) 1 else 0
        } else {
            dp(s, idx + 1, s[idx], 1, k) + 1
        }

        val res = minOf(keepChar, deleteChar)
        memo[key] = res

        return res
    }
}

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

Задача: 937. Reorder Data in Log Files
Сложность: medium

Вам дается массив журналов. Каждый журнал представляет собой строку слов, ограниченную пробелами, где первое слово является идентификатором. Существует два типа журналов: Буквенные журналы: Все слова (кроме идентификатора) состоят из строчных английских букв. Цифровые журналы: Все слова (кроме идентификатора) состоят из цифр. Упорядочите эти журналы таким образом: буквенные журналы идут перед всеми цифровыми журналами. Буквенные журналы сортируются лексикографически по их содержанию. Если их содержимое одинаково, то отсортируйте их лексикографически по их идентификаторам. Цифровые журналы сохраняют свой относительный порядок. Верните окончательный порядок журналов.

Пример:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

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

1⃣Разделить журналы на буквенные и цифровые.

2⃣Отсортировать буквенные журналы:
Лексикографически по содержимому.
Если содержимое одинаково, отсортировать по идентификатору.
Объединить отсортированные буквенные журналы и цифровые журналы в исходном порядке.

3⃣Вернуть окончательный результат.

😎 Решение:

class Solution {
    fun reorderLogFiles(logs: Array<String>): Array<String> {
        return logs.sortedWith { log1, log2 ->
            val split1 = log1.split(" ", limit = 2)
            val split2 = log2.split(" ", limit = 2)
            val isDigit1 = split1[1][0].isDigit()
            val isDigit2 = split2[1][0].isDigit()
            
            if (!isDigit1 && !isDigit2) {
                val cmp = split1[1].compareTo(split2[1])
                if (cmp != 0) cmp else split1[0].compareTo(split2[0])
            } else if (isDigit1 && isDigit2) {
                0
            } else if (isDigit1) {
                1
            } else {
                -1
            }
        }.toTypedArray()
    }
}

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

Задача: 904. Fruit Into Baskets
Сложность: medium

Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.

Пример:

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

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

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

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

3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге.

😎 Решение:

class Solution {
    fun totalFruit(fruits: IntArray): Int {
        val basket = mutableMapOf<Int, Int>()
        var left = 0
        var maxFruits = 0

        for (right in fruits.indices) {
            basket[fruits[right]] = basket.getOrDefault(fruits[right], 0) + 1
            while (basket.size > 2) {
                basket[fruits[left]] = basket[fruits[left]]!! - 1
                if (basket[fruits[left]] == 0) {
                    basket.remove(fruits[left])
                }
                left++
            }
            maxFruits = maxOf(maxFruits, right - left + 1)
        }

        return maxFruits
    }
}

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