Swift | LeetCode

Задача: 1268. Search Suggestions System
Сложность: medium

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

Пример:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

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

1⃣Отсортируйте массив продуктов.

2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу.

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

😎 Решение:

class Solution {
    func suggestedProducts(_ products: [String], _ searchWord: String) -> [[String]] {
        let sortedProducts = products.sorted()
        var result = [[String]]()
        var prefix = ""
        for char in searchWord {
            prefix.append(char)
            var suggestions = [String]()
            for product in sortedProducts {
                if product.hasPrefix(prefix) {
                    suggestions.append(product)
                    if suggestions.count == 3 { break }
                }
            }
            result.append(suggestions)
        }
        return result
    }
}

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

Задача: 664. Strange Printer
Сложность: hard

Существует странный принтер с двумя особыми свойствами:

Принтер может печатать последовательность одного и того же символа за раз.
На каждом шагу принтер может печатать новые символы, начиная и заканчивая в любом месте, при этом покрывая уже существующие символы.
Дана строка s. Верните минимальное количество ходов, необходимых для её печати.

Пример:

Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

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

1⃣Инициализация и подсчет:
Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1].

2⃣Динамическое программирование:
Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим.
В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов.


3⃣Возврат результата:
Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки.

😎 Решение:

class Solution {
    func strangePrinter(_ s: String) -> Int {
        let n = s.count
        var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
        let chars = Array(s)
        
        for length in 1...n {
            for i in 0...(n - length) {
                let j = i + length - 1
                dp[i][j] = (i == j) ? 1 : dp[i][j - 1] + 1
                for k in i..<j {
                    if chars[k] == chars[j] {
                        dp[i][j] = min(dp[i][j], dp[i][k] + (dp[k + 1][j - 1] if k + 1 <= j - 1 else 0))
                    }
                }
            }
        }
        return dp[0][n - 1]
    }
}

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

Задача: 1036. Escape a Large Maze
Сложность: hard

Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.

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

3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    func isEscapePossible(_ blocked: [[Int]], _ source: [Int], _ target: [Int]) -> Bool {
        let blockedSet = Set(blocked.map { ($0[0], $0[1]) })
        let source = (source[0], source[1])
        let target = (target[0], target[1])
        
        if blockedSet.contains(source) || blockedSet.contains(target) {
            return false
        }
        
        func bfs(_ start: (Int, Int), _ end: (Int, Int)) -> Bool {
            var queue = [(start.0, start.1)]
            var visited = Set([(start.0, start.1)])
            let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            let maxArea = blocked.count * (blocked.count - 1) / 2
            
            while !queue.isEmpty {
                if visited.count > maxArea {
                    return true
                }
                let (x, y) = queue.removeFirst()
                for (dx, dy) in directions {
                    let nx = x + dx, ny = y + dy
                    if nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.contains((nx, ny)) && !blockedSet.contains((nx, ny)) {
                        if (nx, ny) == end {
                            return true
                        }
                        queue.append((nx, ny))
                        visited.insert((nx, ny))
                    }
                }
            }
            return false
        }
        
        return bfs(source, target) && bfs(target, source)
    }
}

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

Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy

Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.

Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

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

1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.

2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.

3⃣Верните список answer.

😎 Решение:

class Solution {
    func kidsWithCandies(_ candies: [Int], _ extraCandies: Int) -> [Bool] {
        var maxCandies = 0
        for candy in candies {
            maxCandies = max(candy, maxCandies)
        }
        var result = [Bool]()
        for candy in candies {
            result.append(candy + extraCandies >= maxCandies)
        }
        return result
    }
}

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

Задача: 346. Moving Average from Data Stream
Сложность: easy

Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне.

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

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

1⃣Инициализация:
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.

2⃣Добавление нового значения:
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.

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

😎 Решение:

class MovingAverage {
    private var size: Int
    private var queue: [Int]
    private var sum: Int
    
    init(_ size: Int) {
        self.size = size
        self.queue = []
        self.sum = 0
    }
    
    func next(_ val: Int) -> Double {
        queue.append(val)
        sum += val
        if queue.count > size {
            sum -= queue.removeFirst()
        }
        return Double(sum) / Double(queue.count)
    }
}

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

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

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

Задача: 387. First Unique Character in a String
Сложность: easy

Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1.

Пример:

Input: s = "leetcode"
Output: 0

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

1⃣Постройте хеш-таблицу, где ключами являются символы строки, а значениями — количество их появлений. Для этого пройдите по строке и для каждого символа увеличивайте его счетчик в хеш-таблице.

2⃣Пройдите по строке снова и проверьте для каждого символа, является ли его количество появлений в хеш-таблице равным 1.

3⃣Если найдется символ с количеством появлений, равным 1, верните его индекс. Если такой символ не найден, верните -1.

😎 Решение:

class Solution {
    private var original: [Int]
    private var array: [Int]

    init(_ nums: [Int]) {
        self.original = nums
        self.array = nums
    }

    func reset() -> [Int] {
        self.array = self.original
        return self.original
    }

    func shuffle() -> [Int] {
        let n = array.count
        for i in 0..<n {
            let randIndex = Int.random(in: i..<n)
            array.swapAt(i, randIndex)
        }
        return array
    }
}

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

Задача: 459. Repeated Substring Pattern
Сложность: easy

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

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

1⃣Создайте целочисленную переменную n, равную длине строки s.

2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2:
Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s.
Если pattern равен s, вернуть true.

3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false.

😎 Решение:

class Solution {
    func repeatedSubstringPattern(_ s: String) -> Bool {
        let n = s.count
        for i in 1...n / 2 {
            if n % i == 0 {
                var pattern = ""
                let substr = String(s.prefix(i))
                for _ in 0..<n / i {
                    pattern += substr
                }
                if s == pattern {
                    return true
                }
            }
        }
        return false
    }
}

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

Задача: 996. Number of Squareful Arrays
Сложность: hard

Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].

Пример:

Input: nums = [1,17,8]
Output: 2

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

1⃣Генерация перестановок:
Сгенерируйте все возможные перестановки массива nums.
Для каждой перестановки проверьте, является ли она квадратной.

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

3⃣Подсчет квадратных перестановок:
Подсчитайте количество перестановок, которые являются квадратными, и верните это значение.

😎 Решение:

class Solution {
    func numSquarefulPerms(_ nums: [Int]) -> Int {
        var nums = nums.sorted()
        var used = Array(repeating: false, count: nums.count)
        var result = Set<[Int]>()
        var path = [Int]()
        backtrack(nums, &used, &path, &result)
        return result.count
    }
    
    private func backtrack(_ nums: [Int], _ used: inout [Bool], _ path: inout [Int], _ result: inout Set<[Int]>) {
        if path.count == nums.count {
            if isSquareful(path) {
                result.insert(path)
            }
            return
        }
        
        for i in 0..<nums.count {
            if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue }
            path.append(nums[i])
            used[i] = true
            backtrack(nums, &used, &path, &result)
            path.removeLast()
            used[i] = false
        }
    }
    
    private func isSquareful(_ perm: [Int]) -> Bool {
        for i in 0..<perm.count - 1 {
            let sum = perm[i] + perm[i + 1]
            let root = Int(sqrt(Double(sum)))
            if root * root != sum { return false }
        }
        return true
    }
}

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

Задача: 954. Array of Doubled Pairs
Сложность: medium

Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.

Пример:

Input: arr = [3,1,3,6]
Output: false

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

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

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

3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.

😎 Решение:

class Solution {
    func canReorderDoubled(_ arr: [Int]) -> Bool {
        var count = [Int: Int]()
        for num in arr {
            count[num, default: 0] += 1
        }
        for num in arr.sorted(by: { abs($0) < abs($1) }) {
            if count[num]! == 0 {
                continue
            }
            if count[2 * num, default: 0] == 0 {
                return false
            }
            count[num]! -= 1
            count[2 * num]! -= 1
        }
        return true
    }
}

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

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

😎 Решение:

import Foundation

func minCostPath(_ coins: [Int], _ maxJump: Int) -> [Int] {
    let n = coins.count
    if coins[0] == -1 { return [] }
    
    var dp = [Int](repeating: Int.max, count: n)
    dp[0] = coins[0]
    var path = Array(repeating: [Int](), count: n)
    path[0] = [1]
    
    var heap = [(cost: Int, index: Int)]()
    heap.append((coins[0], 0))
    
    while !heap.isEmpty {
        heap.sort(by: { $0.cost < $1.cost })
        let (current_cost, i) = heap.removeFirst()
        if current_cost > dp[i] { continue }
        for k in 1...maxJump {
            if i + k < n && coins[i + k] != -1 {
                let new_cost = current_cost + coins[i + k]
                if new_cost < dp[i + k] || (new_cost == dp[i + k] && path[i] + [i + k + 1] < path[i + k]) {
                    dp[i + k] = new_cost
                    path[i + k] = path[i] + [i + k + 1]
                    heap.append((new_cost, i + k))
                }
            }
        }
    }
    
    return dp[n - 1] == Int.max ? [] : path[n - 1]
}

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

Задача: 757. Set Intersection Size At Least Two
Сложность: hard

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

1⃣Отсортируйте интервалы по их конечным точкам.

2⃣Инициализируйте пустое множество для хранения чисел.

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

😎 Решение:

func minSetSize(_ intervals: [[Int]]) -> Int {
    let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
    var nums = [Int]()
    for interval in sortedIntervals {
        let start = interval[0]
        let end = interval[1]
        if nums.isEmpty || nums.last! < start {
            nums.append(end - 1)
            nums.append(end)
        } else if nums.last! == end - 1 {
            nums.append(end)
        }
    }
    return nums.count
}

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

Задача: 985. Sum of Even Numbers After Queries
Сложность: medium

Дан целочисленный массив nums и массив queries, где queries[i] = [vali, indexi].

Для каждого запроса i, сначала примените nums[indexi] = nums[indexi] + vali, затем выведите сумму четных значений nums.

Верните целочисленный массив answer, где answer[i] - это ответ на i-й запрос.

Пример:

Input: nums = [1], queries = [[4,0]]
Output: [0]

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

1⃣Инициализация переменных:
Завести переменную evenSum для хранения суммы всех четных чисел в массиве nums.
Пройти по массиву nums и вычислить начальное значение evenSum, сложив все четные числа в nums.

2⃣Обработка запросов:
Создать пустой массив result для хранения ответов на каждый запрос.
Для каждого запроса [val, index] из массива queries выполнить следующие действия:
Если значение nums[index] четное, вычесть его из evenSum.
Обновить nums[index] добавлением val.
Если новое значение nums[index] четное, добавить его к evenSum.
Добавить текущее значение evenSum в массив result.

3⃣Возврат результата:
Вернуть массив result, содержащий ответы на все запросы.

😎 Решение:

func sumEvenAfterQueries(_ nums: [Int], _ queries: [[Int]]) -> [Int] {
    var nums = nums
    var evenSum = nums.filter { $0 % 2 == 0 }.reduce(0, +)
    var result = [Int]()
    
    for query in queries {
        let val = query[0], index = query[1]
        if nums[index] % 2 == 0 {
            evenSum -= nums[index]
        }
        nums[index] += val
        if nums[index] % 2 == 0 {
            evenSum += nums[index]
        }
        result.append(evenSum)
    }
    
    return result
}

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

Задача: 643. Maximum Average Subarray I
Сложность: easy

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

Пример:

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

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

1⃣Инициализация скользящего окна: Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы.

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

3⃣Обновление максимальной суммы: На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.

😎 Решение:

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

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

Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard

Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.

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

Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.

Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

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

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

class Solution {
    func minmaxGasDist(_ stations: [Int], _ K: Int) -> Double {
        let N = stations.count
        var deltas = [Double](repeating: 0, count: N-1)
        for i in 0..<N-1 {
            deltas[i] = Double(stations[i+1] - stations[i])
        }

        var dp = [[Double]](repeating: [Double](repeating: 0, count: K+1), count: N-1)
        for i in 0...K {
            dp[0][i] = deltas[0] / Double(i+1)
        }

        for p in 1..<N-1 {
            for k in 0...K {
                var bns = Double.greatestFiniteMagnitude
                for x in 0...k {
                    bns = min(bns, max(deltas[p] / Double(x+1), dp[p-1][k-x]))
                }
                dp[p][k] = bns
            }
        }

        return dp[N-2][K]
    }
}

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

Задача: 230. Kth Smallest Element in a BST
Сложность: medium

Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.

Пример:

Input: root = [3,1,4,null,2], k = 1
Output: 1

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

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

2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение.

3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение.

😎 Решение:

class Solution {
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var stack = [TreeNode]()
        var root = root
        var k = k
        
        while true {
            while root != nil {
                stack.append(root!)
                root = root?.left
            }
            root = stack.removeLast()
            k -= 1
            if k == 0 {
                return root!.val
            }
            root = root?.right
        }
    }
}

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

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

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

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

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
    var count = 0

    func dfs(_ node: Int, _ parent: Int, _ adj: [Int: [[Int]]]) {
        guard let neighbors = adj[node] else { return }
        for neighbor in neighbors {
            let (nei, sign) = (neighbor[0], neighbor[1])
            if nei != parent {
                count += sign
                dfs(nei, node, adj)
            }
        }
    }

    func minReorder(_ n: Int, _ connections: [[Int]]) -> Int {
        var adj = [Int: [[Int]]]()
        for connection in connections {
            adj[connection[0], default: []].append([connection[1], 1])
            adj[connection[1], default: []].append([connection[0], 0])
        }
        dfs(0, -1, adj)
        return count
    }
}

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

Задача: 415. Add Strings
Сложность: easy

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

Пример:

Input: num1 = "11", num2 = "123"
Output: "134"

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

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

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

3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число.

😎 Решение:

func thirdMax(_ nums: [Int]) -> Int {
    var first: Int? = nil
    var second: Int? = nil
    var third: Int? = nil
    
    for num in nums {
        if num == first || num == second || num == third {
            continue
        }
        if first == nil || num > first! {
            third = second
            second = first
            first = num
        } else if second == nil || num > second! {
            third = second
            second = num
        } else if third == nil || num > third! {
            third = num
        }
    }
    
    return third ?? first!
}

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

Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

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

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    func isBoomerang(_ points: [[Int]]) -> Bool {
        let (x1, y1) = (points[0][0], points[0][1])
        let (x2, y2) = (points[1][0], points[1][1])
        let (x3, y3) = (points[2][0], points[2][1])
        return (x1 != x2 || y1 != y2) && (x1 != x3 || y1 != y3) && (x2 != x3 || y2 != y3) && (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0
    }
}

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

Задача: 640. Solve the Equation
Сложность: medium

Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.

Пример:

Input: s = "*"
Output: 9

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

1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='.

2⃣Парсинг и упрощение: Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений.

3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'.

😎 Решение:

class Solution {
    func solveEquation(_ equation: String) -> String {
        func parse(_ s: String) -> (Int, Int) {
            var coeff = 0
            var constPart = 0
            var sign = 1
            var num = 0
            var i = s.startIndex
            
            while i < s.endIndex {
                if s[i] == "+" {
                    sign = 1
                    i = s.index(after: i)
                } else if s[i] == "-" {
                    sign = -1
                    i = s.index(after: i)
                } else if s[i].isNumber {
                    num = 0
                    while i < s.endIndex && s[i].isNumber {
                        num = num * 10 + s[i].wholeNumberValue!
                        i = s.index(after: i)
                    }
                    if i < s.endIndex && s[i] == "x" {
                        coeff += sign * num
                        i = s.index(after: i)
                    } else {
                        constPart += sign * num
                    }
                } else if s[i] == "x" {
                    coeff += sign
                    i = s.index(after: i)
                }
            }
            return (coeff, constPart)
        }
        
        let parts = equation.split(separator: "=")
        let (leftCoeff, leftConst) = parse(String(parts[0]))
        let (rightCoeff, rightConst) = parse(String(parts[1]))
        
        let coeff = leftCoeff - rightCoeff
        let constPart = rightConst - leftConst
        
        if coeff == 0 {
            return constPart == 0 ? "Infinite solutions" : "No solution"
        }
        return "x=\(constPart / coeff)"
    }
}

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