Задача: 957. Prison Cells After N Days
Сложность: medium

Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста.
Каждый день статус камеры, занята она или пуста, меняется по следующим правилам:
Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой.
В противном случае, она становится пустой.
Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей.

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

Пример:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

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

1⃣Преобразуйте текущее состояние камер в целое число с помощью битовой маски. Это позволит удобно отслеживать повторяющиеся состояния.

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

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

😎 Решение:

class Solution {
    fun cellsToBitmap(cells: IntArray): Int {
        var stateBitmap = 0
        for (cell in cells) {
            stateBitmap = (stateBitmap shl 1) or cell
        }
        return stateBitmap
    }

    fun nextDay(cells: IntArray): IntArray {
        val newCells = IntArray(cells.size)
        for (i in 1 until cells.size - 1) {
            newCells[i] = if (cells[i - 1] == cells[i + 1]) 1 else 0
        }
        return newCells
    }

    fun prisonAfterNDays(cells: IntArray, N: Int): IntArray {
        var cells = cells
        var N = N
        val seen = mutableMapOf<Int, Int>()
        var isFastForwarded = false

        while (N > 0) {
            if (!isFastForwarded) {
                val stateBitmap = cellsToBitmap(cells)
                if (stateBitmap in seen) {
                    N %= seen[stateBitmap]!! - N
                    isFastForwarded = true
                } else {
                    seen[stateBitmap] = N
                }
            }

            if (N > 0) {
                N--
                cells = nextDay(cells)
            }
        }
        return cells
    }
}

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

Задача: 298. Binary Tree Longest Consecutive Sequence
Сложность: medium

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

Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути.

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

Пример:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

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

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

2⃣Сравнение текущего узла с родительским узлом:
Для каждого узла сравните его значение со значением родительского узла.
Если значение текущего узла на единицу больше значения родительского узла, увеличьте length.
Если значение текущего узла не является последовательным (не больше на единицу), сбросьте length на 1.

3⃣Обход дерева:
Рекурсивно обходите левое и правое поддерево, передавая обновлённое значение length.
В каждом узле обновляйте максимальную длину последовательного пути, если текущая длина больше.

😎 Решение:

class Solution {
    private var maxLength = 0

    fun longestConsecutive(root: TreeNode?): Int {
        dfs(root, null, 0)
        return maxLength
    }

    private fun dfs(node: TreeNode?, parent: TreeNode?, length: Int) {
        if (node == null) return
        var currentLength = length
        if (parent != null && node.`val` == parent.`val` + 1) {
            currentLength += 1
        } else {
            currentLength = 1
        }
        maxLength = maxOf(maxLength, currentLength)
        dfs(node.left, node, currentLength)
        dfs(node.right, node, currentLength)
    }
}

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

Задача: 300. Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

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

1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.

2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).

3⃣Верните максимальное значение из dp.

😎 Решение:

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        if (nums.isEmpty()) return 0

        val dp = IntArray(nums.size) { 1 }

        for (i in 1 until nums.size) {
            for (j in 0 until i) {
                if (nums[i] > nums[j]) {
                    dp[i] = maxOf(dp[i], dp[j] + 1)
                }
            }
        }

        return dp.maxOrNull() ?: 0
    }
}

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

Задача: 230. Kth Smallest Element in a BST
Сложность: medium

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

Пример:

Input: root = [3,1,4,null,2], k = 1
Output: 1

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

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

2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение.

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

😎 Решение:

class Solution {
    fun kthSmallest(root: TreeNode?, k: Int): Int {
        val stack = LinkedList<TreeNode>()
        var root = root
        var k = k

        while (true) {
            while (root != null) {
                stack.push(root)
                root = root.left
            }
            root = stack.pop()
            if (--k == 0) return root.`val`
            root = root.right
        }
    }
}

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

Задача: 675. Cut Off Trees for Golf Event
Сложность: hard

Вам необходимо срубить все деревья в лесу для проведения гольф-мероприятия. Лес представлен в виде матрицы m x n. В этой матрице:

- 0 означает, что ячейка непроходима.
- 1 представляет собой пустую проходимую ячейку.
- Число больше 1 представляет собой дерево в ячейке, и это число обозначает высоту дерева.

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

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

Начиная с точки (0, 0), верните минимальное количество шагов, необходимых для того, чтобы срубить все деревья. Если невозможно срубить все деревья, верните -1.

Примечание: Входные данные сформированы так, что нет двух деревьев с одинаковой высотой, и нужно срубить как минимум одно дерево.

Пример:

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

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

1⃣Начиная с (0, 0), для каждого дерева в порядке возрастания высоты будем вычислять расстояние от текущего местоположения до следующего дерева (и перемещаться туда), добавляя это расстояние к ответу.

2⃣Формулируем задачу как предоставление функции расстояния dist(forest, sr, sc, tr, tc), которая вычисляет расстояние от точки (sr, sc) до цели (tr, tc) с учетом препятствий, где dist[i][j] == 0. (Эта функция расстояния вернет -1, если путь невозможен.)

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

😎 Решение:

class Solution {
    fun cutOffTree(forest: List<List<Int>>): Int {
        val trees = forest.withIndex().flatMap { (r, row) ->
            row.withIndex().mapNotNull { (c, v) ->
                if (v > 1) Triple(v, r, c) else null
            }
        }.sortedBy { it.first }
        
        var sr = 0
        var sc = 0
        var ans = 0
        for ((_, tr, tc) in trees) {
            val d = dist(forest, sr, sc, tr, tc)
            if (d < 0) return -1
            ans += d
            sr = tr
            sc = tc
        }
        return ans
    }

    fun dist(forest: List<List<Int>>, sr: Int, sc: Int, tr: Int, tc: Int): Int {
        // Implement the distance function here
        return 0
    }
}

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

Задача: 253. Meeting Rooms II
Сложность: medium

Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

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

1⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.

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

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

😎 Решение:

import java.util.*

class Solution {
    fun minMeetingRooms(intervals: Array<IntArray>): Int {
        intervals.sortBy { it[0] }
        val heap = PriorityQueue<Int>()
        heap.add(intervals[0][1])
        
        for (i in 1 until intervals.size) {
            if (intervals[i][0] >= heap.peek()) {
                heap.poll()
            }
            heap.add(intervals[i][1])
        }
        return heap.size
    }
}

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

Задача: 1530. Number of Good Leaf Nodes Pairs
Сложность: medium

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

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

Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

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

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

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

3⃣ Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.

😎 Решение:

class Solution {
    fun countPairs(root: TreeNode?, distance: Int): Int {
        val graph = mutableMapOf<TreeNode, MutableList<TreeNode>>()
        val leafNodes = mutableSetOf<TreeNode>()
        traverseTree(root, null, graph, leafNodes)
        var ans = 0
        for (leaf in leafNodes) {
            val bfsQueue: Queue<TreeNode> = LinkedList()
            val seen = mutableSetOf<TreeNode>()
            bfsQueue.add(leaf)
            seen.add(leaf)
            for (i in 0..distance) {
                val size = bfsQueue.size
                for (j in 0 until size) {
                    val currNode = bfsQueue.poll()
                    if (leafNodes.contains(currNode) && currNode != leaf) {
                        ans++
                    }
                    graph[currNode]?.let {
                        for (neighbor in it) {
                            if (!seen.contains(neighbor)) {
                                bfsQueue.add(neighbor)
                                seen.add(neighbor)
                            }
                        }
                    }
                }
            }
        }
        return ans / 2
    }

    private fun traverseTree(currNode: TreeNode?, prevNode: TreeNode?,
                             graph: MutableMap<TreeNode, MutableList<TreeNode>>, leafNodes: MutableSet<TreeNode>) {
        if (currNode == null) {
            return
        }
        if (currNode.left == null && currNode.right == null) {
            leafNodes.add(currNode)
        }
        if (prevNode != null) {
            graph.computeIfAbsent(prevNode) { mutableListOf() }.add(currNode)
            graph.computeIfAbsent(currNode) { mutableListOf() }.add(prevNode)
        }
        traverseTree(currNode.left, currNode, graph, leafNodes)
        traverseTree(currNode.right, currNode, graph, leafNodes)
    }
}

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

Задача: 628. Maximum Product of Three Numbers
Сложность: medium

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

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

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

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

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

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

😎 Решение:

fun maximumProduct(nums: IntArray): Int {
    nums.sort()
    val n = nums.size
    val max1 = nums[n - 1] * nums[n - 2] * nums[n - 3]
    val max2 = nums[0] * nums[1] * nums[n - 1]
    return kotlin.math.max(max1, max2)
}

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

Задача: 259. 3Sum Smaller
Сложность: medium

Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.

Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

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

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

2⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.

3⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.

😎 Решение:

class Solution {
    fun threeSumSmaller(nums: IntArray, target: Int): Int {
        nums.sort()
        var sum = 0
        for (i in 0 until nums.size - 2) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i])
        }
        return sum
    }

    private fun twoSumSmaller(nums: IntArray, startIndex: Int, target: Int): Int {
        var sum = 0
        for (i in startIndex until nums.size - 1) {
            val j = binarySearch(nums, i, target - nums[i])
            sum += j - i
        }
        return sum
    }

    private fun binarySearch(nums: IntArray, startIndex: Int, target: Int): Int {
        var left = startIndex
        var right = nums.size - 1
        while (left < right) {
            val mid = (left

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

Задача №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок \([nums[a], nums[b], nums[c], nums[d]]\) таких, что:
- \(0 \leq a, b, c, d < n\)
- \(a, b, c\) и \(d\) различны.
- \(nums[a] + nums[b] + nums[c] + nums[d] = target\)

Вы можете вернуть ответ в любом порядке.

Пример:

Input: nums = [1,0,-1,0,-2,2], target = 0  
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]  

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

1⃣ Отсортировать массив для упрощения поиска и исключения дубликатов.

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

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

😎 Решение:

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        nums.sort()
        val target: Long = target.toLong()
        val sums = mutableListOf<List<Int>>()
        val lastIndex = nums.size - 1

        for (i in 0..lastIndex - 3) {
            if (i > 0 && nums[i - 1] == nums[i]) continue

            val targetI = target - nums[i]

            if (targetI < nums[i].toLong() + nums[i + 1].toLong() + nums[i + 2].toLong()) break
            if (targetI > nums[lastIndex].toLong() + nums[lastIndex - 1].toLong() + nums[lastIndex - 2].toLong()) {
                continue
            }

            for (j in i + 1..lastIndex - 2) {
                if (j > i + 1 && nums[j - 1] == nums[j]) continue

                val targetJ = targetI - nums[j]

                if (targetJ < nums[j].toLong() + nums[j + 1].toLong()) break
                if (targetJ > nums[lastIndex].toLong() + nums[lastIndex - 1].toLong()) continue

                for (k in j + 1..lastIndex - 1) {
                    if (k > j + 1 && nums[k - 1] == nums[k]) continue

                    val targetK = targetJ - nums[k]
                    val l = nums.binarySearch(targetK.toInt(), fromIndex = k + 1)
                    if (l >= 0) {
                        sums.add(listOf(nums[i], nums[j], nums[k], nums[l]))
                    }
                }
            }
        }

        return sums
    }
}

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

Задача: 280. Wiggle Sort
Сложность: medium

Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....

Вы можете считать, что входной массив всегда имеет допустимый ответ.

Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

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

1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена.

2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

😎 Решение:

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

    fun wiggleSort(nums: IntArray) {
        for (i in 0 until nums.size - 1) {
            if ((i % 2 == 0 && nums[i] > nums[i + 1]) || (i % 2 == 1 && nums[i] < nums[i + 1])) {
                swap(nums, i, i + 1)
            }
        }
    }
}

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
    fun getSum(a: Int, b: Int): Int {
        var x = kotlin.math.abs(a)
        var y = kotlin.math.abs(b)
        if (x < y) return getSum(b, a)
        val sign = if (a > 0) 1 else -1

        if (a * b >= 0) {
            while (y != 0) {
                val carry = (x and y) shl 1
                x = x xor y
                y = carry
            }
        } else {
            while (y != 0) {
                val borrow = ((x.inv()) and y) shl 1
                x = x xor y
                y = borrow
            }
        }
        return x * sign
    }
}

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

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

Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.

Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

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

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

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

3⃣Форматирование результата:
Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов.

😎 Решение:

import "fmt"

func readBinaryWatch(turnedOn int) []string {
    results := []string{}
    for h := 0; h < 12; h++ {
        for m := 0; m < 60; m++ {
            if bitCount(h)+bitCount(m) == turnedOn {
                results = append(results, fmt.Sprintf("%d:%02d", h, m))
            }
        }
    }
    return results
}

func bitCount(n int) int {
    count := 0
    for n > 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

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

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

Вам дан массив целых чисел nums.

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

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

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

2⃣Итерация по первым четырем элементам отсортированного массива: для каждого индекса left от 0 до 3 вычислите соответствующий правый индекс, разницу между элементами на этих индексах и обновите minDiff с минимальным значением.

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

😎 Решение:

class Solution {
    fun minDifference(nums: IntArray): Int {
        val numsSize = nums.size
        
        if (numsSize <= 4) return 0
        
        nums.sort()
        
        var minDiff = Int.MAX_VALUE
        
        for (left in 0 until 4) {
            val right = numsSize - 4 + left
            minDiff = minOf(minDiff, nums[right] - nums[left])
        }
        
        return minDiff
    }
}

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

Задача: 57. Insert Interval
Сложность: medium

Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.

Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).

Верните массив intervals после вставки.

Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его.

Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

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

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

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

3⃣Обработка интервалов после вставки:
Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним.
Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом.

😎 Решение:

class Solution {
    fun insert(intervals: List<List<Int>>, newInterval: MutableList<Int>): List<List<Int>> {
        val n = intervals.size
        var i = 0
        val res = mutableListOf<List<Int>>()

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i])
            i++
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = minOf(newInterval[0], intervals[i][0])
            newInterval[1] = maxOf(newInterval[1], intervals[i][1])
            i++
        }
        res.add(newInterval)

        while (i < n) {
            res.add(intervals[i])
            i++
        }

        return res
    }
}

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

Задача: 617. Merge Two Binary Trees
Сложность: medium

Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев.

Пример:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

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

1⃣Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null.

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

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

😎 Решение:

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

fun mergeTrees(root1: TreeNode?, root2: TreeNode?): TreeNode? {
    if (root1 == null) return root2
    if (root2 == null) return root1
    
    val mergedNode = TreeNode(root1.`val` + root2.`val`)
    mergedNode.left = mergeTrees(root1.left, root2.left)
    mergedNode.right = mergeTrees(root1.right, root2.right)
    
    return mergedNode
}

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

Задача: 1357. Apply Discount Every n Orders
Сложность: medium

В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i].

Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара).

Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100).

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

Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен.
double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты.

Пример:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]

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

1⃣Инициализация объекта:
Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами.

2⃣Обработка каждого счета:
Создайте метод getBill, который принимает массивы product и amount.
Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты.
Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу.

3⃣Верните итоговую сумму счета.

😎 Решение:

class Cashier(private val n: Int, private val discount: Int, products: IntArray, prices: IntArray) {
    private val productsPrices = products.zip(prices).toMap()
    private var customerCount = 0

    fun getBill(product: IntArray, amount: IntArray): Double {
        customerCount++
        var bill = 0.0
        
        for ((prod, amt) in product.zip(amount)) {
            bill += productsPrices[prod]!! * amt
        }
        
        if (customerCount % n == 0) {
            bill *= (100 - discount) / 100.0
        }
        
        return bill
    }
}

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

Задача: 870. Advantage Shuffle
Сложность: medium

Даны два целочисленных массива nums1 и nums2 одинаковой длины. Преимущество nums1 относительно nums2 — это количество индексов i, для которых nums1[i] > nums2[i].

Верните любую перестановку nums1, которая максимизирует его преимущество относительно nums2.

Пример:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

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

1⃣Отсортируйте nums1 и nums2. Для каждой карты a из отсортированного nums1 определите, может ли она побить текущую наименьшую карту b из отсортированного nums2. Если да, добавьте a в assigned[b], если нет, добавьте a в remaining.

2⃣После распределения всех карт из nums1, используйте assigned и remaining для построения итогового результата. Для каждой карты b из nums2, если assigned[b] не пуст, добавьте в результат последнюю карту из assigned[b], иначе добавьте последнюю карту из remaining.

3⃣Верните итоговый результат.

😎 Решение:

class Solution {
    fun advantageCount(A: IntArray, B: IntArray): IntArray {
        val sortedA = A.sorted()
        val sortedB = B.indices.sortedBy { B[it] }
        val assigned = mutableMapOf<Int, MutableList<Int>>().withDefault { mutableListOf() }
        val remaining = mutableListOf<Int>()
        
        var j = 0
        for (a in sortedA) {
            if (a > B[sortedB[j]]) {
                assigned[B[sortedB[j]]]?.add(a)
                j++
            } else {
                remaining.add(a)
            }
        }

        return B.map { b ->
            if (assigned[b]?.isNotEmpty() == true) assigned[b]?.removeAt(0)!!
            else remaining.removeAt(0)
        }.toIntArray()
    }
}

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

Задача: 1394. Find Lucky Integer in an Array
Сложность: easy

Дан массив целых чисел arr. Счастливое число — это число, частота которого в массиве равна его значению.

Верните наибольшее счастливое число в массиве. Если счастливого числа нет, верните -1.

Пример:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

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

1⃣Создайте хэш-карту для подсчёта частоты каждого числа в массиве.

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

3⃣Верните наибольшее счастливое число или -1, если таких чисел нет.

😎 Решение:

class Solution {
    fun findLucky(arr: IntArray): Int {
        val counts = mutableMapOf<Int, Int>()
        for (num in arr) {
            counts[num] = counts.getOrDefault(num, 0) + 1
        }
        
        var largestLuckyNumber = -1
        for ((key, value) in counts) {
            if (key == value) {
                largestLuckyNumber = Math.max(largestLuckyNumber, key)
            }
        }
        
        return largestLuckyNumber
    }
}

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

Задача: 742. Closest Leaf in a Binary Tree
Сложность: medium

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

Пример:

Input: root = [1,3,2], k = 1
Output: 2

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

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

2⃣Найдите все листья и минимальное расстояние до них, используя BFS, начиная с найденного узла k.

3⃣Верните значение ближайшего листа.

😎 Решение:

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

fun findClosestLeaf(root: TreeNode?, k: Int): Int {
    val path = mutableListOf<TreeNode>()
    val leaves = mutableMapOf<TreeNode, Int>()
    
    fun findPath(node: TreeNode?, k: Int): Boolean {
        if (node == null) return false
        path.add(node)
        if (node.`val` == k) return true
        if (findPath(node.left, k) || findPath(node.right, k)) return true
        path.removeAt(path.size - 1)
        return false
    }
    
    fun findLeaves(node: TreeNode?) {
        if (node == null) return
        if (node.left == null && node.right == null) leaves[node] = 0
        findLeaves(node.left)
        findLeaves(node.right)
    }
    
    findPath(root, k)
    findLeaves(root)
    
    val queue = mutableListOf<Pair<TreeNode, Int>>()
    queue.add(Pair(path.last(), 0))
    val visited = mutableSetOf<TreeNode>()
    
    while (queue.isNotEmpty()) {
        val (node, dist) = queue.removeAt(0)
        if (leaves.containsKey(node)) return node.`val`
        visited.add(node)
        node.left?.let {
            if (!visited.contains(it)) queue.add(Pair(it, dist + 1))
        }
        node.right?.let {
            if (!visited.contains(it)) queue.add(Pair(it, dist + 1))
        }
        if (path.size > 1) {
            queue.add(Pair(path.removeAt(path.size - 1), dist + 1))
        }
    }
    return -1
}

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

Задача: 27. Remove Element
Сложность: easy

Учитывая целочисленный массив nums и целочисленное значение val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в nums, которые не равны val.

Пример:

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

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

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

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

3⃣ Возвращаем значение index, которое соответствует количеству оставшихся элементов.

😎 Решение:

fun removeElement(nums: IntArray, `val`: Int): Int {
    var index = 0
    for (num in nums) {
        if (num != `val`) {
            nums[index] = num
            index++
        }
    }
    return index
}

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