Задача: 77. Combinations
Сложность: medium

Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].

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

Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

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

1⃣Инициализировать массив ответов ans и массив для построения комбинаций curr.

2⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:
Если длина curr равна k, добавить копию curr в ans и вернуться.
Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.
Итерировать num от firstNum до firstNum + available включительно.
Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.

3⃣Вызвать backtrack с изначально пустым curr и firstNum = 1.
Вернуть ans.

😎 Решение:

class Solution {
    fun combine(n: Int, k: Int): List<List<Int>> {
        val ans = mutableListOf<List<Int>>()
        
        fun backtrack(curr: MutableList<Int>, firstNum: Int) {
            if (curr.size == k) {
                ans.add(curr.toList())
                return
            }

            val need = k - curr.size
            val remain = n - firstNum + 1
            val available = remain - need

            for (num in firstNum..(firstNum + available)) {
                curr.add(num)
                backtrack(curr, num + 1)
                curr.removeAt(curr.size - 1)
            }
        }

        backtrack(mutableListOf(), 1)
        return ans
    }
}

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

Задача: 1325. Delete Leaves With a Given Value
Сложность: medium

Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target.

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

Пример:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

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

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

2⃣Рекурсивный обход: Выполните обход в постфиксном порядке, чтобы гарантировать обработку всех потомков перед текущим узлом (root):
— Рекурсивно вызовите removeLeafNodes для левого дочернего узла root и обновите левый дочерний узел возвращаемым значением.
— Аналогично, рекурсивно вызовите removeLeafNodes для правого дочернего узла root и обновите правый дочерний узел возвращаемым значением.

3⃣Оценка узла:
— Проверьте, является ли текущий узел root листовым узлом и совпадает ли его значение с target. Если оба условия выполнены, верните null, чтобы эффективно удалить узел, не присоединяя его к родителю.
— Если узел не является листом или не совпадает с target, верните сам root.

😎 Решение:

class Solution {
    fun removeLeafNodes(root: TreeNode?, target: Int): TreeNode? {
        if (root == null) return null

        root.left = removeLeafNodes(root.left, target)
        root.right = removeLeafNodes(root.right, target)

        return if (root.left == null && root.right == null && root.`val` == target) {
            null
        } else {
            root
        }
    }
}

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

Задача: 593. Valid Square
Сложность: medium

Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат.

Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке.

Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов).

Пример:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

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

1⃣Определите функцию для вычисления расстояния между двумя точками.

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

3⃣Верните true, если хотя бы одна из проверок проходит.

😎 Решение:

class Solution {
    fun dist(p1: IntArray, p2: IntArray): Int {
        return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0])
    }

    fun check(p1: IntArray, p2: IntArray, p3: IntArray, p4: IntArray): Boolean {
        return dist(p1, p2) > 0 &&
               dist(p1, p2) == dist(p2, p3) &&
               dist(p2, p3) == dist(p3, p4) &&
               dist(p3, p4) == dist(p4, p1) &&
               dist(p1, p3) == dist(p2, p4)
    }

    fun validSquare(p1: IntArray, p2: IntArray, p3: IntArray, p4: IntArray): Boolean {
        return check(p1, p2, p3, p4) ||
               check(p1, p3, p2, p4) ||
               check(p1, p2, p4, p3)
    }
}

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

Задача: 751. IP to CIDR
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

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

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

fun ipToInt(ip: String): Int {
    val parts = ip.split(".").map { it.toInt() }
    return (parts[0] shl 24) + (parts[1] shl 16) + (parts[2] shl 8) + parts[3]
}

fun intToIp(num: Int): String {
    return "${(num shr 24) and 255}.${(num shr 16) and 255}.${(num shr 8) and 255}.${num and 255}"
}

fun cidr(ip: String, prefixLength: Int): String {
    return "$ip/$prefixLength"
}

fun findCidrBlocks(startIp: String, n: Int): List<String> {
    var start = ipToInt(startIp)
    val result = mutableListOf<String>()
    var remaining = n
    
    while (remaining > 0) {
        var maxSize = 1
        while (maxSize <= start && maxSize <= remaining) {
            maxSize = maxSize shl 1
        }
        maxSize = maxSize shr 1
        
        while (start % maxSize != 0) {
            maxSize = maxSize shr 1
        }
        
        result.add(cidr(intToIp(start), 32 - Integer.bitCount(maxSize - 1) + 1))
        start += maxSize
        remaining -= maxSize
    }
    
    return result
}

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

Задача: 1539. Kth Missing Positive Number
Сложность: easy

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

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение:

class Solution {
    fun findKthPositive(arr: IntArray, k: Int): Int {
        var k = k
        if (k <= arr[0] - 1) {
            return k
        }
        k -= arr[0] - 1
        val n = arr.size
        for (i in 0 until n - 1) {
            val currMissing = arr[i + 1] - arr[i] - 1
            if (k <= currMissing) {
                return arr[i] + k
            }
            k -= currMissing
        }
        return arr[n - 1] + k
    }
}

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

Задача: 852. Peak Index in a Mountain Array
Сложность: medium

Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются.

Верните индекс пикового элемента.

Ваша задача — решить это с временной сложностью O(log(n)).

Пример:

Input: arr = [0,1,0]

Output: 1

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

1⃣Создайте целочисленную переменную i и инициализируйте её значением 0.

2⃣Используя цикл while, проверьте, если текущий элемент, на который указывает i, меньше следующего элемента на индексе i + 1. Если arr[i] < arr[i + 1], увеличьте i на 1.

3⃣В противном случае, если arr[i] > arr[i + 1], верните i.

😎 Решение:

class Solution {
    fun peakIndexInMountainArray(arr: IntArray): Int {
        var i = 0
        while (arr[i] < arr[i + 1]) {
            i++
        }
        return i
    }
}

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

Задача: 1135. Connecting Cities With Minimum Cost
Сложность: medium

Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.

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

Стоимость - это сумма использованных стоимостей соединений.

Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

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

1⃣Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.

2⃣Итерация по рёбрам и объединение:
Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST).

3⃣Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.

😎 Решение:

class DisjointSet(n: Int) {
    private val parent = IntArray(n + 1) { it }

    fun find(x: Int): Int {
        if (parent[x] != x) {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)
        if (rootX != rootY) {
            parent[rootY] = rootX
        }
    }
}

class Solution {
    fun minimumCost(n: Int, connections: Array<IntArray>): Int {
        connections.sortBy { it[2] }
        val disjointSet = DisjointSet(n)
        var totalCost = 0
        var edgesUsed = 0

        for (connection in connections) {
            val (x, y, cost) = connection
            if (disjointSet.find(x) != disjointSet.find(y)) {
                disjointSet.union(x, y)
                totalCost += cost
                edgesUsed += 1
                if (edgesUsed == n - 1) {
                    return totalCost
                }
            }
        }
        return if (edgesUsed == n - 1) totalCost else -1
    }
}

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

Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.

Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

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

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

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

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

😎 Решение:

class Solution {
    fun longestSubstring(s: String, k: Int): Int {
        if (s.isEmpty() || k > s.length) {
            return 0
        }
        val n = s.length
        var result = 0
        
        for (start in 0 until n) {
            val countMap = IntArray(26)
            for (end in start until n) {
                countMap[s[end] - 'a']++
                if (isValid(countMap, k)) {
                    result = maxOf(result, end - start + 1)
                }
            }
        }
        return result
    }

    private fun isValid(countMap: IntArray, k: Int): Boolean {
        var countLetters = 0
        var countAtLeastK = 0
        for (count in countMap) {
            if (count > 0) countLetters++
            if (count >= k) countAtLeastK++
        }
        return countLetters == countAtLeastK
    }
}

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

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

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

Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

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

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

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

😎 Решение:

class Solution {
    fun maxLength(arr: List<String>): Int {
        fun isUnique(s: String): Boolean {
            return s.toSet().size == s.length
        }

        fun backtrack(index: Int, current: String): Int {
            if (!isUnique(current)) return 0
            var maxLength = current.length
            for (i in index until arr.size) {
                maxLength = maxOf(maxLength, backtrack(i + 1, current + arr[i]))
            }
            return maxLength
        }

        return backtrack(0, "")
    }
}

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

Задача: 515. Find Largest Value in Each Tree Row
Сложность: medium

Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

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

1⃣Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS).

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

3⃣Добавьте currMax в ans. Верните ans.

😎 Решение:

class Solution {
    fun largestValues(root: TreeNode?): List<Int> {
        if (root == null) return emptyList()
        
        val ans = mutableListOf<Int>()
        val queue = ArrayDeque<TreeNode>()
        queue.add(root)
        
        while (queue.isNotEmpty()) {
            val currentLength = queue.size
            var currMax = Int.MIN_VALUE
            
            repeat(currentLength) {
                val node = queue.removeFirst()
                currMax = maxOf(currMax, node.`val`)
                node.left?.let { queue.add(it) }
                node.right?.let { queue.add(it) }
            }
            
            ans.add(currMax)
        }
        
        return ans
    }
}

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

Задача: 1041. Robot Bounded In Circle
Сложность: medium

На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.

Пример:

Input: instructions = "GGLLGG"
Output: true

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

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

2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).

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

😎 Решение:

class Solution {
    fun isRobotBounded(instructions: String): Boolean {
        val directions = arrayOf(Pair(0, 1), Pair(1, 0), Pair(0, -1), Pair(-1, 0))
        var x = 0
        var y = 0
        var direction = 0
        
        for (instruction in instructions) {
            when (instruction) {
                'G' -> {
                    x += directions[direction].first
                    y += directions[direction].second
                }
                'L' -> direction = (direction + 3) % 4
                'R' -> direction = (direction + 1) % 4
            }
        }
        
        return (x == 0 && y == 0) || direction != 0
    }
}

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

Задача: 1228. Missing Number In Arithmetic Progression
Сложность: easy

В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1.

Из массива arr было удалено значение, которое не было первым или последним значением в массиве.

Дан массив arr, вернуть удаленное значение.

Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

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

1⃣Рассчитать разность difference между элементами арифметической прогрессии.

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

3⃣Вернуть первое ожидаемое значение, которое не совпадает с текущим значением в массиве.

😎 Решение:

class Solution {
    fun missingNumber(arr: IntArray): Int {
        val n = arr.size
        val difference = (arr[n - 1] - arr[0]) / n
        var expected = arr[0]

        for (val in arr) {
            if (val != expected) {
                return expected
            }
            expected += difference
        }
        return expected
    }
}

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

Задача: 494. Target Sum
Сложность: medium

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

Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.

Пример:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

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

1⃣Инициализация и вызов рекурсивной функции
Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target).

2⃣Рекурсивная функция calculate
Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы.

3⃣Возврат результата
После завершения всех рекурсивных вызовов верните значение счетчика решений.

😎 Решение:

class Solution {
    var count = 0

    fun findTargetSumWays(nums: IntArray, S: Int): Int {
        calculate(nums, 0, 0, S)
        return count
    }

    fun calculate(nums: IntArray, i: Int, sum: Int, S: Int) {
        if (i == nums.size) {
            if (sum == S) {
                count++
            }
        } else {
            calculate(nums, i + 1, sum + nums[i], S)
            calculate(nums, i + 1, sum - nums[i], S)
        }
    }
}

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

Задача: 247. Strobogrammatic Number II
Сложность: medium

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

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

Пример:

Input: n = 2
Output: ["11","69","88","96"]

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

1⃣Задаём пару «переворачиваемых» цифр:
("0","0"), ("1","1"), ("6","9"), ("8","8"), ("9","6").

2⃣Используем рекурсию для расчета длины всех комбинаций n, начиная с базовых случаев
n == 0→[""]
n == 1→["0", "1", "8"]

3⃣Для каждой строки generate(n - 2)вставляйте пару символов по краям.
Не добавляйте '0'в начало, если это внешний уровень ( n == finalLength).

😎 Решение:

class Solution {
    private val reversiblePairs = listOf(
        listOf('0', '0'), listOf('1', '1'), 
        listOf('6', '9'), listOf('8', '8'), listOf('9', '6')
    )
    
    private fun generateStroboNumbers(n: Int, finalLength: Int): List<String> {
        if (n == 0) {
            return listOf("")
        }
        
        if (n == 1) {
            return listOf("0", "1", "8")
        }
        
        val prevStroboNums = generateStroboNumbers(n - 2, finalLength)
        val currStroboNums = mutableListOf<String>()
        
        for (prevStroboNum in prevStroboNums) {
            for (pair in reversiblePairs) {
                if (pair[0] != '0' || n != finalLength) {
                    currStroboNums.add("${pair[0]}$prevStroboNum${pair[1]}")
                }
            }
        }
        
        return currStroboNums
    }
    
    fun findStrobogrammatic(n: Int): List<String> {
        return generateStroboNumbers(n, n)
    }
}

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

Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Сложность: medium

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

Пример:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

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

1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна.

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

3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат.

😎 Решение:

import java.util.PriorityQueue

class Solution {
    fun longestSubarray(nums: IntArray, limit: Int): Int {
        val maxHeap = PriorityQueue<IntArray> { a, b -> b[0] - a[0] }
        val minHeap = PriorityQueue<IntArray>(compareBy { it[0] })
        var left = 0
        var maxLength = 0

        for (right in nums.indices) {
            maxHeap.offer(intArrayOf(nums[right], right))
            minHeap.offer(intArrayOf(nums[right], right))

            while (maxHeap.peek()[0] - minHeap.peek()[0] > limit) {
                left = minOf(maxHeap.peek()[1], minHeap.peek()[1]) + 1
                while (maxHeap.peek()[1] < left) maxHeap.poll()
                while (minHeap.peek()[1] < left) minHeap.poll()
            }

            maxLength = maxOf(maxLength, right - left + 1)
        }

        return maxLength
    }
}

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

Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

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

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

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

😎 Решение:

class Solution {
    private fun overlap(a: IntArray, b: IntArray): Boolean {
        return a[0] <= b[1] && b[0] <= a[1]
    }

    private fun buildGraph(intervals: Array<IntArray>): HashMap<List<Int>, MutableList<IntArray>> {
        val graph = HashMap<List<Int>, MutableList<IntArray>>()
        for (i in intervals.indices) {
            for (j in i + 1 until intervals.size) {
                if (overlap(intervals[i], intervals[j])) {
                    graph.getOrPut(intervals[i].toList()) { mutableListOf() }.add(intervals[j])
                    graph.getOrPut(intervals[j].toList()) { mutableListOf() }.add(intervals[i])
                }
            }
        }
        return graph
    }

    private fun mergeNodes(nodes: List<IntArray>): IntArray {
        val minStart = nodes.minOf { it[0] }
        val maxEnd = nodes.maxOf { it[1] }
        return intArrayOf(minStart, maxEnd)
    }

    private fun getComponents(
        graph: HashMap<List<Int>, MutableList<IntArray>>,
        intervals: Array<IntArray>
    ): Pair<HashMap<Int, MutableList<IntArray>>, Int> {
        val visited = mutableSetOf<List<Int>>()
        var compNumber = 0
        val nodesInComp = HashMap<Int, MutableList<IntArray>>()

        fun markComponentDFS(start: IntArray) {
            val stack = mutableListOf(start)
            while (stack.isNotEmpty()) {
                val node = stack.removeLast().toList()
                if (node !in visited) {
                    visited.add(node)
                    nodesInComp.getOrPut(compNumber) { mutableListOf() }.add(start)
                    graph[node]?.forEach { stack.add(it) }
                }
            }
        }

        for (interval in intervals) {
            if (interval.toList() !in visited) {
                markComponentDFS(interval)
                compNumber++
            }
        }

        return Pair(nodesInComp, compNumber)
    }

    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        val (graph, nodesInComp, numberComps) = buildGraph(intervals).let {
            val (nodesInComp, numberComps) = getComponents(it, intervals)
            Triple(it, nodesInComp, numberComps)
        }

        return Array(numberComps) { comp ->
            mergeNodes(nodesInComp[comp]!!)
        }
    }
}

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

Задача: 756. Pyramid Transition Matrix
Сложность: medium

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

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

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

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

😎 Решение:

class Solution {
    fun pyramidTransition(bottom: String, allowed: List<String>): Boolean {
        val allowedDict = mutableMapOf<String, MutableList<Char>>()

        for (pattern in allowed) {
            val key = pattern.substring(0, 2)
            val value = pattern[2]
            allowedDict.computeIfAbsent(key) { mutableListOf() }.add(value)
        }

        return canBuild(bottom, allowedDict)
    }

    private fun canBuild(currentLevel: String, allowedDict: Map<String, List<Char>>): Boolean {
        if (currentLevel.length == 1) return true

        val nextLevelOptions = mutableListOf<List<Char>>()
        for (i in 0 until currentLevel.length - 1) {
            val key = currentLevel.substring(i, i + 2)
            if (!allowedDict.containsKey(key)) return false
            nextLevelOptions.add(allowedDict[key]!!)
        }

        return canBuildNextLevel(nextLevelOptions, 0, "", allowedDict)
    }

    private fun canBuildNextLevel(options: List<List<Char>>, index: Int, nextLevel: String, allowedDict: Map<String, List<Char>>): Boolean {
        if (index == options.size) return canBuild(nextLevel, allowedDict)
        for (option in options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true
        }
        return false
    }
}

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

Задача: 65. Valid Number
Сложность: hard

Учитывая строку s, определите, является ли s валидным числом.

Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".

Формально, валидное число определяется с использованием одного из следующих определений:

Целое число с необязательным показателем степени.
Десятичное число с необязательным показателем степени.
Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры.

Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений:

Цифры, за которыми следует точка '.'.
Цифры, за которыми следует точка '.', за которой следуют цифры.
Точка '.', за которой следуют цифры.
Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число.

Цифры определяются как одна или более цифр.

Пример:

Input: s = "0"

Output: true

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

1⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true.

2⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число.

3⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры.

😎 Решение:

class Solution {
    fun isNumber(s: String): Boolean {
        var seenDigit = false
        var seenExponent = false
        var seenDot = false

        for ((i, c) in s.withIndex()) {
            when {
                c.isDigit() -> seenDigit = true
                c == '+' || c == '-' -> {
                    if (i > 0 && s[i - 1] != 'e' && s[i - 1] != 'E') {
                        return false
                    }
                }
                c == 'e' || c == 'E' -> {
                    if (seenExponent || !seenDigit) {
                        return false
                    }
                    seenExponent = true
                    seenDigit = false // Reset seenDigit after exponent
                }
                c == '.' -> {
                    if (seenDot || seenExponent) {
                        return false
                    }
                    seenDot = true
                }
                else -> return false
            }
        }
        return seenDigit
    }
}

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

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

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1⃣Сначала отсортируйте массив nums.

2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

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

😎 Решение:

class Solution {
    fun missingNumber(nums: IntArray): Int {
        nums.sort()
        if (nums.last() != nums.size) {
            return nums.size
        } else if (nums.first() != 0) {
            return 0
        }
        for (i in 1 until nums.size) {
            val expectedNum = nums[i - 1] + 1
            if (nums[i] != expectedNum) {
                return expectedNum
            }
        }
        return -1
    }
}

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

Задача: 936. Stamping The Sequence
Сложность: hard

Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив

Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

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

1⃣Инициализировать переменные:
s как массив символов '?', длиной target.length.
res как список для хранения результатов.
done как массив булевых значений для отслеживания того, какие позиции уже штампованы.
target как массив символов для удобства.

2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i.
Использовать функцию doStamp для штампования stamp в target начиная с индекса i.
Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length):
Перебрать все возможные начальные позиции для штампа.
Проверить, можно ли штамповать в текущей позиции.
Если можно, штамповать и добавить индекс в res.

3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив.

😎 Решение:

class Solution {
    fun movesToStamp(stamp: String, target: String): IntArray {
        val s = stamp.toCharArray()
        val t = target.toCharArray()
        val m = s.size
        val n = t.size
        val res = mutableListOf<Int>()
        val done = BooleanArray(n)
        
        fun canStamp(i: Int): Boolean {
            for (j in 0 until m) {
                if (t[i + j] != '?' && t[i + j] != s[j]) {
                    return false
                }
            }
            return true
        }
        
        fun doStamp(i: Int) {
            for (j in 0 until m) {
                t[i + j] = '?'
            }
            res.add(i)
            done[i] = true
        }
        
        var changed = true
        while (changed) {
            changed = false
            for (i in 0..(n - m)) {
                if (!done[i] && canStamp(i)) {
                    doStamp(i)
                    changed = true
                }
            }
        }
        
        return if (t.all { it == '?' }) res.reversed().toIntArray() else IntArray(0)
    }
}

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