Задача: 622. Design Circular Queue
Сложность: medium

Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.

Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

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

1⃣Используйте массив фиксированного размера для хранения элементов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди.

2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу.

3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди.

😎 Решение:

class MyCircularQueue(k: Int) {
    private val queue: IntArray = IntArray(k) { -1 }
    private var front: Int = 0
    private var rear: Int = -1
    private var size: Int = 0
    private val capacity: Int = k
    
    fun enQueue(value: Int): Boolean {
        if (isFull()) {
            return false
        }
        rear = (rear + 1) % capacity
        queue[rear] = value
        size++
        return true
    }
    
    fun deQueue(): Boolean {
        if (isEmpty()) {
            return false
        }
        front = (front + 1) % capacity
        size--
        return true
    }
    
    fun Front(): Int {
        return if (isEmpty()) -1 else queue[front]
    }
    
    fun Rear(): Int {
        return if (isEmpty()) -1 else queue[rear]
    }
    
    fun isEmpty(): Boolean {
        return size == 0
    }
    
    fun isFull(): Boolean {
        return size == capacity
    }
}

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

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

Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.

Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

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

1⃣Итерируйтесь по каждому интервалу в списке intervals.

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

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

😎 Решение:

class Solution {
    fun removeInterval(intervals: List<List<Double>>, toBeRemoved: List<Double>): List<List<Double>> {
        val result = mutableListOf<List<Double>>()
        for (interval in intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.add(listOf(interval[0], minOf(interval[1], toBeRemoved[0])))
            }
            if (interval[1] > toBeRemoved[1]) {
                result.add(listOf(maxOf(interval[0], toBeRemoved[1]), interval[1]))
            }
        }
        return result
    }
}

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

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

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

1⃣Отсортируйте массив слов по длине и лексикографическому порядку.

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

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

😎 Решение:

fun longestWord(words: Array<String>): String {
    words.sort()
    val validWords = mutableSetOf("")
    var longest = ""
    for (word in words) {
        if (validWords.contains(word.dropLast(1))) {
            validWords.add(word)
            if (word.length > longest.length) {
                longest = word
            }
        }
    }
    return longest
}

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
    fun minArea(image: Array<CharArray>, x: Int, y: Int): Int {
        val m = image.size
        val n = image[0].size
        val left = searchColumns(image, 0, y, 0, m, true)
        val right = searchColumns(image, y + 1, n, 0, m, false)
        val top = searchRows(image, 0, x, left, right, true)
        val bottom = searchRows(image, x + 1, m, left, right, false)
        return (right - left) * (bottom - top)
    }

    private fun searchColumns(image: Array<CharArray>, i: Int, j: Int, top: Int, bottom: Int, whiteToBlack: Boolean): Int {
        var i = i
        var j = j
        while (i != j) {
            var k = top
            val mid = (i + j) / 2
            while (k < bottom && image[k][mid] == '0') {
                k++
            }
            if ((k < bottom) == whiteToBlack) {
                j = mid
            } else {
                i = mid + 1
            }
        }
        return i
    }

    private fun searchRows(image: Array<CharArray>, i: Int, j: Int, left: Int, right: Int, whiteToBlack: Boolean): Int {
        var i = i
        var j = j
        while (i != j) {
            var k = left
            val mid = (i + j) / 2
            while (k < right && image[mid][k] == '0') {
                k++
            }
            if ((k < right) == whiteToBlack) {
                j = mid
            } else {
                i = mid + 1
            }
        }
        return i
    }
}

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy

Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.

Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.

Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..

2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.

3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.

😎 Решение:

class Solution {
    fun isMajorityElement(nums: IntArray, target: Int): Boolean {
        var count = 0
        for (num in nums) {
            if (num == target) {
                count++
            }
        }
        return count > nums.size / 2
    }
}

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

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

Напишите алгоритм для определения, является ли число n счастливым.

Счастливое число определяется следующим процессом:

Начиная с любого положительного целого числа, замените число суммой квадратов его цифр.
Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1.
Те числа, для которых этот процесс завершается 1, являются счастливыми.
Верните true, если n является счастливым числом, и false, если нет.

Пример:

Input: n = 2
Output: false

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

1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач.

2⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet.

3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач.

😎 Решение:

class Solution {
    private fun getNext(n: Int): Int {
        var n = n
        var totalSum = 0
        while (n > 0) {
            val digit = n % 10
            n /= 10
            totalSum += digit * digit
        }
        return totalSum
    }

    fun isHappy(n: Int): Boolean {
        var n = n
        val seen = mutableSetOf<Int>()
        while (n != 1 && n !in seen) {
            seen.add(n)
            n = getNext(n)
        }
        return n == 1
    }
}

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

Задача: 147. Insertion Sort List
Сложность: medium

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

Пример:

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

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

1⃣Создайте фиктивный узел dummy, указывающий на начало нового отсортированного списка. Он упростит вставку элементов, в том числе в начало.

2⃣Для каждого узла curr из оригинального списка найдите место в отсортированной части (dummy), где он должен стоять, и вставьте его туда.

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

😎 Решение:

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

class Solution {
    fun insertionSortList(head: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var curr = head

        while (curr != null) {
            var prev = dummy
            while (prev.next != null && prev.next!!.`val` <= curr.`val`) {
                prev = prev.next!!
            }
            val next = curr.next
            curr.next = prev.next
            prev.next = curr
            curr = next
        }
        return dummy.next
    }
}

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

Задача: 446. Arithmetic Slices II - Subsequence
Сложность: hard

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

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

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.

2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

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

😎 Решение:

class Solution {
    private var n = 0
    private var ans = 0

    private fun dfs(dep: Int, A: IntArray, cur: MutableList<Long>) {
        if (dep == n) {
            if (cur.size < 3) return
            for (i in 1 until cur.size) {
                if (cur[i] - cur[i - 1] != cur[1] - cur[0]) return
            }
            ans++
            return
        }
        dfs(dep + 1, A, cur)
        cur.add(A[dep].toLong())
        dfs(dep + 1, A, cur)
        cur.removeAt(cur.size - 1)
    }

    fun numberOfArithmeticSlices(A: IntArray): Int {
        n = A.size
        ans = 0
        dfs(0, A, mutableListOf())
        return ans
    }
}

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

Задача: 272. Closest Binary Search Tree Value II
Сложность: hard

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

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

Пример:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

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

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

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

3⃣Вернуть первые k значений из отсортированного массива:
Извлечь первые k элементов из отсортированного массива и вернуть их.

😎 Решение:

class Solution {
    fun closestKValues(root: TreeNode?, target: Double, k: Int): List<Int> {
        val arr = mutableListOf<Int>()
        dfs(root, arr)
        arr.sortBy { Math.abs(it - target) }
        return arr.take(k)
    }
    
    private fun dfs(node: TreeNode?, arr: MutableList<Int>) {
        if (node == null) return
        arr.add(node.`val`)
        dfs(node.left, arr)
        dfs(node.right, arr)
    }
}

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

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

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.

😎 Решение:

class Solution {
    fun minCostToMoveChips(position: IntArray): Int {
        var evenCount = 0
        var oddCount = 0
        
        for (pos in position) {
            if (pos % 2 == 0) {
                evenCount++
            } else {
                oddCount++
            }
        }
        
        return minOf(evenCount, oddCount)
    }
}

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

Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed
Сложность: hard

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

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

RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.
bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.
bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.
int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.
Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.

Пример:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

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

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

2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае.
Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае.

3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента.

😎 Решение:

import kotlin.random.Random

class RandomizedCollection {
    private val dict = mutableMapOf<Int, MutableSet<Int>>()
    private val list = mutableListOf<Int>()

    fun insert(val: Int): Boolean {
        val exists = dict.containsKey(val)
        if (!exists) {
            dict[val] = mutableSetOf()
        }
        dict[val]?.add(list.size)
        list.add(val)
        return !exists
    }

    fun remove(val: Int): Boolean {
        val indices = dict[val] ?: return false
        val index = indices.first()
        indices.remove(index)
        val lastElement = list.removeAt(list.size - 1)
        if (index < list.size) {
            list[index] = lastElement
            dict[lastElement]?.remove(list.size)
            dict[lastElement]?.add(index)
        }
        if (indices.isEmpty()) {
            dict.remove(val)
        }
        return true
    }

    fun getRandom(): Int {
        return list[Random.nextInt(list.size)]
    }
}

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

Задача: 267. Palindrome Permutation II
Сложность: medium

Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.

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

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

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

2⃣Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.

3⃣Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private HashSet<string> set;

    public Solution() {
        set = new HashSet<string>();
    }

    public IList<string> GeneratePalindromes(string s) {
        int[] map = new int[128];
        char[] st = new char[s.Length / 2];
        if (!CanPermutePalindrome(s, map)) {
            return new List<string>();
        }

        char ch = '\0';
        int k = 0;
        for (int i = 0; i < map.Length; i++) {
            if (map[i] % 2 == 1) {
                ch = (char)i;
            }
            for (int j = 0; j < map[i] / 2; j++) {
                st[k++] = (char)i;
            }
        }
        Permute(st, 0, ch);
        return new List<string>(set);
    }

    private bool CanPermutePalindrome(string s, int[] map) {
        int count = 0;
        foreach (char c in s) {
            int index = (int)c;
            map[index]++;
            if (map[index] % 2 == 0) {
                count--;
            } else {
                count++;
            }
        }
        return count <= 1;
    }

    private void Swap(ref char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    private void Permute(char[] s, int l, char ch) {
        if (l == s.Length) {
            StringBuilder sb = new StringBuilder();
            sb.Append(s);
            if (ch != '\0') {
                sb.Append(ch);
            }
            Array.Reverse(s);
            sb.Append(s);
            set.Add(sb.ToString());
            Array.Reverse(s);
        } else {
            for (int i = l; i < s.Length; i++) {
                if (s[l] != s[i] || l == i) {
                    Swap(ref s, l, i);
                    Permute(s, l + 1, ch);
                    Swap(ref s, l, i);
                }
            }
        }
    }
}

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

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

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