Swift | LeetCode

Задача: 188. Best Time to Buy and Sell Stock IV Сложность: hard Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k. Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз. Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить). Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

👨‍💻 Алгоритм: 1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции). 2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием: dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой). dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей). 3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов. 😎 Решение:

class Solution {
    func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
        let n = prices.count
        if n <= 0 || k <= 0 { return 0 }
        if k * 2 >= n {
            return prices.dropFirst().enumerated().reduce(0) { $0 + max(0, prices[$1.offset + 1] - prices[$1.offset]) }
        }
        var dp = Array(repeating: Array(repeating: [Int.min / 2, Int.min / 2], count: k + 1), count: n)
        dp[0][0][0] = 0
        dp[0][1][1] = -prices[0]

        for i in 1..<n {
            for j in 0...k {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
                if j > 0 {
                    dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
                }
            }
        }
        return dp[n - 1].map { $0[0] }.max() ?? 0
    }
}

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

Задача: №18. 4Sum Сложность: medium Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что: - 0 <= a, b, c, d < n - a, b, c и d различны. - nums[a] + nums[b] + nums[c] + nums[d] == target Вы можете вернуть ответ в любом порядке. Пример:

Input: nums = [1,0,-1,0,-2,2], target = 0  
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]  

👨‍💻 Алгоритм: 1⃣Отсортировать массив для удобного пропуска дубликатов и эффективного поиска. 2⃣Использовать два вложенных цикла для выбора первых двух чисел и два указателя для поиска оставшихся двух чисел. 3⃣Обрабатывать дубликаты, чтобы избежать повторяющихся четверок. 😎 Решение:

class Solution {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        let len = nums.count
        guard len >= 4 else { return [] }
        
        var result = [[Int]]()
        let sort = nums.sorted()
        
        for a in 0..<(len - 3) {
            if a > 0, sort[a] == sort[a - 1] { continue }
            for b in (a + 1)..<(len - 2) {
                if b > a + 1, sort[b] == sort[b - 1] { continue }
                
                var c = b + 1, d = len - 1
                while c < d {
                    let sum = sort[a] + sort[b] + sort[c] + sort[d]
                    if sum == target {
                        result.append([sort[a], sort[b], sort[c], sort[d]])
                        repeat { c += 1 } while c < d && sort[c] == sort[c - 1]
                        repeat { d -= 1 } while c < d && sort[d] == sort[d + 1]
                    } else if sum < target {
                        c += 1
                    } else {
                        d -= 1
                    }
                }
            }
        }
        return result
    }
}

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

Задача: 315. Count of Smaller Numbers After Self Сложность: hard Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i]. Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

👨‍💻 Алгоритм: 1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3⃣Верните результат. 😎 Решение:

class Solution {
    func countSmaller(_ nums: [Int]) -> [Int] {
        let offset = 10000 
        let size = 2 * 10000 + 1
        var tree = [Int](repeating: 0, count: size * 2)
        var result = [Int]()
        
        for num in nums.reversed() {
            let smallerCount = query(0, num + offset, tree, size)
            result.append(smallerCount)
            update(num + offset, 1, tree, size)
        }
        
        return result.reversed()
    }

    private func update(_ index: Int, _ value: Int, _ tree: inout [Int], _ size: Int) {
        var idx = index + size
        tree[idx] += value
        while idx > 1 {
            idx /= 2
            tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]
        }
    }

    private func query(_ left: Int, _ right: Int, _ tree: [Int], _ size: Int) -> Int {
        var result = 0
        var l = left + size 
        var r = right + size
        while l < r {
            if l % 2 == 1 {
                result += tree[l]
                l += 1
            }
            l /= 2
            if r % 2 == 1 {
                r -= 1
                result += tree[r]
            }
            r /= 2
        }
        return result
    }
}

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

Задача: 634. Find the Derangement of An Array Сложность: medium В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7. Пример:

Input: n = 3
Output: 2

👨‍💻 Алгоритм: 1⃣Инициализация массива для хранения результатов Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0. 2⃣Вычисление количества отклонений Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD. 3⃣Возвращение результата Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7. 😎 Решение:

import Foundation

func countDerangements(_ n: Int) -> Int {
    let MOD = 1_000_000_007
    if n == 0 {
        return 1
    }
    if n == 1 {
        return 0
    }
    
    var dp = [Int](repeating: 0, count: n + 1)
    dp[0] = 1
    dp[1] = 0
    
    for i in 2...n {
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
    }
    
    return dp[n]
}

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

Задача: 201. Bitwise AND of Numbers Range Сложность: medium Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно. Пример:

Input: left = 5, right = 7
Output: 4

👨‍💻 Алгоритм: 1⃣Сдвигать left и right вправо, пока они не станут равными. 2⃣Подсчитать количество сдвигов. 3⃣Сдвинуть left влево на количество сдвигов и вернуть результат. 😎 Решение:

class Solution {
    func rangeBitwiseAnd(_ left: Int, _ right: Int) -> Int {
        var left = left
        var right = right
        var shift = 0
        
        while left < right {
            left >>= 1
            right >>= 1
            shift += 1
        }
        
        return left << shift
    }
}

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

Задача: 1137. N-th Tribonacci Number Сложность: easy Трибоначчи последовательность Tn определяется следующим образом: T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0. Дано n, вернуть значение Tn. Пример:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

👨‍💻 Алгоритм: 1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи. 2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1. 3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c. 😎 Решение:

class Solution {
    func tribonacci(_ n: Int) -> Int {
        if n < 3 {
            return n > 0 ? 1 : 0
        }
        
        var a = 0, b = 1, c = 1
        for _ in 0..<n-2 {
            let tmp = a + b + c
            a = b
            b = c
            c = tmp
        }
        
        return c
    }
}

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

Задача: 491. Non-decreasing Subsequences Сложность: medium Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке. Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

👨‍💻 Алгоритм: 1⃣Инициализация и запуск функции обратного отслеживания Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0. 2⃣Функция обратного отслеживания Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента. 3⃣Возврат результата После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его. 😎 Решение:

class Solution {
    func findSubsequences(_ nums: [Int]) -> [[Int]] {
        var result = Set<[Int]>()
        var sequence = [Int]()
        backtrack(nums, 0, &sequence, &result)
        return Array(result)
    }

    func backtrack(_ nums: [Int], _ index: Int, _ sequence: inout [Int], _ result: inout Set<[Int]>) {
        if index == nums.count {
            if sequence.count >= 2 {
                result.insert(sequence)
            }
            return
        }
        if sequence.isEmpty || sequence.last! <= nums[index] {
            sequence.append(nums[index])
            backtrack(nums, index + 1, &sequence, &result)
            sequence.removeLast()
        }
        backtrack(nums, index + 1, &sequence, &result)
    }
}

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

Задача: 815. Bus Routes Сложность: hard Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно. Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно. Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах. Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно. Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

👨‍💻 Алгоритм: 1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis. 2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными. 3⃣Верните -1 после завершения обхода в ширину (BFS). 😎 Решение:

class Solution {
    func numBusesToDestination(_ routes: [[Int]], _ source: Int, _ target: Int) -> Int {
        if source == target { return 0 }
        
        var adjList = [Int: [Int]]()
        for route in 0..<routes.count {
            for stop in routes[route] {
                adjList[stop, default: []].append(route)
            }
        }
        
        var q = [Int]()
        var vis = Set<Int>()
        for route in adjList[source] ?? [] {
            q.append(route)
            vis.insert(route)
        }
        
        var busCount = 1
        while !q.isEmpty {
            for _ in 0..<q.count {
                let route = q.removeFirst()
                for stop in routes[route] {
                    if stop == target { return busCount }
                    for nextRoute in adjList[stop] ?? [] {
                        if !vis.contains(nextRoute) {
                            vis.insert(nextRoute)
                            q.append(nextRoute)
                        }
                    }
                }
            }
            busCount += 1
        }
        return -1
    }
}

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

Задача: 1422. Maximum Score After Splitting a String Сложность: easy Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку). Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке. Пример:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

👨‍💻 Алгоритм: 1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения. 2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц. 3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума. 😎 Решение:

class Solution {
    func maxScore(_ s: String) -> Int {
        let ones = s.filter { $0 == "1" }.count
        var zeros = 0, ans = 0, countOnes = ones

        for i in 0..<s.count - 1 {
            let char = s[s.index(s.startIndex, offsetBy: i)]
            if char == "1" {
                countOnes -= 1
            } else {
                zeros += 1
            }
            ans = max(ans, zeros + countOnes)
        }
        return ans
    }
}

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

Задача: 412. Fizz Buzz Сложность: easy Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно. Пример:

Input: n = 3
Output: ["1","2","Fizz"]

👨‍💻 Алгоритм: 1⃣Создайте пустой список для хранения результата. 2⃣Пройдите по всем числам от 1 до n и для каждого числа выполните проверку: Если число делится на 3 и на 5, добавьте "FizzBuzz". Если число делится на 3, добавьте "Fizz". Если число делится на 5, добавьте "Buzz". Если ни одно из условий не выполнено, добавьте само число как строку. 3⃣Верните полученный список. 😎 Решение:

func fizzBuzz(_ n: Int) -> [String] {
    var answer = [String]()
    for i in 1...n {
        if i % 3 == 0 && i % 5 == 0 {
            answer.append("FizzBuzz")
        } else if i % 3 == 0 {
            answer.append("Fizz")
        } else if i % 5 == 0 {
            answer.append("Buzz")
        } else {
            answer.append(String(i))
        }
    }
    return answer
}

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

Задача: 1243. Array Transformation Сложность: easy Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив. Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

👨‍💻 Алгоритм: 1⃣Инициализация нового массива с такими же значениями, как у исходного массива. Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться. 2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей. Если элемент меньше своего левого и правого соседей, увеличиваем его. Если элемент больше своего левого и правого соседей, уменьшаем его. 3⃣Первый и последний элементы массива остаются неизменными. 😎 Решение:

class Solution {
    func transformArray(_ arr: [Int]) -> [Int] {
        var arr = arr
        var changed = false
        repeat {
            changed = false
            var newArr = arr
            for i in 1..<arr.count - 1 {
                if arr[i] < arr[i - 1] && arr[i] < arr[i + 1] {
                    newArr[i] += 1
                    changed = true
                } else if arr[i] > arr[i - 1] && arr[i] > arr[i + 1] {
                    newArr[i] -= 1
                    changed = true
                }
            }
            arr = newArr
        } while changed
        return arr
    }
}

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

Задача: 1278. Palindrome Partitioning III Сложность: hard Вам дана строка s, содержащая строчные буквы, и целое число k. Вам нужно: Сначала заменить некоторые символы s на другие строчные английские буквы. Затем разделить s на k непустых непересекающихся подстрок так, чтобы каждая подстрока была палиндромом. Верните минимальное количество символов, которое нужно изменить, чтобы разделить строку. Пример:

Input: s = "abc", k = 2
Output: 1

👨‍💻 Алгоритм: 1⃣Используйте динамическое программирование для вычисления количества изменений, необходимых для превращения любой подстроки в палиндром. 2⃣Используйте еще одно динамическое программирование для разбиения строки на k палиндромических подстрок с минимальным количеством изменений. 3⃣Верните минимальное количество изменений, найденное во втором шаге. 😎 Решение:

class Solution {
    func minChangesToMakePalindrome(_ s: String, _ k: Int) -> Int {
        let n = s.count
        let sArray = Array(s)
        
        func minChangeToPalindrome(_ i: Int, _ j: Int) -> Int {
            var changes = 0
            var i = i
            var j = j
            while i < j {
                if sArray[i] != sArray[j] {
                    changes += 1
                }
                i += 1
                j -= 1
            }
            return changes
        }
        
        var dp1 = Array(repeating: Array(repeating: 0, count: n), count: n)
        for length in 1...n {
            for i in 0...(n - length) {
                let j = i + length - 1
                dp1[i][j] = minChangeToPalindrome(i, j)
            }
        }

        var dp2 = Array(repeating: Array(repeating: Int.max, count: k + 1), count: n + 1)
        dp2[0][0] = 0

        for i in 1...n {
            for kk in 1...k {
                for j in 0..<i {
                    dp2[i][kk] = min(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1])
                }
            }
        }

        return dp2[n][k]
    }
}

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

Задача: 1663. Smallest String With A Given Numeric Value Сложность: medium Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее. Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8. Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k. Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке. Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

👨‍💻 Алгоритм: 1⃣Построить строку или массив символов result для хранения выбранных символов для каждой позиции. 2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции: Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1. Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции. Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции. 3⃣Повторять процесс, пока все позиции не будут заполнены. 😎 Решение:

class Solution {
    func getSmallestString(_ n: Int, _ k: Int) -> String {
        var result = Array(repeating: "a", count: n)
        var k = k
        
        for position in 0..<n {
            let positionsLeft = (n - position - 1)
            if k > positionsLeft * 26 {
                let add = k - (positionsLeft * 26)
                result[position] = String(UnicodeScalar(97 + add - 1)!)
                k -= add
            } else {
                k -= 1
            }
        }
        
        return result.joined()
    }
}

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

Задача: 27. Remove Element Сложность: easy Учитывая целочисленный массив nums и целочисленное значение val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов, которые не равны val. Пример:

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

👨‍💻Алгоритм: 1⃣Используем указатель k для отслеживания позиции, куда вставлять элементы, не равные val. 2⃣Проходим по массиву и при нахождении элемента, отличного от val, записываем его на позицию k, затем увеличиваем k. 3⃣В конце k будет содержать количество элементов, которые не равны val. 😎Решение:

func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
    var k = 0
    
    for i in 0..<nums.count {
        if nums[i] != val {
            nums[k] = nums[i]
            k += 1
        }
    }
    
    return k
}

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

Задача: 716. Max Stack Сложность: hard Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова. Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

👨‍💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение:

class MaxStack {

    private var stack: [Int]
    private var maxStack: [Int]

    init() {
        stack = []
        maxStack = []
    }

    func push(_ x: Int) {
        stack.append(x)
        if maxStack.isEmpty || x >= maxStack.last! {
            maxStack.append(x)
        }
    }

    func pop() -> Int {
        let x = stack.removeLast()
        if x == maxStack.last! {
            maxStack.removeLast()
        }
        return x
    }

    func top() -> Int {
        return stack.last!
    }

    func peekMax() -> Int {
        return maxStack.last!
    }

    func popMax() -> Int {
        let maxVal = maxStack.removeLast()
        var buffer: [Int] = []
        while stack.last! != maxVal {
            buffer.append(stack.removeLast())
        }
        stack.removeLast()
        while !buffer.isEmpty {
            push(buffer.removeLast())
        }
        return maxVal
    }
}

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

Задача: 1319. Number of Operations to Make Network Connected Сложность: medium Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть. Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными. Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1. Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

👨‍💻 Алгоритм: 1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1. 2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0. 3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS: Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i. Отметьте узел как посещенный. Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла. Верните numberOfConnectedComponents - 1. 😎 Решение

class Solution {
    func dfs(_ node: Int, _ adj: [Int: [Int]], _ visit: inout [Bool]) {
        visit[node] = true
        guard let neighbors = adj[node] else { return }
        for neighbor in neighbors {
            if !visit[neighbor] {
                visit[neighbor] = true
                dfs(neighbor, adj, &visit)
            }
        }
    }

    func makeConnected(_ n: Int, _ connections: [[Int]]) -> Int {
        if connections.count < n - 1 {
            return -1
        }

        var adj = [Int: [Int]]()
        for connection in connections {
            adj[connection[0], default: []].append(connection[1])
            adj[connection[1], default: []].append(connection[0])
        }

        var numberOfConnectedComponents = 0
        var visit = [Bool](repeating: false, count: n)
        for i in 0..<n {
            if !visit[i] {
                numberOfConnectedComponents += 1
                dfs(i, adj, &visit)
            }
        }

        return numberOfConnectedComponents - 1
    }
}

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

Задача: 1427. Perform String Shifts Сложность: easy Вам дана строка s, содержащая строчные английские буквы, и матрица shift, где shift[i] = [directioni, amounti]: directioni может быть 0 (для сдвига влево) или 1 (для сдвига вправо). amounti - это количество, на которое строка s должна быть сдвинута. Сдвиг влево на 1 означает удаление первого символа строки s и добавление его в конец. Аналогично, сдвиг вправо на 1 означает удаление последнего символа строки s и добавление его в начало. Верните итоговую строку после всех операций. Пример:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

👨‍💻 Алгоритм: 1⃣Пройдите по списку сдвигов, суммируя все сдвиги вправо и влево в два отдельных значения. 2⃣Определите, какое из значений больше, и частично компенсируйте его другим. Затем выполните соответствующий сдвиг с оставшимся значением. Если оба значения равны, строка останется неизменной. 3⃣Выполните сдвиг строки на основе вычисленного значения и верните итоговую строку. 😎 Решение:

class Solution {
    func stringShift(_ s: String, _ shift: [[Int]]) -> String {
        var leftShifts = 0
        var rightShifts = 0
        for move in shift {
            if move[0] == 0 {
                leftShifts += move[1]
            } else {
                rightShifts += move[1]
            }
        }
        
        let netShifts = (rightShifts - leftShifts) % s.count
        let netShift = netShifts < 0 ? s.count + netShifts : netShifts
        
        if netShift == 0 {
            return s
        }
        
        let splitIndex = s.index(s.startIndex, offsetBy: s.count - netShift)
        return String(s[splitIndex...]) + String(s[..<splitIndex])
    }
}

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

Задача: 720. Longest Word in Dictionary Сложность: medium Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова. Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

👨‍💻 Алгоритм: 1⃣Отсортируйте массив слов по длине и лексикографическому порядку. 2⃣Используйте множество для отслеживания слов, которые можно построить. 3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве. 😎 Решение:

func longestWord(_ words: [String]) -> String {
    let sortedWords = words.sorted()
    var validWords: Set<String> = [""]
    var longest = ""
    for word in sortedWords {
        if validWords.contains(String(word.dropLast())) {
            validWords.insert(word)
            if word.count > longest.count {
                longest = word
            }
        }
    }
    return longest
}

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

Задача: 784. Letter Case Permutation Сложность: medium Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве. Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

👨‍💻 Алгоритм: 1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине. 2⃣Если c является цифрой, мы добавим его к каждому слову. 3⃣Продолжайте процесс для всех символов в строке, чтобы получить все возможные комбинации. 😎 Решение:

class Solution {
    func letterCasePermutation(_ S: String) -> [String] {
        var ans: [[Character]] = [[]]
        
        for char in S {
            let n = ans.count
            if char.isLetter {
                for i in 0..<n {
                    ans.append(ans[i])
                    ans[i].append(char.lowercased().first!)
                    ans[n+i].append(char.uppercased().first!)
                }
            } else {
                for i in 0..<n {
                    ans[i].append(char)
                }
            }
        }
        
        return ans.map { String($0) }
    }
}

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

Задача: 130. Surrounded Regions Сложность: Medium Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены: Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали. Регион: Для формирования региона соедините каждую ячейку 'O'. Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски. Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице. Пример:

Input: board = [["X"]]

Output: [["X"]]

👨‍💻 Алгоритм: 1⃣Выбор начальных ячеек и инициация DFS: Начинаем с выбора всех ячеек, расположенных на границах доски. Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS). 2⃣Логика и выполнение DFS: Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'. Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'. 3⃣Классификация и финальная обработка ячеек: После обхода всех граничных ячеек мы получаем три типа ячеек: Ячейки с буквой 'X': эти ячейки можно считать стеной. Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'. Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'. 😎 Решение:

class Solution {
    private var rows: Int = 0
    private var cols: Int = 0

    func solve(_ board: inout [[Character]]) {
        rows = board.count
        guard rows > 0 else { return }
        cols = board[0].count
        guard cols > 0 else { return }

        for i in 0..<rows {
            for j in 0..<cols {
                if i == 0 || j == 0 || i == rows - 1 || j == cols - 1 {
                    dfs(&board, i, j)
                }
            }
        }

        for i in 0..<rows {
            for j in 0..<cols {
                if board[i][j] == "O" {
                    board[i][j] = "X"
                } else if board[i][j] == "E" {
                    board[i][j] = "O"
                }
            }
        }
    }

    private func dfs(_ board: inout [[Character]], _ i: Int, _ j: Int) {
        if board[i][j] != "O" { return }
        board[i][j] = "E"
        if j < cols - 1 { dfs(&board, i, j + 1) }
        if i < rows - 1 { dfs(&board, i + 1, j) }
        if j > 0 { dfs(&board, i, j - 1) }
        if i > 0 { dfs(&board, i - 1, j) }
    }
}

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