Задача: 685. Redundant Connection II
Сложность: hard

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

Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.

Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.

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

Пример:

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

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

1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.

2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.

3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов.

😎 Решение:

class Solution {
    class OrbitResult {
        var node: Int
        var seen: Set<Int>
        init(_ n: Int, _ s: Set<Int>) {
            node = n
            seen = s
        }
    }
    
    func findRedundantDirectedConnection(_ edges: [[Int]]) -> [Int] {
        let N = edges.count
        var parent = [Int: Int]()
        var candidates = [[Int]]()
        
        for edge in edges {
            if let p = parent[edge[1]] {
                candidates.append([p, edge[1]])
                candidates.append(edge)
            } else {
                parent[edge[1]] = edge[0]
            }
        }
        
        let root = orbit(1, parent).node
        if candidates.isEmpty {
            let cycle = orbit(root, parent).seen
            var ans = [0, 0]
            for edge in edges {
                if cycle.contains(edge[0]) && cycle.contains(edge[1]) {
                    ans = edge
                }
            }
            return ans
        }
        
        var children = [Int: [Int]]()
        for (v, pv) in parent {
            children[pv, default: []].append(v)
        }
        
        var seen = [Bool](repeating: false, count: N + 1)
        seen[0] = true
        var stack = [root]
        
        while !stack.isEmpty {
            let node = stack.removeLast()
            if !seen[node] {
                seen[node] = true
                if let childNodes = children[node] {
                    stack.append(contentsOf: childNodes)
                }
            }
        }
        
        for b in seen {
            if !b {
                return candidates[0]
            }
        }
        return candidates[1]
    }
    
    func orbit(_ node: Int, _ parent: [Int: Int]) -> OrbitResult {
        var seen = Set<Int>()
        var node = node
        
        while let next = parent[node], !seen.contains(node) {
            seen.insert(node)
            node = next
        }
        
        return OrbitResult(node, seen)
    }
}

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

Задача: 1396. Design Underground System
Сложность: medium

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

Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время вычисляется на основе всех предыдущих временных интервалов поездок от startStation до endStation, которые происходили непосредственно, т.е. регистрация на startStation с последующим выходом на endStation.
Время, необходимое для поездки от startStation до endStation, может отличаться от времени поездки от endStation до startStation.
Перед вызовом getAverageTime будет как минимум один пассажир, который уже совершил поездку от startStation до endStation.
Вы можете предположить, что все вызовы методов checkIn и checkOut являются последовательными. Если пассажир регистрируется в момент времени t1, а затем выходит в момент времени t2, то t1 < t2. Все события происходят в хронологическом порядке.

Пример:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

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

1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.

2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.

3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.

😎 Решение:

cclass UndergroundSystem {
    private var journeyData = [String: (totalTime: Double, trips: Double)]()
    private var checkInData = [Int: (stationName: String, time: Int)]()

    func checkIn(_ id: Int, _ stationName: String, _ t: Int) {
        checkInData[id] = (stationName, t)
    }

    func checkOut(_ id: Int, _ stationName: String, _ t: Int) {
        let checkIn = checkInData.removeValue(forKey: id)!
        let routeKey = "\(checkIn.stationName)->\(stationName)"
        let tripTime = Double(t - checkIn.time)
        let stats = journeyData[routeKey, default: (0, 0)]
        journeyData[routeKey] = (stats.totalTime + tripTime, stats.trips + 1)
    }

    func getAverageTime(_ startStation: String, _ endStation: String) -> Double {
        let stats = journeyData["\(startStation)->\(endStation)"]!
        return stats.totalTime / stats.trips
    }
}

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

Задача: 82. Remove Duplicates from Sorted List II
Сложность: medium

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

Пример:

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

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

1⃣Инициализация "стража" и предшественника:
Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены.
Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж.

2⃣Проход по списку с проверкой на дубликаты:
Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.
Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов.

3⃣Переход к следующему узлу и возврат результата:
Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел.
Двигаем указатель head на следующий узел в списке.
После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов.

😎 Решение:

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

func deleteDuplicates(_ head: ListNode?) -> ListNode? {
    let sentinel = ListNode(0, head)
    var pred = sentinel
    var current = head
    
    while current != nil {
        if current!.next != nil && current!.val == current!.next!.val {
            while current!.next != nil && current!.val == current!.next!.val {
                current = current!.next
            }
            pred.next = current!.next
        } else {
            pred = pred.next!
        }
        current = current!.next
    }
    
    return sentinel.next
}

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

Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal
Сложность: medium

Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево.

Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

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

1⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder.

2⃣Определите вспомогательную функцию helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None.

3⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень.

😎 Решение:

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

class Solution {
    func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        var idxMap = [Int: Int]()
        var postIdx = postorder.count - 1

        func helper(_ inLeft: Int, _ inRight: Int) -> TreeNode? {
            if inLeft > inRight {
                return nil
            }
            let rootVal = postorder[postIdx]
            let root = TreeNode(rootVal)
            guard let index = idxMap[rootVal] else { return nil }
            postIdx -= 1
            root.right = helper(index + 1, inRight)
            root.left = helper(inLeft, index - 1)
            return root
        }

        for i in 0..<inorder.count {
            idxMap[inorder[i]] = i
        }
        return helper(0, inorder.count - 1)
    }
}

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

Задача: 735. Asteroid Collision
Сложность: medium

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

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

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

3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат.

😎 Решение:

func asteroidCollision(_ asteroids: [Int]) -> [Int] {
    var stack = [Int]()
    
    for asteroid in asteroids {
        var alive = true
        while alive && asteroid < 0 && !stack.isEmpty && stack.last! > 0 {
            let last = stack.removeLast()
            if last == -asteroid {
                alive = false
            } else if last > -asteroid {
                stack.append(last)
                alive = false
            }
        }
        if alive {
            stack.append(asteroid)
        }
    }
    
    return stack
}

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

Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
Сложность: hard

Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:

maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
      if (maximum_value  < arr[i]){
           maximum_value  = arr[i]
           maximum_index = i
           search_cost = search_cost + 1
      }
}
return maximum_index

Вам необходимо построить массив arr, который имеет следующие свойства:
arr содержит ровно n целых чисел.
1 <= arr[i] <= m, где (0 <= i < n).
После применения указанного алгоритма к arr, значение search_cost равно k.
Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7.

Пример:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

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

1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1.

2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений.

3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи.

😎 Решение:

class Solution {
    func numOfArrays(_ n: Int, _ m: Int, _ k: Int) -> Int {
        let MOD = 1_000_000_007
        var dp = Array(repeating: Array(repeating: Array(repeating: 0, count: k + 1), count: m + 1), count: n + 1)
        
        for num in 0...m {
            dp[n][num][0] = 1
        }
        
        for i in stride(from: n - 1, through: 0, by: -1) {
            for maxSoFar in stride(from: m, through: 0, by: -1) {
                for remain in 0...k {
                    var ans = 0
                    for num in 1...maxSoFar {
                        ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD
                    }
                    
                    if remain > 0 {
                        for num in (maxSoFar + 1)...m {
                            ans = (ans + dp[i + 1][num][remain - 1]) % MOD
                        }
                    }
                    
                    dp[i][maxSoFar][remain] = ans
                }
            }
        }
        
        return dp[0][0][k]
    }
}

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

Задача: 465. Optimal Account Balancing
Сложность: medium

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

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

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

class Solution {
    var creditList = [Int]()
    
    func minTransfers(_ transactions: [[Int]]) -> Int {
        var creditMap = [Int: Int]()
        for t in transactions {
            creditMap[t[0], default: 0] += t[2]
            creditMap[t[1], default: 0] -= t[2]
        }
        
        for amount in creditMap.values {
            if amount != 0 {
                creditList.append(amount)
            }
        }
        
        let n = creditList.count
        return dfs(0, n)
    }
    
    private func dfs(_ cur: Int, _ n: Int) -> Int {
        var cur = cur
        while cur < n && creditList[cur] == 0 {
            cur += 1
        }
        
        if cur == n {
            return 0
        }
        
        var cost = Int.max
        for nxt in cur+1..<n {
            if creditList[nxt] * creditList[cur] < 0 {
                creditList[nxt] += creditList[cur]
                cost = min(cost, 1 + dfs(cur + 1, n))
                creditList[nxt] -= creditList[cur]
            }
        }
        
        return cost
    }
}

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        var x = abs(a), y = abs(b)
        if x < y {
            return getSum(b, a)
        }
        let sign = a > 0 ? 1 : -1

        if a * b >= 0 {
            while y != 0 {
                let carry = (x & y) << 1
                x ^= y
                y = carry
            }
        } else {
            while y != 0 {
                let borrow = ((~x) & y) << 1
                x ^= y
                y = borrow
            }
        }
        return x * sign
    }
}

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

Задача: 907. Sum of Subarray Minimums
Сложность: medium

Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.

Пример:

Input: arr = [3,1,2,4]
Output: 17

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

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

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

3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.

😎 Решение:

class Solution {
    func sumSubarrayMins(_ arr: [Int]) -> Int {
        let MOD = 1_000_000_007
        let n = arr.count
        var left = [Int](repeating: 0, count: n)
        var right = [Int](repeating: 0, count: n)
        var stack = [Int]()
        
        for i in 0..<n {
            while !stack.isEmpty && arr[stack.last!] > arr[i] {
                stack.removeLast()
            }
            left[i] = stack.isEmpty ? i + 1 : i - stack.last!
            stack.append(i)
        }
        
        stack = []
        
        for i in stride(from: n - 1, through: 0, by: -1) {
            while !stack.isEmpty && arr[stack.last!] >= arr[i] {
                stack.removeLast()
            }
            right[i] = stack.isEmpty ? n - i : stack.last! - i
            stack.append(i)
        }
        
        var result = 0
        for i in 0..<n {
            result = (result + arr[i] * left[i] * right[i]) % MOD
        }
        
        return result
    }
}

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

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

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

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

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

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

😎 Решение:

class MyCircularDeque {
    private var deque: [Int]
    private var front: Int
    private var rear: Int
    private var size: Int
    private var capacity: Int

    init(_ k: Int) {
        self.capacity = k
        self.deque = [Int](repeating: 0, count: k)
        self.front = 0
        self.rear = 0
        self.size = 0
    }

    func insertFront(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        front = (front - 1 + capacity) % capacity
        deque[front] = value
        size += 1
        return true
    }

    func insertLast(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        deque[rear] = value
        rear = (rear + 1) % capacity
        size += 1
        return true
    }

    func deleteFront() -> Bool {
        if isEmpty() {
            return false
        }
        front = (front + 1) % capacity
        size -= 1
        return true
    }

    func deleteLast() -> Bool {
        if isEmpty() {
            return false
        }
        rear = (rear - 1 + capacity) % capacity
        size -= 1
        return true
    }

    func getFront() -> Int {
        if isEmpty() {
            return -1
        }
        return deque[front]
    }

    func getRear() -> Int {
        if isEmpty() {
            return -1
        }
        return deque[(rear - 1 + capacity) % capacity]
    }

    func isEmpty() -> Bool {
        return size == 0
    }

    func isFull() -> Bool {
        return size == capacity
    }
}

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