Задача: 1406. Stone Game III
Сложность: hard

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

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

Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.

Пример:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

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

1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0.

2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре.

3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья.

😎 Решение:

class Solution {
    func stoneGameIII(_ stoneValue: [Int]) -> String {
        let n = stoneValue.count
        var dp = [Int](repeating: 0, count: n + 1)
        for i in stride(from: n - 1, through: 0, by: -1) {
            dp[i] = stoneValue[i] - dp[i + 1]
            if i + 2 <= n {
                dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2])
            }
            if i + 3 <= n {
                dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3])
            }
        }
        if dp[0] > 0 {
            return "Alice"
        } else if dp[0] < 0 {
            return "Bob"
        } else {
            return "Tie"
        }
    }
}

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

Задача: 1103. Distribute Candies to People
Сложность: easy

Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом:
Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку.
Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку.

Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз).

Верните массив (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет.

Пример:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

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

1⃣Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты:
p = floor(sqrt(2C+0.25)-0.5)
remainig = C - p(p+1)/2

2⃣Вычислите количество полных циклов и распределите конфеты:
rows = p // n
d[i]= i*rows + n*rows*(rows-1)/2

3⃣Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты:
d[i]+=i+n⋅rows для первых p%n людей
d[p%n]+=remaining
Верните распределение конфет d


😎 Решение:

class Solution {
    func distributeCandies(_ candies: Int, _ num_people: Int) -> [Int] {
        let n = num_people
        let p = Int((sqrt(2 * Double(candies) + 0.25) - 0.5))
        let remaining = candies - (p + 1) * p / 2
        let rows = p / n
        let cols = p % n
        
        var d = [Int](repeating: 0, count: n)
        for i in 0..<n {
            d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n
            if i < cols {
                d[i] += i + 1 + rows * n
            }
        }
        d[cols] += remaining
        return d
    }
}

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

Задача: 213. House Robber II
Сложность: medium

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

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

Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

1⃣Обработка базовых случаев:
Если в массиве nums нет домов, возвращаем 0.
Если в массиве nums только один дом, возвращаем значение этого дома.

2⃣Разделение задачи на две подзадачи:
Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию rob_simple с параметрами 0 и nums.count - 2.
Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и nums.count - 1.

3⃣Сравнение результатов и возврат максимального значения:
Возвращаем максимальное значение из двух полученных результатов.

😎 Решение:

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.isEmpty { return 0 }
        if nums.count == 1 { return nums[0] }

        let max1 = rob_simple(nums, 0, nums.count - 2)
        let max2 = rob_simple(nums, 1, nums.count - 1)

        return max(max1, max2)
    }

    func rob_simple(_ nums: [Int], _ start: Int, _ end: Int) -> Int {
        var t1 = 0
        var t2 = 0

        for i in start...end {
            let temp = t1
            let current = nums[i]
            t1 = max(current + t2, t1)
            t2 = temp
        }

        return t1
    }
}

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

Задача: 912. Sort an Array
Сложность: medium

Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью.

Пример:

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

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

1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

2⃣Разделить массив на две половины.
Рекурсивно отсортировать каждую половину.

3⃣Слить две отсортированные половины.

😎 Решение:

func mergeSort(_ nums: inout [Int]) {
    if nums.count > 1 {
        let mid = nums.count / 2
        var left_half = Array(nums[0..<mid])
        var right_half = Array(nums[mid..<nums.count])

        mergeSort(&left_half)
        mergeSort(&right_half)

        var i = 0, j = 0, k = 0
        while i < left_half.count && j < right_half.count {
            if left_half[i] < right_half[j] {
                nums[k] = left_half[i]
                i += 1
            } else {
                nums[k] = right_half[j]
                j += 1
            }
            k += 1
        }

        while i < left_half.count {
            nums[k] = left_half[i]
            i += 1
            k += 1
        }

        while j < right_half.count {
            nums[k] = right_half[j]
            j += 1
            k += 1
        }
    }
}

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

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

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