Swift | LeetCode

Задача: 940. Distinct Subsequences II
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.

Пример:

Input: s = "abc"
Output: 7

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

1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.

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

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

😎 Решение:

class Solution {
    func countSubsequences(_ s: String) -> Int {
        let MOD = 1000000007
        var dp = [Int](repeating: 0, count: 26)
        for c in s {
            let index = Int(c.asciiValue! - Character("a").asciiValue!)
            dp[index] = (dp.reduce(0, +) + 1) % MOD
        }
        return dp.reduce(0, +) % MOD
    }
}

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

Задача: 73. Set Matrix Zeroes
Сложность: medium

Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца.

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

Пример:

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

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

1⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0.

2⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки.

3⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми.

😎 Решение:

func setZeroes(_ matrix: inout [[Int]]) {
    var isCol = false
    let R = matrix.count
    let C = matrix[0].count
    
    for i in 0..<R {
        if matrix[i][0] == 0 {
            isCol = true
        }
        for j in 1..<C {
            if matrix[i][j] == 0 {
                matrix[0][j] = 0
                matrix[i][0] = 0
            }
        }
    }
    
    for i in 1..<R {
        for j in 1..<C {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    
    if matrix[0][0] == 0 {
        for j in 0..<C {
            matrix[0][j] = 0
        }
    }
    
    if isCol {
        for i in 0..<R {
            matrix[i][0] = 0
        }
    }
}

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

Задача: 294. Flip Game II
Сложность: medium

Вы играете в игру Flip со своим другом.

Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем.

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

Пример:

Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

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

1⃣Генерация всех возможных следующих ходов:
Для текущего состояния currentState, создайте все возможные новые состояния, заменяя каждую пару "++" на "--".

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

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

😎 Решение:

class Solution {
    func canWin(_ currentState: String) -> Bool {
        var stateArray = Array(currentState)
        
        for i in 0..<(stateArray.count - 1) {
            if stateArray[i] == "+" && stateArray[i + 1] == "+" {
                stateArray[i] = "-"
                stateArray[i + 1] = "-"
                let newState = String(stateArray)
                
                if !canWin(newState) {
                    stateArray[i] = "+"
                    stateArray[i + 1] = "+"
                    return true
                }
                
                stateArray[i] = "+"
                stateArray[i + 1] = "+"
            }
        }
        
        return false
    }
}

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

Задача: 1357. Apply Discount Every n Orders
Сложность: medium

В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i].

Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара).

Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100).

Реализуйте класс Cashier:

Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен.
double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты.

Пример:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]

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

1⃣Инициализация объекта:
Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами.

2⃣Обработка каждого счета:
Создайте метод getBill, который принимает массивы product и amount.
Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты.
Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу.

3⃣Верните итоговую сумму счета.

😎 Решение:

class Cashier {
    private let n: Int
    private let discount: Int
    private var productsPrices: [Int: Int]
    private var customerCount: Int

    init(_ n: Int, _ discount: Int, _ products: [Int], _ prices: [Int]) {
        self.n = n
        self.discount = discount
        self.customerCount = 0
        self.productsPrices = Dictionary(uniqueKeysWithValues: zip(products, prices))
    }

    func getBill(_ product: [Int], _ amount: [Int]) -> Double {
        customerCount += 1
        var bill = 0.0

        for (index, prod) in product.enumerated() {
            bill += Double(productsPrices[prod]! * amount[index])
        }

        if customerCount % n == 0 {
            bill *= Double(100 - discount) / 100.0
        }

        return bill
    }
}

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

Задача: 128. Longest Consecutive Sequence
Сложность: Medium

Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.

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

Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

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

2⃣Обработка чисел в массиве:
Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).
Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.
Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3⃣Завершение обработки и возврат результата:
В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).
Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎 Решение:

func longestConsecutive(_ nums: [Int]) -> Int {
    var longestStreak = 0
    let numSet = Set(nums)  
    for num in numSet {
        if !numSet.contains(num - 1) {  
            var currentNum = num
            var currentStreak = 1

            while numSet.contains(currentNum + 1) {
                currentNum += 1
                currentStreak += 1
            }

            longestStreak = max(longestStreak, currentStreak)
        }
    }
    return longestStreak
}

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

Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

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

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

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

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

3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.

😎 Решение:

class Solution {
    var seen = Set<Int>()
    let MAX_EDGE_VAL = 1000

    func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
        var graph = Array(repeating: [Int](), count: MAX_EDGE_VAL + 1)

        for edge in edges {
            seen.removeAll()
            if !graph[edge[0]].isEmpty && !graph[edge[1]].isEmpty && dfs(graph, edge[0], edge[1]) {
                return edge
            }
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        }
        return []
    }

    func dfs(_ graph: [[Int]], _ source: Int, _ target: Int) -> Bool {
        if !seen.contains(source) {
            seen.insert(source)
            if source == target { return true }
            for nei in graph[source] {
                if dfs(graph, nei, target) { return true }
            }
        }
        return false
    }
}

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

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

Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.

Дано целое число n, верните true, если n является уродливым числом.

Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

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

1⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.

2⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.

3⃣Если после всех делений n равно 1, верните true, иначе верните false.

😎 Решение:

class Solution {
    func isUgly(_ n: Int) -> Bool {
        if n <= 0 {
            return false
        }
        var n = n
        for factor in [2, 3, 5] {
            n = keepDividingWhenDivisible(n, factor)
        }
        return n == 1
    }

    private func keepDividingWhenDivisible(_ dividend: Int, _ divisor: Int) -> Int {
        var dividend = dividend
        while dividend % divisor == 0 {
            dividend /= divisor
        }
        return dividend
    }
}

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

Задача: 931. Minimum Falling Path Sum
Сложность: medium

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

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

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

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

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

😎 Решение:

class Solution {
    func minFallingPathSum(_ matrix: [[Int]]) -> Int {
        let n = matrix.count
        var dp = matrix[0]
        
        for i in 1..<n {
            var newDp = [Int](repeating: 0, count: n)
            for j in 0..<n {
                newDp[j] = matrix[i][j] + min(dp[j], dp[j-1] ?? Int.max, dp[j+1] ?? Int.max)
            }
            dp = newDp
        }
        
        return dp.min()!
    }
}

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

Задача: 844. Backspace String Compare
Сложность: easy

Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace.

Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым.

Пример:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

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

1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы.

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

3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false.

😎 Решение:

class Solution {
    func backspaceCompare(_ S: String, _ T: String) -> Bool {
        var i = S.count - 1, j = T.count - 1
        var skipS = 0, skipT = 0
        let sArray = Array(S), tArray = Array(T)

        while i >= 0 || j >= 0 {
            while i >= 0 {
                if sArray[i] == "#" {
                    skipS += 1
                    i -= 1
                } else if skipS > 0 {
                    skipS -= 1
                    i -= 1
                } else {
                    break
                }
            }
            while j >= 0 {
                if tArray[j] == "#" {
                    skipT += 1
                    j -= 1
                } else if skipT > 0 {
                    skipT -= 1
                    j -= 1
                } else {
                    break
                }
            }
            if i >= 0 && j >= 0 && sArray[i] != tArray[j] {
                return false
            }
            if (i >= 0) != (j >= 0) {
                return false
            }
            i -= 1
            j -= 1
        }
        return true
    }
}

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

Задача: 438. Find All Anagrams in a String
Сложность: medium

Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.

Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

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

1⃣Построить эталонный счетчик pCount для строки p.

2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

class Solution {
    func findAnagrams(_ s: String, _ p: String) -> [Int] {
        let ns = s.count, np = p.count
        if ns < np { return [] }

        var pCount = [Character: Int]()
        var sCount = [Character: Int]()

        for ch in p {
            pCount[ch, default: 0] += 1
        }

        var output = [Int]()

        let sArray = Array(s)
        for i in 0..<ns {
            let ch = sArray[i]
            sCount[ch, default: 0] += 1

            if i >= np {
                let leftChar = sArray[i - np]
                if sCount[leftChar] == 1 {
                    sCount.removeValue(forKey: leftChar)
                } else {
                    sCount[leftChar]! -= 1
                }
            }

            if pCount == sCount {
                output.append(i - np + 1)
            }
        }
        return output
    }
}

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

Задача: 677. Map Sum Pairs
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

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

3⃣Вернуть полученную сумму как результат.

😎 Решение:

class MapSum {
    private var mapData: [String: Int]

    init() {
        self.mapData = [:]
    }

    func insert(_ key: String, _ val: Int) {
        mapData[key] = val
    }

    func sum(_ prefix: String) -> Int {
        var ans = 0
        for (key, val) in mapData {
            if key.hasPrefix(prefix) {
                ans += val
            }
        }
        return ans
    }
}

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

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

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

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

1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму.

2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу.

3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.

😎 Решение

class Solution {
    private func solve(_ root: TreeNode?, _ parent: Int, _ gParent: Int) -> Int {
        guard let root = root else {
            return 0
        }
        return solve(root.left, root.val, parent) 
            + solve(root.right, root.val, parent) 
            + (gParent % 2 == 0 ? root.val : 0)
    }

    func sumEvenGrandparent(_ root: TreeNode?) -> Int {
        return solve(root, -1, -1)
    }
}

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

Задача: 1066. Campus Bikes II
Сложность: medium

На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.

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

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

Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

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

1⃣Для каждого рабочего, начиная с рабочего с индексом 0, пройдите по всем велосипедам и назначьте велосипед рабочему, если он доступен (visited[bikeIndex] = false). После назначения велосипеда отметьте его как недоступный (visited[bikeIndex] = true). Добавьте Манхэттенское расстояние от этого назначения к общей текущей сумме расстояний, представленной currDistanceSum, и выполните рекурсивный вызов для следующего рабочего.

2⃣Когда рекурсивный вызов завершится, сделайте велосипед снова доступным, установив visited[bikeIndex] в false. Если мы назначили велосипеды всем рабочим, сравните currDistanceSum с smallestDistanceSum и обновите smallestDistanceSum соответственно.

3⃣Перед назначением любого велосипеда рабочему, проверьте, если currDistanceSum уже больше или равен smallestDistanceSum. Если это так, пропустите остальных рабочих и вернитесь. Это связано с тем, что currDistanceSum может только увеличиваться, и таким образом мы не найдем лучший результат, чем smallestDistanceSum, используя текущую комбинацию рабочих и велосипедов.

😎 Решение:

class Solution {
    var smallestDistanceSum = Int.max
    var visited = [Bool](repeating: false, count: 10)
    
    func findDistance(_ worker: [Int], _ bike: [Int]) -> Int {
        return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
    }
    
    func minimumDistanceSum(_ workers: [[Int]], _ workerIndex: Int, 
                            _ bikes: [[Int]], _ currDistanceSum: Int) {
        if workerIndex >= workers.count {
            smallestDistanceSum = min(smallestDistanceSum, currDistanceSum)
            return
        }
        
        if currDistanceSum >= smallestDistanceSum {
            return
        }
        
        for bikeIndex in 0..<bikes.count {
            if !visited[bikeIndex] {
                visited[bikeIndex] = true
                minimumDistanceSum(workers, workerIndex + 1, bikes, 
                    currDistanceSum + findDistance(workers[workerIndex], bikes[bikeIndex]))
                visited[bikeIndex] = false
            }
        }
    }
    
    func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
        minimumDistanceSum(workers, 0, bikes, 0)
        return smallestDistanceSum
    }
}

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

Задача: 354. Russian Doll Envelopes
Сложность: hard

Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.

Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).

Примечание: Вы не можете поворачивать конверт.

Пример:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

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

1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).

2⃣Извлеките вторую размерность (высоты) отсортированного массива.

3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.

😎 Решение:

class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        var dp = [Int](repeating: 0, count: nums.count)
        var len = 0
        for num in nums {
            var i = dp.binarySearch(0..<len, num)
            if i < 0 { i = -(i + 1) }
            dp[i] = num
            if i == len { len += 1 }
        }
        return len
    }

    func maxEnvelopes(_ envelopes: [[Int]]) -> Int {
        let sortedEnvelopes = envelopes.sorted {
            if $0[0] == $1[0] { return $0[1] > $1[1] }
            return $0[0] < $1[0]
        }
        let secondDim = sortedEnvelopes.map { $0[1] }
        return lengthOfLIS(secondDim)
    }
}

extension Array where Element == Int {
    func binarySearch(_ range: Range<Int>, _ target: Int) -> Int {
        var left = range.lowerBound
        var right = range.upperBound
        while left < right {
            let mid = left + (right - left) / 2
            if self[mid] < target {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left < range.upperBound && self[left] == target ? left : -(left + 1)
    }
}

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

Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium

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

Пример:

Input: nums = [3,6,5,1,8]
Output: 18

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

1⃣Найдите сумму всех элементов массива.

2⃣Если сумма делится на 3, то она и есть ответ.

3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2).
Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2).

😎 Решение:

class Solution {
    func maxSumDivThree(_ nums: [Int]) -> Int {
        let totalSum = nums.reduce(0, +)
        if totalSum % 3 == 0 {
            return totalSum
        }
        
        var mod1 = [Int]()
        var mod2 = [Int]()
        
        for num in nums {
            if num % 3 == 1 {
                mod1.append(num)
            } else if num % 3 == 2 {
                mod2.append(num)
            }
        }
        
        mod1.sort()
        mod2.sort()
        
        if totalSum % 3 == 1 {
            let remove1 = mod1.isEmpty ? Int.max : mod1[0]
            let remove2 = mod2.count < 2 ? Int.max : mod2[0] + mod2[1]
            return totalSum - min(remove1, remove2)
        } else {
            let remove2 = mod2.isEmpty ? Int.max : mod2[0]
            let remove1 = mod1.count < 2 ? Int.max : mod1[0] + mod1[1]
            return totalSum - min(remove2, remove1)
        }
    }
}

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

Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy

Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.

Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку.

Пример:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

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

1⃣Построение списка символов для word2:
Создайте список list2 для хранения всех символов из массива строк word2.

2⃣Итерация по word1 и проверка соответствующих символов:
Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2.

3⃣Возврат результата:
Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают.

😎 Решение:

class Solution {
    func arrayStringsAreEqual(_ word1: [String], _ word2: [String]) -> Bool {
        let list2 = word2.joined()
        var index = list2.startIndex

        for word in word1 {
            for char in word {
                if index == list2.endIndex || char != list2[index] {
                    return false
                }
                index = list2.index(after: index)
            }
        }

        return index == list2.endIndex
    }
}

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

Задача: 851. Loud and Rich
Сложность: medium

Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.

Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).

Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.

Пример:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

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

1⃣Постройте граф, описанный выше, и пусть dfs(person) будет самым спокойным человеком в поддереве person. Обратите внимание, что из-за логической последовательности утверждений граф должен быть DAG — ориентированным графом без циклов.

2⃣Теперь dfs(person) — это либо сам person, либо min(dfs(child) для каждого child из person). То есть, самый спокойный человек в поддереве — это либо сам person, либо самый спокойный человек в каком-то поддереве потомка person.

3⃣Мы можем кэшировать значения dfs(person) в answer[person], выполняя обход графа в пост-обходе. Таким образом, мы не повторяем работу. Этот метод уменьшает квадратичное время выполнения алгоритма до линейного.

😎 Решение:

class Solution {
    var graph: [[Int]] = []
    var answer: [Int] = []
    var quiet: [Int] = []

    func loudAndRich(_ richer: [[Int]], _ quiet: [Int]) -> [Int] {
        let N = quiet.count
        graph = Array(repeating: [], count: N)
        answer = Array(repeating: -1, count: N)
        self.quiet = quiet

        for edge in richer {
            graph[edge[1]].append(edge[0])
        }

        for node in 0..<N {
            _ = dfs(node)
        }
        return answer
    }

    func dfs(_ node: Int) -> Int {
        if answer[node] == -1 {
            answer[node] = node
            for child in graph[node] {
                let cand = dfs(child)
                if quiet[cand] < quiet[answer[node]] {
                    answer[node] = cand
                }
            }
        }
        return answer[node]
    }
}

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

Задача: 287. Find the Duplicate Number
Сложность: medium

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

Пример:

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

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

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

2⃣Восстановление массива:
Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива.

3⃣Возврат результата:
Верните найденный дубликат.

😎 Решение:

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        var nums = nums
        var duplicate = -1
        for i in 0..<nums.count {
            let cur = abs(nums[i])
            if nums[cur] < 0 {
                duplicate = cur
                break
            }
            nums[cur] *= -1
        }
        for i in 0..<nums.count {
            nums[i] = abs(nums[i])
        }
        return duplicate
    }
}

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

Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

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

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

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

1⃣Инициализация:
Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.
Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

2⃣Рекурсивный обход:
Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):
- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

3⃣Оценка узла:
Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:
- если у узла есть левый или правый дочерний узел, добавьте их в forest.
- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.
Если узел не нужно удалять, верните сам узел.

😎 Решение:

class Solution {
    func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
        var toDeleteSet = Set(to_delete)
        var forest = [TreeNode?]()

        func processNode(_ node: TreeNode?) -> TreeNode? {
            guard let node = node else { return nil }

            node.left = processNode(node.left)
            node.right = processNode(node.right)

            if toDeleteSet.contains(node.val) {
                if let left = node.left { forest.append(left) }
                if let right = node.right { forest.append(right) }
                return nil
            }
            return node
        }

        let root = processNode(root)
        if let root = root { forest.append(root) }

        return forest
    }
}

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