Задача: 1473. Paint House III
Сложность: hard

Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.

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

Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.

Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

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

1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.

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

3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.

😎 Решение:

class Solution {
    let MAX_COST = 1000001
    var memo = [[[Int?]]](repeating: [[Int?]](repeating: [Int?](repeating: nil, count: 22), count: 102), count: 102)
    
    func findMinCost(_ houses: [Int], _ cost: [[Int]], _ targetCount: Int, _ currIndex: Int, _ neighborhoodCount: Int, _ prevHouseColor: Int) -> Int {
        if currIndex == houses.count {
            return neighborhoodCount == targetCount ? 0 : MAX_COST
        }
        
        if neighborhoodCount > targetCount {
            return MAX_COST
        }
        
        if let memoValue = memo[currIndex][neighborhoodCount][prevHouseColor] {
            return memoValue
        }
        
        var minCost = MAX_COST
        
        if houses[currIndex] != 0 {
            let newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0)
            minCost = findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
        } else {
            for color in 1...cost[0].count {
                let newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0)
                let currCost = cost[currIndex][color - 1] + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
                minCost = min(minCost, currCost)
            }
        }
        
        memo[currIndex][neighborhoodCount][prevHouseColor] = minCost
        return minCost
    }
    
    func minCost(_ houses: [Int], _ cost: [[Int]], _ m: Int, _ n: Int, _ target: Int) -> Int {
        let answer = findMinCost(houses, cost, target, 0, 0, 0)
        return answer == MAX_COST ? -1 : answer
    }
}

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

Задача: 775. Global and Local Inversions
Сложность: medium

Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].

Число глобальных инверсий — это количество различных пар (i, j), где:

0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:

0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.

Пример:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

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

1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1.

2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии.

3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false.

😎 Решение:

class Solution {
    func isIdealPermutation(_ A: [Int]) -> Bool {
        let N = A.count
        for i in 0..<N {
            for j in i+2..<N {
                if A[i] > A[j] { 
                    return false 
                }
            }
        }
        return true
    }
}

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

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: steps = 3, arrLen = 2
Output: 4

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

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

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

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

😎 Решение:

class Solution {
    func numWays(_ steps: Int, _ arrLen: Int) -> Int {
        let mod = 1_000_000_007
        let max_pos = min(arrLen - 1, steps)
        var dp = [Int](repeating: 0, count: max_pos + 1)
        dp[0] = 1
        for _ in 0..<steps {
            var new_dp = [Int](repeating: 0, count: max_pos + 1)
            for i in 0...max_pos {
                new_dp[i] = dp[i] % mod
                if i > 0 {
                    new_dp[i] = (new_dp[i] + dp[i - 1]) % mod
                }
                if i < max_pos {
                    new_dp[i] = (new_dp[i] + dp[i + 1]) % mod
                }
            }
            dp = new_dp
        }
        return dp[0]
    }
}

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

Задача: 669. Trim a Binary Search Tree
Сложность: medium

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ.

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

3⃣В противном случае обрезаем обе стороны дерева.

😎 Решение:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
}

class Solution {
    func trimBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> TreeNode? {
        guard let root = root else { return nil }
        if root.val > high { return trimBST(root.left, low, high) }
        if root.val < low { return trimBST(root.right, low, high) }
        root.left = trimBST(root.left, low, high)
        root.right = trimBST(root.right, low, high)
        return root
    }
}

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

Задача: 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 {
    func diagonalSort(_ mat: [[Int]]) -> [[Int]] {
        var mat = mat
        let m = mat.count
        let n = mat[0].count
        
        var diagonals = [Int: PriorityQueue<Int>]()
        
        for row in 0..<m {
            for col in 0..<n {
                let key = row - col
                if diagonals[key] == nil {
                    diagonals[key] = PriorityQueue<Int>(order: <)
                }
                diagonals[key]?.push(mat[row][col])
            }
        }
        
        for row in 0..<m {
            for col in 0..<n {
                let key = row - col
                mat[row][col] = diagonals[key]?.pop() ?? 0
            }
        }
        
        return mat
    }
}

struct PriorityQueue<T: Comparable> {
    private var heap: [T]
    private let order: (T, T) -> Bool

    init(order: @escaping (T, T) -> Bool) {
        self.heap = []
        self.order = order
    }

    var isEmpty: Bool { return heap.isEmpty }
    var count: Int { return heap.count }

    mutating func push(_ element: T) {
        heap.append(element)
        siftUp(heap.count - 1)
    }

    mutating func pop() -> T? {
        guard !heap.isEmpty else { return nil }
        if heap.count == 1 {
            return heap.removeFirst()
        } else {
            let value = heap[0]
            heap[0] = heap.removeLast()
            siftDown(0)
            return value
        }
    }

    private mutating func siftUp(_ index: Int) {
        var childIndex = index
        let child = heap[childIndex]
        var parentIndex = (childIndex - 1) / 2
        
        while childIndex > 0 && order(child, heap[parentIndex]) {
            heap[childIndex] = heap[parentIndex]
            childIndex = parentIndex
            parentIndex = (childIndex - 1) / 2
        }
        heap[childIndex] = child
    }

    private mutating func siftDown(_ index: Int) {
        var parentIndex = index
        let count = heap.count
        let element = heap[parentIndex]
        var childIndex = (parentIndex * 2) + 1

        while childIndex < count {
            let rightChildIndex = childIndex + 1
            if rightChildIndex < count && order(heap[rightChildIndex], heap[childIndex]) {
                childIndex = rightChildIndex
            }
            if order(heap[childIndex], element) {
                heap[parentIndex] = heap[childIndex]
                parentIndex = childIndex
                childIndex = (parentIndex * 2) + 1
            } else {
                break
            }
        }
        heap[parentIndex] = element
    }
}

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

Задача: 414. Third Maximum Number
Сложность: easy

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

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

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

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

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

3⃣Если третье максимальное число существует, верните его. В противном случае, верните первое максимальное число.

😎 Решение:

func thirdMax(_ nums: [Int]) -> Int {
    var first: Int? = nil
    var second: Int? = nil
    var third: Int? = nil
    
    for num in nums {
        if num == first || num == second || num == third {
            continue
        }
        if first == nil || num > first! {
            third = second
            second = first
            first = num
        } else if second == nil || num > second! {
            third = second
            second = num
        } else if third == nil || num > third! {
            third = num
        }
    }
    
    return third ?? first!
}

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

Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard

Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.

Пример:

Input: n = 2, m = 3
Output: 3

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

1⃣Инициализация рекурсивной функции:
Функция принимает размеры прямоугольника n x m.

2⃣Базовый случай:
Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия.

3⃣Рекурсивный случай:
Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

class Solution {
    func tilingRectangle(_ n: Int, _ m: Int) -> Int {
        var dp = Array(repeating: Array(repeating: Int.max, count: m + 1), count: n + 1)
        
        for i in 1...min(n, m) {
            dp[i][i] = 1
        }
        
        for h in 1...n {
            for w in 1...m {
                if h == w { continue }
                for i in 1...h / 2 {
                    dp[h][w] = min(dp[h][w], dp[i][w] + dp[h - i][w])
                }
                for j in 1...w / 2 {
                    dp[h][w] = min(dp[h][w], dp[h][j] + dp[h][w - j])
                }
            }
        }
        return dp[n][m]
    }
}

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

Задача: 1035. Uncrossed Lines
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.

Пример:

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

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

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

2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.

3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].

😎 Решение:

class Solution {
    func maxUncrossedLines(_ nums1: [Int], _ nums2: [Int]) -> Int {
        let m = nums1.count, n = nums2.count
        var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)

        for i in 1...m {
            for j in 1...n {
                if nums1[i - 1] == nums2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }

        return dp[m][n]
    }
}

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

Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    func wordPatternMatch(_ pattern: String, _ s: String) -> Bool {
        var symbolMap = [Character: String]()
        var wordSet = Set<String>()
        return isMatch(s, 0, pattern, 0, &symbolMap, &wordSet)
    }

    private func isMatch(_ s: String, _ sIndex: Int, _ pattern: String, _ pIndex: Int,
                         _ symbolMap: inout [Character: String], _ wordSet: inout Set<String>) -> Bool {
        if pIndex == pattern.count {
            return sIndex == s.count
        }
        let symbol = pattern[pattern.index(pattern.startIndex, offsetBy: pIndex)]
        if let word = symbolMap[symbol] {
            if !s.hasPrefix(word, from: sIndex) {
                return false
            }
            return isMatch(s, sIndex + word.count, pattern, pIndex + 1, &symbolMap, &wordSet)
        }
        for k in sIndex + 1...s.count {
            let newWord = String(s[s.index(s.startIndex, offsetBy: sIndex)..<s.index(s.startIndex, offsetBy: k)])
            if wordSet.contains(newWord) {
                continue
            }
            symbolMap[symbol] = newWord
            wordSet.insert(newWord)
            if isMatch(s, k, pattern, pIndex + 1, &symbolMap, &wordSet) {
                return true
            }
            symbolMap[symbol] = nil
            wordSet.remove(newWord)
        }
        return false
    }
}

extension String {
    func hasPrefix(_ prefix: String, from index: Int) -> Bool {
        return self[index..<index + prefix.count] == prefix
    }

    subscript (bounds: Range<Int>) -> Substring {
        let start = index(startIndex, offsetBy: bounds.lowerBound)
        let end = index(startIndex, offsetBy: bounds.upperBound)
        return self[start..<end]
    }
}

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

Задача: 934. Shortest Bridge
Сложность: medium

Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.

Пример:

Input: grid = [[0,1],[1,0]]
Output: 1

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

1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.

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

3⃣Вернуть длину кратчайшего пути.

😎 Решение:

class Solution {
    func shortestBridge(_ grid: [[Int]]) -> Int {
        let n = grid.count
        var grid = grid
        
        func neighbors(_ x: Int, _ y: Int) -> [(Int, Int)] {
            return [(-1, 0), (1, 0), (0, -1), (0, 1)].map { (dx, dy) in (x + dx, y + dy) }.filter { (nx, ny) in 0 <= nx && nx < n && 0 <= ny && ny < n }
        }
        
        func bfs(_ queue: [(Int, Int)]) -> Int {
            var queue = queue
            var visited = Set(queue)
            var steps = 0
            while !queue.isEmpty {
                var newQueue = [(Int, Int)]()
                for (x, y) in queue {
                    for (nx, ny) in neighbors(x, y) {
                        if !visited.contains((nx, ny)) {
                            if grid[nx][ny] == 1 {
                                return steps
                            }
                            visited.insert((nx, ny))
                            newQueue.append((nx, ny))
                        }
                    }
                }
                queue = newQueue
                steps += 1
            }
            return -1
        }
        
        func findFirstIsland() -> [(Int, Int)] {
            for i in 0..<n {
                for j in 0..<n {
                    if grid[i][j] == 1 {
                        var queue = [(i, j)]
                        grid[i][j] = -1
                        var island = [(i, j)]
                        while !queue.isEmpty {
                            let (x, y) = queue.removeFirst()
                            for (nx, ny) in neighbors(x, y) {
                                if grid[nx][ny] == 1 {
                                    grid[nx][ny] = -1
                                    queue.append((nx, ny))
                                    island.append((nx, ny))
                                }
                            }
                        }
                        return island
                    }
                }
            }
            return []
        }
        
        let island = findFirstIsland()
        return bfs(island)
    }
}

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

Задача: №17. Letter Combinations of a Phone Number
Сложность: medium

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Пример:

Input: digits = "23"  
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]  

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

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

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

3⃣Вернуть итоговый список комбинаций.

😎 Решение:

class Solution {
    private let mat: [Character: [String]] = [
        "2": ["a","b","c"], "3": ["d","e","f"], "4": ["g","h","i"],
        "5": ["j","k","l"], "6": ["m","n","o"], "7": ["p","q","r","s"],
        "8": ["t","u","v"], "9": ["w","x","y","z"]
    ]

    func letterCombinations(_ digits: String) -> [String] {
        guard !digits.isEmpty else { return [] }
        var res = [""]
        
        for digit in digits {
            guard let letters = mat[digit] else { continue }
            res = res.flatMap { prefix in letters.map { prefix + $0 } }
        }
        
        return res
    }
}

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

Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

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

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

class Solution {
    func atMostNGivenDigitSet(_ digits: [String], _ n: Int) -> Int {
        let s = String(n)
        let K = s.count
        var dp = [Int](repeating: 0, count: K + 1)
        dp[K] = 1

        for i in stride(from: K - 1, through: 0, by: -1) {
            for d in digits {
                let sc = s[s.index(s.startIndex, offsetBy: i)]
                if d < String(sc) {
                    dp[i] += Int(pow(Double(digits.count), Double(K - i - 1)))
                } else if d == String(sc) {
                    dp[i] += dp[i + 1]
                }
            }
        }

        var total = dp[0]
        for i in 1..<K {
            total += Int(pow(Double(digits.count), Double(i)))
        }

        return total
    }
}

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

Задача: 594. Longest Harmonious Subsequence
Сложность: easy

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

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

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

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

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

3⃣Верните максимальную длину гармоничной подпоследовательности.

😎 Решение:

class Solution {
    func findLHS(_ nums: [Int]) -> Int {
        var countDict = [Int: Int]()
        var res = 0
        
        for num in nums {
            countDict[num, default: 0] += 1
            if let countPlusOne = countDict[num + 1] {
                res = max(res, countDict[num]! + countPlusOne)
            }
            if let countMinusOne = countDict[num - 1] {
                res = max(res, countDict[num]! + countMinusOne)
            }
        }
        
        return res
    }
}

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

Задача: 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 {
    func calculate(_ low: Int, _ high: Int) -> Int {
        if low >= high {
            return 0
        }
        var minres = Int.max
        for i in low...high {
            let res = i + max(calculate(i + 1, high), calculate(low, i - 1))
            minres = min(res, minres)
        }
        return minres
    }

    func getMoneyAmount(_ n: Int) -> Int {
        return calculate(1, n)
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив previousEnd.next = node.
Настройте указатели узла: node.prev = previousEnd и node.next = tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.

2⃣Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev.
Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.

3⃣Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val.
put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.

😎 Решение:

class Node {
    var key: Int
    var value: Int
    var next: Node?
    var prev: Node?

    init(_ key: Int, _ value: Int) {
        self.key = key
        self.value = value
    }
}

class LRUCache {
    private var capacity: Int
    private var dict = [Int: Node]()
    private let head: Node
    private let tail: Node

    init(_ capacity: Int) {
        self.capacity = capacity
        head = Node(-1, -1)
        tail = Node(-1, -1)
        head.next = tail
        tail.prev = head
    }

    func get(_ key: Int) -> Int {
        guard let node = dict[key] else {
            return -1
        }
        remove(node)
        add(node)
        return node.value
    }

    func put(_ key: Int, _ value: Int) {
        if let node = dict[key] {
            remove(node)
        }
        let newNode = Node(key, value)
        add(newNode)
        dict[key] = newNode
        if dict.count > capacity {
            if let nodeToDelete = head.next {
                remove(nodeToDelete)
                dict.removeValue(forKey: nodeToDelete.key)
            }
        }
    }

    private func add(_ node: Node) {
        let prev = tail.prev
        prev?.next = node
        node.prev = prev
        node.next = tail
        tail.prev = node
    }

    private func remove(_ node: Node) {
        let prev = node.prev
        let next = node.next
        prev?.next = next
        next?.prev = prev
    }
}

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

Задача: 553. Optimal Division
Сложность: medium

Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой.

Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4".
Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным.

Верните соответствующее выражение, которое имеет максимальное значение в строковом формате.

Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

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

1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе.

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

3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его.

😎 Решение:

class Solution {
    private func addStrings(_ num1: [Int], _ num2: [Int]) -> [Int] {
        var ans = [Int]()
        var carry = 0
        let n1 = num1.count
        let n2 = num2.count

        for i in 0..<max(n1, n2) + 1 {
            let digit1 = i < n1 ? num1[i] : 0
            let digit2 = i < n2 ? num2[i] : 0
            let sum = digit1 + digit2 + carry
            carry = sum / 10
            ans.append(sum % 10)
        }
        return ans
    }

    private func multiplyOneDigit(_ firstNumber: String, _ secondNumberDigit: Character, _ numZeros: Int) -> [Int] {
        var currentResult = [Int](repeating: 0, count: numZeros)
        var carry = 0

        for digit in firstNumber {
            let multiplication = (secondNumberDigit.wholeNumberValue! * digit.wholeNumberValue!) + carry
            carry = multiplication / 10
            currentResult.append(multiplication % 10)
        }
        if carry != 0 {
            currentResult.append(carry)
        }
        return currentResult
    }

    func multiply(_ firstNumber: String, _ secondNumber: String) -> String {
        if firstNumber == "0" || secondNumber == "0" {
            return "0"
        }

        let firstNumber = String(firstNumber.reversed())
        let secondNumber = String(secondNumber.reversed())

        var ans = [Int](repeating: 0, count: firstNumber.count + secondNumber.count)

        for (i, digit) in secondNumber.enumerated() {
            ans = addStrings(multiplyOneDigit(firstNumber, digit, i), ans)
        }

        while ans.last == 0 {
            ans.removeLast()
        }

        return ans.reversed().map { String($0) }.joined()
    }
}

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

Задача: 680. Valid Palindrome II
Сложность: easy

Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее.

Пример:

Input: s = "aba"
Output: true

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

1⃣Создайте вспомогательную функцию checkPalindrome, которая принимает строку s и два указателя i и j. Эта функция возвращает логическое значение, указывающее, является ли подстрока s.substring(i, j) палиндромом.

2⃣Инициализируйте два указателя: i = 0 и j = s.length() - 1. Пока i < j, проверьте, совпадают ли символы в индексах i и j. Если нет, это значит, что нам нужно удалить один из этих символов.

3⃣Попробуйте оба варианта, используя checkPalindrome. Верните true, если либо checkPalindrome(s, i, j - 1), либо checkPalindrome(s, i + 1, j) возвращает true. Если мы выходим из цикла while, это значит, что исходная строка является палиндромом. Поскольку нам не нужно было использовать удаление, следует вернуть true.

😎 Решение:

class Solution {
    private func checkPalindrome(_ s: String, _ i: Int, _ j: Int) -> Bool {
        var i = i
        var j = j
        let sArray = Array(s)
        
        while i < j {
            if sArray[i] != sArray[j] {
                return false
            }
            i += 1
            j -= 1
        }
        
        return true
    }
    
    func validPalindrome(_ s: String) -> Bool {
        var i = 0
        var j = s.count - 1
        let sArray = Array(s)
        
        while i < j {
            if sArray[i] != sArray[j] {
                return checkPalindrome(s, i, j - 1) || checkPalindrome(s, i + 1, j)
            }
            i += 1
            j -= 1
        }
        
        return true
    }
}

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

Задача: 1480. Running Sum of 1d Array
Сложность: easy

Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]).

Верните массив текущих сумм для nums.

Пример:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

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

1⃣Инициализация:
Определите массив result.
Инициализируйте первый элемент массива result первым элементом входного массива nums.

2⃣Вычисление текущих сумм:
На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result.

3⃣Повторение для всех индексов:
Повторите шаг 2 для всех индексов от 1 до n-1.

😎 Решение:

class Solution {
    func runningSum(_ nums: [Int]) -> [Int] {
        var result = [Int](repeating: 0, count: nums.count)
        result[0] = nums[0]
        for i in 1..<nums.count {
            result[i] = result[i - 1] + nums[i]
        }
        return result
    }
}

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

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

class Solution {
    func isCompleteTree(_ root: TreeNode?) -> Bool {
        if root == nil {
            return true
        }

        var queue = [TreeNode?]()
        queue.append(root)
        var nullNodeFound = false

        while !queue.isEmpty {
            let node = queue.removeFirst()
            
            if node == nil {
                nullNodeFound = true
            } else {
                if nullNodeFound {
                    return false
                }
                queue.append(node?.left)
                queue.append(node?.right)
            }
        }
        return true
    }
}

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

Задача: 941. Valid Mountain Array
Сложность: easy

Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Пример:

Input: arr = [2,1]
Output: false

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

1⃣Убедиться, что длина массива не меньше 3.

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

3⃣Вернуть true, если оба условия выполнены, иначе вернуть false.

😎 Решение:

class Solution {
    func validMountainArray(_ arr: [Int]) -> Bool {
        if arr.count < 3 {
            return false
        }
        
        var i = 1
        while i < arr.count && arr[i] > arr[i - 1] {
            i += 1
        }
        
        if i == 1 || i == arr.count {
            return false
        }
        
        while i < arr.count && arr[i] < arr[i - 1] {
            i += 1
        }
        
        return i == arr.count
    }
}

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

Задача: 25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

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

2⃣Используем фиктивный узел (dummy) для удобного управления указателями.

3⃣Переворачиваем группы по k узлов, изменяя связи в списке.

😎Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil || k == 1 {
        return head
    }
    
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    var next: ListNode?
    var prev: ListNode? = dummy
    
    var count = 0
    while current?.next != nil {
        current = current?.next
        count += 1
    }
    
    while count >= k {
        current = prev?.next
        next = current?.next
        for _ in 1..<k {
            current?.next = next?.next
            next?.next = prev?.next
            prev?.next = next
            next = current?.next
        }
        prev = current
        count -= k
    }
    
    return dummy.next
}

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