Задача: 1074. Number of Submatrices That Sum to Target
Сложность: hard

Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению.

Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.

Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.

Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

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

1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений.

2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target.

3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count.

😎 Решение:

class Solution {
    fun numSubmatrixSumTarget(matrix: Array<IntArray>, target: Int): Int {
        val r = matrix.size
        val c = matrix[0].size
        val ps = Array(r + 1) { IntArray(c + 1) }
        
        for (i in 1..r) {
            for (j in 1..c) {
                ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1]
            }
        }
        
        var count = 0
        
        for (r1 in 1..r) {
            for (r2 in r1..r) {
                val h = mutableMapOf<Int, Int>()
                h[0] = 1
                for (col in 1..c) {
                    val currSum = ps[r2][col] - ps[r1 - 1][col]
                    count += h.getOrDefault(currSum - target, 0)
                    h[currSum] = h.getOrDefault(currSum, 0) + 1
                }
            }
        }
        
        return count
    }
}

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

Задача №44. Wildcard Matching
Сложность: hard

Учитывая входную строку s и шаблон p, реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой '?' и '*', где:
- '?' соответствует любому отдельному символу.
- '*' соответствует любой последовательности символов (включая пустую последовательность).
- Соответствие должно охватывать всю входную строку.

Пример:

Input: s = "aa", p = "a*"  
Output: true  

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

1⃣ Использовать два указателя (i1 для шаблона, i2 для строки) и переменную start, отслеживающую последний *.

2⃣ Последовательно сравнивать символы строки и шаблона, учитывая правила ? и *.

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

😎 Решение:

class Solution {
    fun isMatch(s: String, p: String): Boolean {
        var i1 = 0
        var i2 = 0
        var start = -1
        var match = 0

        while (i2 < s.length) {
            if (i1 < p.length && (p[i1] == s[i2] || p[i1] == '?')) {
                i1++
                i2++
            } else if (i1 < p.length && p[i1] == '*') {
                start = i1
                match = i2
                i1++
            } else if (start != -1) {
                i1 = start + 1
                match++
                i2 = match
            } else {
                return false
            }
        }

        while (i1 < p.length && p[i1] == '*') {
            i1++
        }

        return i1 == p.length
    }
}

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

Задача: 179. Largest Number
Сложность: medium

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

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

Пример:

Input: nums = [10,2]
Output: "210"

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

1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.

2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

class Solution {
    fun largestNumber(nums: IntArray): String {
        val strNums = nums.map { it.toString() }
        val sortedNums = strNums.sortedWith(compareByDescending<String> { a, b -> (a + b).compareTo(b + a) })
        if (sortedNums.first() == "0") {
            return "0"
        }
        return sortedNums.joinToString("")
    }
}

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

Задача: 113. Path Sum II
Сложность: medium

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

Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

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

1⃣Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке.

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

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

😎 Решение:

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

class Solution {

    fun recurseTree(
        node: TreeNode?,
        remainingSum: Int,
        pathNodes: MutableList<Int>,
        pathsList: MutableList<MutableList<Int>>
    ) {
        if (node == null) {
            return
        }

        pathNodes.add(node.`val`)

        if (remainingSum == node.`val` && node.left == null && node.right == null) {
            pathsList.add(ArrayList(pathNodes))
        } else {
            node.left?.let {
                recurseTree(it, remainingSum - node.`val`, pathNodes, pathsList)
            }
            node.right?.let {
                recurseTree(it, remainingSum - node.`val`, pathNodes, pathsList)
            }
        }

        pathNodes.removeAt(pathNodes.size - 1)
    }

    fun pathSum(root: TreeNode?, sum: Int): MutableList<MutableList<Int>> {
        val pathsList = mutableListOf<MutableList<Int>>()
        recurseTree(root, sum, mutableListOf(), pathsList)
        return pathsList
    }
}

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

Задача: 1002. Find Common Characters
Сложность: easy

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

Пример:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

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

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

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

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

😎 Решение:

class Solution {
    fun commonChars(words: Array<String>): List<String> {
        val minFreq = IntArray(26) { Int.MAX_VALUE }
        
        for (word in words) {
            val freq = IntArray(26)
            for (char in word) {
                freq[char - 'a']++
            }
            for (i in 0..25) {
                minFreq[i] = minOf(minFreq[i], freq[i])
            }
        }
        
        val result = mutableListOf<String>()
        for (i in 0..25) {
            repeat(minFreq[i]) {
                result.add(('a' + i).toString())
            }
        }
        return result
    }
}

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

Задача: 244. Shortest Word Distance II
Сложность: medium

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

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

WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.

Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

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

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

2⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎 Решение:

class WordDistance(words: Array<String>) {

    private val locations: MutableMap<String, MutableList<Int>> = HashMap()

    init {
        for (i in words.indices) {
            if (!locations.containsKey(words[i])) {
                locations[words[i]] = ArrayList()
            }
            locations[words[i]]!!.add(i)
        }
    }

    fun shortest(word1: String, word2: String): Int {
        val loc1 = locations[word1]!!
        val loc2 = locations[word2]!!
        var l1 = 0
        var l2 = 0
        var minDiff = Int.MAX_VALUE

        while (l1 < loc1.size && l2 < loc2.size) {
            minDiff = Math.min(minDiff, Math.abs(loc1[l1] - loc2[l2]))
            if (loc1[l1] < loc2[l2]) {
                l1++
            } else {
                l2++
            }
        }
        return minDiff
    }
}

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

Задача: 993. Cousins in Binary Tree
Сложность: easy

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

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

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

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

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

2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

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

😎 Решение:

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

class Solution {
    private var parentX: TreeNode? = null
    private var parentY: TreeNode? = null
    private var depthX = -1
    private var depthY = -1
    
    fun isCousins(root: TreeNode?, x: Int, y: Int): Boolean {
        dfs(root, null, 0, x, y)
        return depthX == depthY && parentX != parentY
    }
    
    private fun dfs(node: TreeNode?, parent: TreeNode?, depth: Int, x: Int, y: Int) {
        if (node == null) return
        if (node.`val` == x) {
            parentX = parent
            depthX = depth
        } else if (node.`val` == y) {
            parentY = parent
            depthY = depth
        } else {
            dfs(node.left, node, depth + 1, x, y)
            dfs(node.right, node, depth + 1, x, y)
        }
    }
}

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

Задача: 514. Freedom Trail
Сложность: hard

В видеоигре Fallout 4 в квесте "Дорога к свободе" игрокам нужно добраться до металлического диска, называемого "Кольцо Свободы", и использовать его для набора определённого ключевого слова, чтобы открыть дверь.

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

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

На этапе вращения кольца для набора символа key[i]:

Вы можете вращать кольцо по часовой или против часовой стрелки на одно место, что считается одним шагом. Конечная цель вращения — выровнять один из символов кольца в направлении "12 часов", и этот символ должен быть равен key[i].
Если символ key[i] уже выровнен в направлении "12 часов", нажмите центральную кнопку, чтобы набрать его, что также считается одним шагом. После нажатия вы можете начинать набирать следующий символ из key (следующий этап). Иначе, вы завершили весь набор.

Пример:

Input: ring = "godding", key = "godding"
Output: 13

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

1⃣Определите функцию countSteps для вычисления минимального пути между двумя индексами кольца ring. Создайте переменные ringLen и keyLen для хранения длин кольца и ключа соответственно. Создайте словарь bestSteps для хранения минимального количества шагов для нахождения символа на keyIndex, когда ringIndex кольца выровнен в позиции "12 часов".

2⃣Определите функцию tryLock, которая возвращает минимальное количество шагов для набора ключевого слова. Параметры: ringIndex, keyIndex, minSteps (минимальные шаги для набора ключевого слова на данный момент). Проверьте, равен ли keyIndex значению keyLen; если да, верните 0. Проверьте, есть ли пара (ringIndex, keyIndex) в bestSteps. Если есть, верните bestSteps[ringIndex][keyIndex]. Пройдите по каждому charIndex в ring. Если ring[charIndex] равен key[keyIndex], вычислите totalSteps, добавляя результат countSteps, единицу (нажатие центральной кнопки) и результат tryLock для следующего символа в key. Сохраните минимальное значение между totalSteps и текущим minSteps в minSteps. Сохраните minSteps для (ringIndex, keyIndex) в bestSteps.

3⃣Вызовите tryLock(0, 0, INT_MAX), начиная с нулевого индекса ring в позиции "12 часов" и первого символа в key. Наибольшее целое число передается как последний параметр, так как путь между нулевым индексом ring и первым символом key еще не определен.

😎 Решение:

class Solution {
    fun findRotateSteps(ring: String, key: String): Int {
        val ringLen = ring.length
        val keyLen = key.length
        val bestSteps = mutableMapOf<Pair<Int, Int>, Int>()
        
        fun countSteps(curr: Int, next: Int): Int {
            val stepsBetween = kotlin.math.abs(curr - next)
            val stepsAround = ringLen - stepsBetween
            return kotlin.math.min(stepsBetween, stepsAround)
        }
        
        fun tryLock(ringIndex: Int, keyIndex: Int): Int {
            bestSteps[Pair(ringIndex, keyIndex)]?.let { return it }
            
            if (keyIndex == keyLen) {
                bestSteps[Pair(ringIndex, keyIndex)] = 0
                return 0
            }
            
            var minSteps = Int.MAX_VALUE
            for (charIndex in ring.indices) {
                if (ring[charIndex] == key[keyIndex]) {
                    minSteps = minSteps.coerceAtMost(
                        countSteps(ringIndex, charIndex)
                        + 1
                        + tryLock(charIndex, keyIndex + 1)
                    )
                }
            }
            bestSteps[Pair(ringIndex, keyIndex)] = minSteps
            return minSteps
        }
        
        return tryLock(0, 0)
    }
}

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

Задача: 342. Power of Four
Сложность: easy

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

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 16
Output: true

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

1⃣Проверка неотрицательности:
Убедитесь, что n больше нуля, так как степени числа четыре всегда положительны.

2⃣Проверка логарифмом:
Используйте логарифм для проверки, является ли число степенью четырех. Число n является степенью четырех, если логарифм n по основанию 4 является целым числом.

3⃣Проверка побитовым оператором:
Число является степенью четырех, если оно является степенью двух (только один бит установлен) и количество нулей после этого бита четно.

😎 Решение:

class Solution {
    fun isPowerOfFour(n: Int): Boolean {
        if (n <= 0) return false
        val log_n_base_4 = Math.log(n.toDouble()) / Math.log(4.0)
        return log_n_base_4 % 1.0 == 0.0
    }
}

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

Задача: 288. Unique Word Abbreviation
Сложность: medium

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

Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:

ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.

Пример:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

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

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

2⃣Генерация сокращений:
При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение.
Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное).

3⃣Проверка уникальности:
Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict.
Если сокращение отсутствует в abbrDict, возвращайте true.
Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false.

😎 Решение:

class ValidWordAbbr(dictionary: Array<String>) {
    private val abbrDict = mutableMapOf<String, Boolean>()
    private val dict = dictionary.toSet()

    init {
        for (word in dict) {
            val abbr = toAbbr(word)
            abbrDict[abbr] = !(abbrDict[abbr] ?: false)
        }
    }

    fun isUnique(word: String): Boolean {
        val abbr = toAbbr(word)
        val hasAbbr = abbrDict[abbr]
        return hasAbbr == null || (hasAbbr && dict.contains(word))
    }

    private fun toAbbr(word: String): String {
        val n = word.length
        return if (n <= 2) word else "${word.first()}${n - 2}${word.last()}"
    }
}

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

Задача: 256. Paint House
Сложность: medium

Дано: nдома и матрица costs[n][3], где costs[i][j]— стоимость покраски дома iв цвет j(0 — красный, 1 — синий, 2 — зелёный).
Можно покрасить два сохранившихся дома в один цвет.
Необходимо найти минимальную суммарную стоимость покраски всех домов.

Пример:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

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

1⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2].

2⃣Для каждого дома i от 1 до n-1 обновите значения массива dp:
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

3⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]).

😎 Решение:

class Solution {
    fun minCost(costs: Array<IntArray>): Int {
        val n = costs.size
        val dp = Array(n) { IntArray(3) }
        dp[0] = costs[0].copyOf()
        
        for (i in 1 until n) {
            dp[i][0] = costs[i][0] + minOf(dp[i-1][1], dp[i-1][2])
            dp[i][1] = costs[i][1] + minOf(dp[i-1][0], dp[i-1][2])
            dp[i][2] = costs[i][2] + minOf(dp[i-1][0], dp[i-1][1])
        }
        
        return minOf(dp[n-1][0], dp[n-1][1], dp[n-1][2])
    }
}

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

Задача: 1049. Last Stone Weight II
Сложность: medium

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

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

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

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

😎 Решение:

fun lastStoneWeightII(stones: IntArray): Int {
    val totalSum = stones.sum()
    val halfSum = totalSum / 2
    val dp = IntArray(halfSum + 1)

    for (stone in stones) {
        for (j in halfSum downTo stone) {
            dp[j] = maxOf(dp[j], dp[j - stone] + stone)
        }
    }

    return totalSum - 2 * dp[halfSum]
}

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

Задача: 946. Validate Stack Sequences
Сложность: medium

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

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

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

class Solution {
    fun validateStackSequences(pushed: IntArray, popped: IntArray): Boolean {
        val stack = mutableListOf<Int>()
        var j = 0
        for (x in pushed) {
            stack.add(x)
            while (stack.isNotEmpty() && j < popped.size && stack.last() == popped[j]) {
                stack.removeAt(stack.size - 1)
                j++
            }
        }
        return j == popped.size
    }
}

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

Задача: 667. Beautiful Arrangement II
Сложность: medium

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

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

1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎 Решение:

fun constructArray(n: Int, k: Int): IntArray {
    val answer = mutableListOf<Int>()
    var left = 1
    var right = n
    
    for (i in 0..k) {
        if (i % 2 == 0) {
            answer.add(left)
            left++
        } else {
            answer.add(right)
            right--
        }
    }
    
    if (k % 2 == 0) {
        for (i in left..right) answer.add(i)
    } else {
        for (i in right downTo left) answer.add(i)
    }
    
    return answer.toIntArray()
}

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

Задача: 665. Non-decreasing Array
Сложность: medium

Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента.

Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1].

Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

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

1⃣Инициализация переменных:
Завести переменную count для подсчета числа изменений.
Проверить последовательность чисел в массиве nums.

2⃣Проверка условий:
Если nums[i] > nums[i + 1], то увеличиваем count.
Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо.
Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false.

3⃣Возврат результата:
Если количество изменений не превышает 1, вернуть true.

😎 Решение:

class Solution {
    fun checkPossibility(nums: IntArray): Boolean {
        var count = 0
        
        for (i in 1 until nums.size) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false
                }
                count++
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i]
                } else {
                    nums[i] = nums[i - 1]
                }
            }
        }
        
        return true
    }
}

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

Задача: 189. Rotate Array
Сложность: medium

Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.

Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

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

1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива.

2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов.

3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива.

😎 Решение:

class Solution {
    fun rotate(nums: IntArray, k: Int) {
        val n = nums.size
        val a = IntArray(n)
        for (i in nums.indices) {
            a[(i + k) % n] = nums[i]
        }
        for (i in nums.indices) {
            nums[i] = a[i]
        }
    }
}

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

Задача: 922. Sort Array By Parity II
Сложность: medium

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

Пример:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

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

1⃣Инициализировать два указателя even_idx и odd_idx для отслеживания позиций четных и нечетных индексов соответственно.

2⃣Пройти по массиву nums и для каждого элемента:
Если элемент четный, поместить его на позицию even_idx и увеличить even_idx на 2.
Если элемент нечетный, поместить его на позицию odd_idx и увеличить odd_idx на 2.

3⃣Вернуть отсортированный массив.

😎 Решение:

class Solution {
    fun sortArrayByParityII(nums: IntArray): IntArray {
        val result = IntArray(nums.size)
        var evenIdx = 0
        var oddIdx = 1
        
        for (num in nums) {
            if (num % 2 == 0) {
                result[evenIdx] = num
                evenIdx += 2
            } else {
                result[oddIdx] = num
                oddIdx += 2
            }
        }
        
        return result
    }
}

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

Задача: 724. Find Pivot Index
Сложность: easy

Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.

Пример:

Input: nums = [1,7,3,6,5,6]
Output: 3

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

1⃣Вычислите сумму всех элементов массива.

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

3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.

😎 Решение:

fun pivotIndex(nums: IntArray): Int {
    val totalSum = nums.sum()
    var leftSum = 0
    for (i in nums.indices) {
        if (leftSum == totalSum - leftSum - nums[i]) {
            return i
        }
        leftSum += nums[i]
    }
    return -1
}

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

Задача: 757. Set Intersection Size At Least Two
Сложность: hard

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

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

2⃣Инициализируйте пустое множество для хранения чисел.

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

😎 Решение:

fun minSetSize(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[1] }
    val nums = mutableListOf<Int>()
    for (interval in intervals) {
        val start = interval[0]
        val end = interval[1]
        if (nums.isEmpty() || nums.last() < start) {
            nums.add(end - 1)
            nums.add(end)
        } else if (nums.last() == end - 1) {
            nums.add(end)
        }
    }
    return nums.size
}

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

Задача: 120. Triangle
Сложность: medium

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

На каждом шаге вы можете перейти к соседнему числу в строке ниже. Более формально, если вы находитесь на индексе i в текущей строке, вы можете перейти либо к индексу i, либо к индексу i + 1 в следующей строке.

Пример:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

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

1⃣Простейший способ реализации этого заключается в перезаписи входных данных, то есть в использовании алгоритма "на месте". В подходе 2 мы рассмотрим, как модифицировать алгоритм так, чтобы он не перезаписывал входные данные, но при этом не требовал более чем O(n) дополнительного пространства.

2⃣Когда этот алгоритм завершит свою работу, каждая ячейка (строка, столбец) входного треугольника будет перезаписана минимальной суммой пути от (0, 0) (вершины треугольника) до (строка, столбец) включительно.
Совет на собеседовании: Алгоритмы "на месте" перезаписывают входные данные для экономии места, но иногда это может вызвать проблемы. Вот несколько ситуаций, когда алгоритм "на месте" может быть неуместен.

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

😎 Решение:

class Solution {
    fun minimumTotal(triangle: MutableList<MutableList<Int>>): Int {
        for (row in 1 until triangle.size) {
            for (col in 0..row) {
                var smallestAbove = Int.MAX_VALUE
                if (col > 0) {
                    smallestAbove = triangle[row - 1][col - 1]
                }
                if (col < row) {
                    smallestAbove = minOf(smallestAbove, triangle[row - 1][col])
                }
                triangle[row][col] += smallestAbove
            }
        }
        return triangle.last().minOrNull() ?: Int.MAX_VALUE
    }
}

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