Swift | LeetCode

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

🔹 iOS Jobs | Вакансии
🔹 Flutter Dart Jobs | Вакансии
🔹 Android Jobs | Вакансии

🔸 Все каналы с вакансиями

Задача: 523. Continuous Subarray Sum
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае.

Хороший подмассив — это подмассив, который:

имеет длину не менее двух, и
сумма элементов подмассива является кратной k.
Учтите:

Подмассив — это непрерывная часть массива.
Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k.

Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

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

1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

2⃣Итеративно пройдите по всем элементам массива nums.

3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false.

😎 Решение:

class Solution {
    func checkSubarraySum(_ nums: [Int], _ k: Int) -> Bool {
        var prefixMod = 0
        var modSeen: [Int: Int] = [0: -1]
        
        for i in 0..<nums.count {
            prefixMod = (prefixMod + nums[i]) % k
            
            if let prevIndex = modSeen[prefixMod] {
                if i - prevIndex > 1 {
                    return true
                }
            } else {
                modSeen[prefixMod] = i
            }
        }
        
        return false
    }
}

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

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

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

Задача: 200. Number of Islands
Сложность: medium

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

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

Пример:

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

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

1⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS).

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

3⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.

😎 Решение:

class Solution {
    func dfs(_ grid: inout [[Character]], _ r: Int, _ c: Int) {
        let nr = grid.count
        let nc = grid[0].count

        if r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == "0" {
            return
        }

        grid[r][c] = "0"
        dfs(&grid, r - 1, c)
        dfs(&grid, r + 1, c)
        dfs(&grid, r, c - 1)
        dfs(&grid, r, c + 1)
    }

    func numIslands(_ grid: [[Character]]) -> Int {
        var grid = grid
        if grid.isEmpty {
            return 0
        }

        let nr = grid.count
        let nc = grid[0].count
        var numIslands = 0

        for r in 0..<nr {
            for c in 0..<nc {
                if grid[r][c] == "1" {
                    numIslands += 1
                    dfs(&grid, r, c)
                }
            }
        }

        return numIslands
    }
}

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

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

Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.

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

Пример:

Input: num = "69"
Output: true

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

1⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false.

2⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку.

3⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    func isStrobogrammatic(_ num: String) -> Bool {
        var rotatedString = ""
        for c in num.reversed() {
            if c == "0" || c == "1" || c == "8" {
                rotatedString.append(c)
            } else if c == "6" {
                rotatedString.append("9")
            } else if c == "9" {
                rotatedString.append("6")
            } else {
                return false
            }
        }
        return num == rotatedString
    }
}

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

Задача: 644. Maximum Average Subarray II
Сложность: hard

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

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

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

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

😎 Решение:

func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
    var currSum = nums[0..<k].reduce(0, +)
    var maxSum = currSum
    for i in k..<nums.count {
        currSum += nums[i] - nums[i - k]
        if currSum > maxSum {
            maxSum = currSum
        }
    }
    return Double(maxSum) / Double(k)
}

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

Задача: 1493. Longest Subarray of 1's After Deleting One Element
Сложность: medium

Дан бинарный массив nums, из которого следует удалить один элемент.

Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует.

Пример:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

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

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

2⃣Итерация по массиву:
При каждом элементе увеличиваем zeroCount, если это ноль.
Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1.
Обновляем longestWindow текущей длиной окна i - start.

3⃣Возврат результата:
Вернуть longestWindow.

😎 Решение:

class Solution {
    func longestSubarray(_ nums: [Int]) -> Int {
        var zeroCount = 0
        var longestWindow = 0
        var start = 0
        
        for i in 0..<nums.count {
            if nums[i] == 0 {
                zeroCount += 1
            }
            
            while zeroCount > 1 {
                if nums[start] == 0 {
                    zeroCount -= 1
                }
                start += 1
            }
            
            longestWindow = max(longestWindow, i - start)
        }
        
        return longestWindow
    }
}

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

Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy

Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.

Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

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

1⃣Создать словарь для подсчета частоты каждого числа в массиве deck.

2⃣Найти наибольший общий делитель (НОД) всех частот.

3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы.

😎 Решение:

class Solution {
    func hasGroupsSizeX(_ deck: [Int]) -> Bool {
        let count = deck.reduce(into: [:]) { counts, num in
            counts[num, default: 0] += 1
        }
        let freqValues = Array(count.values)
        let g = freqValues.reduce(freqValues[0], gcd)
        return g > 1
    }
    
    private func gcd(_ a: Int, _ b: Int) -> Int {
        var a = a, b = b
        while b != 0 {
            let temp = a % b
            a = b
            b = temp
        }
        return a
    }
}

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

Задача: 765. Couples Holding Hands
Сложность: hard

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

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

3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ.

😎 Решение:

class Solution {
    var N: Int = 0
    var pairs: [[Int]] = []
    
    func minSwapsCouples(_ row: [Int]) -> Int {
        N = row.count / 2
        pairs = Array(repeating: Array(repeating: 0, count: 2), count: N)
        for i in 0..<N {
            pairs[i][0] = row[2 * i] / 2
            pairs[i][1] = row[2 * i + 1] / 2
        }
        return solve(0)
    }
    
    func swap(_ a: Int, _ b: Int, _ c: Int, _ d: Int) {
        let t = pairs[a][b]
        pairs[a][b] = pairs[c][d]
        pairs[c][d] = t
    }
    
    func solve(_ i: Int) -> Int {
        if i == N { return 0 }
        let x = pairs[i][0], y = pairs[i][1]
        if x == y { return solve(i + 1) }
        
        var jx = 0, kx = 0, jy = 0, ky = 0
        for j in (i + 1)..<N {
            for k in 0...1 {
                if pairs[j][k] == x { jx = j; kx = k }
                if pairs[j][k] == y { jy = j; ky = k }
            }
        }
        
        swap(i, 1, jx, kx)
        let ans1 = 1 + solve(i + 1)
        swap(i, 1, jx, kx)
        
        swap(i, 0, jy, ky)
        let ans2 = 1 + solve(i + 1)
        swap(i, 0, jy, ky)
        
        return min(ans1, ans2)
    }
}

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

Задача: 978. Longest Turbulent Subarray
Сложность: medium

Дан целочисленный массив arr, верните длину максимального турбулентного подмассива массива arr.

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

Более формально, подмассив [arr[i], arr[i + 1], ..., arr[j]] массива arr считается турбулентным тогда и только тогда, когда:

Для всех i <= k < j:
arr[k] > arr[k + 1], когда k нечетное, и
arr[k] < arr[k + 1], когда k четное.
Или, для всех i <= k < j:
arr[k] > arr[k + 1], когда k четное, и
arr[k] < arr[k + 1], когда k нечетное.

Пример:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

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

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

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

3⃣Повторяйте шаг 2 до конца массива и верните максимальную длину турбулентного подмассива.

😎 Решение:

class Solution {
    func maxTurbulenceSize(_ A: [Int]) -> Int {
        let N = A.count
        var ans = 1
        var anchor = 0

        for i in 1..<N {
            let c = A[i - 1].compare(to: A[i])
            if c == .orderedSame {
                anchor = i
            } else if i == N - 1 || c.rawValue * A[i].compare(to: A[i + 1]).rawValue != -1 {
                ans = max(ans, i - anchor + 1)
                anchor = i
            }
        }

        return ans
    }
}

extension Int {
    func compare(to other: Int) -> ComparisonResult {
        if self < other {
            return .orderedAscending
        } else if self > other {
            return .orderedDescending
        } else {
            return .orderedSame
        }
    }
}

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

Задача: 30. Substring with Concatenation of All Words
Сложность: hard

Вам дана строка s и массив строк words. Все строки в words имеют одинаковую длину.

Объединенная строка — это строка, которая в точности содержит все строки любой перестановки words.

Возвращает массив начальных индексов всех объединенных подстрок в s.

Пример:

Input: s = "barfoothefoobarman", words = ["foo","bar"]  
Output: [0,9]  

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

1⃣Определяем длину слова len и количество слов cnt.

2⃣Создаем словарь wf с частотами слов в words.

3⃣Проходим по строке s, проверяя подстроки длиной cnt * len.

😎Решение:

class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        let len = words.first!.count
        let cnt = words.count

        guard s.count >= cnt * len else { return [] }
        
        let s = Array(s)
        let words = words.map(Array.init)
        let wf = words.reduce(into: [[Character]: Int]()) { $0[$1, default: 0] += 1 }
        let ws = Set(words)
        var res = [Int]()

        for i in 0...(s.count - cnt * len) {
            var sf = [[Character]: Int]()
            var j = i

            for _ in 0..<cnt {
                let w = Array(s[j..<j + len])
                guard ws.contains(w) else { break }

                let old = sf[w, default: 0]
                guard old + 1 <= wf[w]! else { break }

                sf[w] = old + 1
                j += len
            }

            guard j == i + cnt * len, sf == wf else { continue }
            res.append(i)
        }

        return res
    }
}

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

Задача: 1027. Longest Arithmetic Subsequence
Сложность: medium

Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).

Пример:

Input: nums = [3,6,9,12]
Output: 4

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

1⃣Инициализация переменных:
Создайте массив словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на элементе i с разностью d.

2⃣Заполнение массива dp:
Пройдитесь по каждому элементу массива nums.
Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].
Обновите dp[i][d] на основе значения dp[j][d].

3⃣Поиск максимальной длины:
Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d].

😎 Решение:

class Solution {
    func longestArithSeqLength(_ nums: [Int]) -> Int {
        if nums.isEmpty { return 0 }
        
        var dp = Array(repeating: [Int: Int](), count: nums.count)
        var max_length = 0
        
        for i in 0..<nums.count {
            for j in 0..<i {
                let diff = nums[i] - nums[j]
                if let length = dp[j][diff] {
                    dp[i][diff] = length + 1
                } else {
                    dp[i][diff] = 2 // Start a new sequence
                }
                max_length = max(max_length, dp[i][diff]!)
            }
        }
        
        return max_length
    }
}

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

Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

Вам дан массив цен, где prices[i] — это цена данной акции в i-й день.

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

Пример:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1

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

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

2⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй,
одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство.
В алгоритмах динамического программирования обычно мы создаем массив одного или двух измерений для сохранения промежуточных оптимальных результатов. В данной задаче мы бы использовали два массива, один массив сохранял бы результаты последовательности слева направо, а другой массив сохранял бы результаты последовательности справа налево. Для удобства мы могли бы назвать это двунаправленным динамическим программированием.

3⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i].
Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]).
Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5.
И каждый элемент в массиве right_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в правой подпоследовательности цен от индекса i до N-1, (т.е. Prices[i], Prices[i+1], ... Prices[N-1]).
Например, для правой подпоследовательности [3, 6, 4] соответствующий right_profits[3] будет равен 3, что означает покупку по цене 3 и продажу по цене 6.
Теперь, если мы разделим последовательность цен вокруг элемента с индексом i на две подпоследовательности, с левыми подпоследовательностями как Prices[0], Prices[1], ... Prices[i] и правой подпоследовательностью как Prices[i+1], ... Prices[N-1],
то общая максимальная прибыль, которую мы получим от этого разделения (обозначенная как max_profits[i]), может быть выражена следующим образом:
max_profits[i] = left_profits[i] + right_profits[i+1]

😎 Решение:

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count <= 1 {
            return 0
        }

        let length = prices.count
        var leftMin = prices[0]
        var rightMax = prices.last!

        var leftProfits = Array(repeating: 0, count: length)
        var rightProfits = Array(repeating: 0, count: length + 1)

        for l in 1..<length {
            leftProfits[l] = max(leftProfits[l - 1], prices[l] - leftMin)
            leftMin = min(leftMin, prices[l])

            let r = length - 1 - l
            rightProfits[r] = max(rightProfits[r + 1], rightMax - prices[r])
            rightMax = max(rightMax, prices[r])
        }

        var maxProfit = 0
        for i in 0..<length {
            maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i + 1])
        }

        return maxProfit
    }
}

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

Задача: 60. Permutation Sequence
Сложность: hard

Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.

Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.

Пример:

Input: n = 3, k = 3
Output: "213"

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

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

2⃣Вычислите все факториальные основы от 0 до (N−1)!.

3⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1).

😎 Решение:

class Solution {
    func getPermutation(_ n: Int, _ k: Int) -> String {
        var factorials = [Int](repeating: 1, count: n)
        var nums = [Character]()
        for i in 1..<n {
            factorials[i] = factorials[i - 1] * i
            nums.append(Character(String(i + 1)))
        }
        var k = k - 1
        var result = ""
        for i in stride(from: n - 1, through: 0, by: -1) {
            let idx = k / factorials[i]
            k -= idx * factorials[i]
            result.append(nums[idx])
            nums.remove(at: idx)
        }
        return result
    }
}

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

Задача: 127. Word Ladder
Сложность: Hard

Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:

Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

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

1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние.

2⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.

3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

import Foundation

class Solution {
    func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
        let L = beginWord.count
        var allComboDict: [String: [String]] = [:]

        wordList.forEach { word in
            for i in 0..<L {
                let newWord = "\(word.prefix(i))*\(word.suffix(L - i - 1))"
                var transformations = allComboDict[newWord, default: []]
                transformations.append(word)
                allComboDict[newWord] = transformations
            }
        }

        var queue: [(String, Int)] = [(beginWord, 1)]
        var visited: [String: Bool] = [beginWord: true]

        while !queue.isEmpty {
            let (word, level) = queue.removeFirst()
            for i in 0..<L {
                let newWord = "\(word.prefix(i))*\(word.suffix(L - i - 1))"

                if let adjacentWords = allComboDict[newWord] {
                    for adjacentWord in adjacentWords {
                        if adjacentWord == endWord {
                            return level + 1
                        }
                        if visited[adjacentWord] != true {
                            visited[adjacentWord] = true
                            queue.append((adjacentWord, level + 1))
                        }
                    }
                }
            }
        }

        return 0
    }
}

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

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

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

Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy

Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.

Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.

Пример:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

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

1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.

2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].

3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers.

😎 Решение:

class Solution {
    func luckyNumbers (_ matrix: [[Int]]) -> [Int] {
        let N = matrix.count
        let M = matrix[0].count
        
        var rowMin = [Int]()
        for i in 0..<N {
            var rMin = Int.max
            for j in 0..<M {
                rMin = min(rMin, matrix[i][j])
            }
            rowMin.append(rMin)
        }
        
        var colMax = [Int]()
        for i in 0..<M {
            var cMax = Int.min
            for j in 0..<N {
                cMax = max(cMax, matrix[j][i])
            }
            colMax.append(cMax)
        }
        
        var luckyNumbers = [Int]()
        for i in 0..<N {
            for j in 0..<M {
                if matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j] {
                    luckyNumbers.append(matrix[i][j])
                }
            }
        }
        
        return luckyNumbers
    }
}

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

Задача: 153. Find Minimum in Rotated Sorted Array
Сложность: Medium

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:

[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.

Вы должны написать алгоритм, который работает за время O(log n).

Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

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

1⃣Нахождение середины массива:
Определите элемент, находящийся посередине массива.

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

3⃣Остановка поиска при нахождении точки перегиба:
Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий:
nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом.
nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.

😎 Решение:

class Solution {
    func findMin(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return nums[0]
        }
        
        var left = 0
        var right = nums.count - 1
        
        if nums[right] > nums[0] {
            return nums[0]
        }
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            if nums[mid] > nums[mid + 1] {
                return nums[mid + 1]
            }
            
            if mid > 0 && nums[mid - 1] > nums[mid] {
                return nums[mid]
            }
            
            if nums[mid] > nums[0] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return -1
    }
}

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

Задача: 847. Shortest Path Visiting All Nodes
Сложность: hard

У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром.

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

Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

1⃣Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов.

2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps.

3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов.

😎 Решение:

class Solution {
    func shortestPathLength(_ graph: [[Int]]) -> Int {
        let n = graph.count
        if n == 1 {
            return 0
        }
        
        let endingMask = (1 << n) - 1
        var seen = Array(repeating: Array(repeating: false, count: endingMask), count: n)
        var queue = [(node: Int, mask: Int)]()
        
        for i in 0..<n {
            queue.append((i, 1 << i))
            seen[i][1 << i] = true
        }
        
        var steps = 0
        while !queue.isEmpty {
            var nextQueue = [(node: Int, mask: Int)]()
            for (node, mask) in queue {
                for neighbor in graph[node] {
                    let nextMask = mask | (1 << neighbor)
                    if nextMask == endingMask {
                        return 1 + steps
                    }
                    if !seen[neighbor][nextMask] {
                        seen[neighbor][nextMask] = true
                        nextQueue.append((neighbor, nextMask))
                    }
                }
            }
            steps += 1
            queue = nextQueue
        }
        
        return -1
    }
}

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

Задача: 284. Peeking Iterator
Сложность: medium

Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента).

Реализуйте класс PeekingIterator:
PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел.
int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент.
boolean hasNext(): Возвращает true, если в массиве еще есть элементы.
int peek(): Возвращает следующий элемент в массиве без перемещения указателя.

Пример:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

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

1⃣Инициализация итератора:
В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null.

2⃣Операция peek:
Метод peek возвращает значение next, не перемещая указатель итератора.

3⃣Операции next и hasNext:
Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException.
Метод hasNext возвращает true, если next не равно null, и false в противном случае.

😎 Решение:

class PeekingIterator {
    private var iterator: IndexingIterator<[Int]>
    private var nextElement: Int?

    init(_ nums: [Int]) {
        self.iterator = nums.makeIterator()
        self.nextElement = self.iterator.next()
    }

    func next() -> Int {
        let currentElement = nextElement
        nextElement = iterator.next()
        return currentElement!
    }

    func hasNext() -> Bool {
        return nextElement != nil
    }

    func peek() -> Int {
        return nextElement!
    }
}

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