Задача: 515. Largest Value in Each Tree Row
Сложность: medium

Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

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

1⃣Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS).

2⃣Выполните BFS, пока очередь не пуста: инициализируйте currMax минимальным значением и сохраните длину очереди в currentLength. Повторите currentLength раз: удалите узел из очереди, обновите currMax, если значение узла больше. Для каждого дочернего узла, если он не равен null, добавьте его в очередь.

3⃣Добавьте currMax в ans. Верните ans.

😎 Решение:

class Solution {
    func largestValues(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        
        var ans = [Int]()
        var queue = [root]
        
        while !queue.isEmpty {
            var currentLength = queue.count
            var currMax = Int.min
            
            for _ in 0..<currentLength {
                let node = queue.removeFirst()
                currMax = max(currMax, node.val)
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
            
            ans.append(currMax)
        }
        
        return ans
    }
}

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

Задача: 743. Network Delay Time
Сложность: medium

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

1⃣Представьте граф в виде списка смежности.

2⃣Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов.

3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.

😎 Решение:

import Foundation

func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
    var graph = [Int: [(Int, Int)]]()
    for i in 1...n {
        graph[i] = []
    }
    for time in times {
        graph[time[0]]?.append((time[1], time[2]))
    }

    var minHeap = [(0, k)]
    var minTime = [Int: Int]()
    for i in 1...n {
        minTime[i] = Int.max
    }
    minTime[k] = 0

    while !minHeap.isEmpty {
        minHeap.sort { $0.0 < $1.0 }
        let (time, node) = minHeap.removeFirst()
        if let neighbors = graph[node] {
            for (neighbor, t) in neighbors {
                let newTime = time + t
                if newTime < minTime[neighbor]! {
                    minTime[neighbor] = newTime
                    minHeap.append((newTime, neighbor))
                }
            }
        }
    }

    let maxTime = minTime.values.max()!
    return maxTime == Int.max ? -1 : maxTime
}

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

Задача: 561. Array Partition
Сложность: easy

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

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

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    func arrayPairSum(_ nums: [Int]) -> Int {
        let sortedNums = nums.sorted()
        var sum = 0
        for i in stride(from: 0, to: sortedNums.count, by: 2) {
            sum += sortedNums[i]
        }
        return sum
    }
}

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

Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium

Вам дан массив целых чисел nums и целое число target.

Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

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

1⃣Инициализация и подготовка:
Инициализируйте переменные answer равным 0 и n как длину массива nums.
Отсортируйте массив nums.
Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7.

2⃣Итерация и бинарный поиск:
Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left].
Если left <= right, добавьте количество допустимых подпоследовательностей к answer.

3⃣Возврат результата:
Верните answer по модулю 10^9+7.

😎 Решение:

class Solution {
    func numSubseq(_ nums: [Int], _ target: Int) -> Int {
        let mod = 1_000_000_007
        let n = nums.count
        var nums = nums.sorted()
        
        var power = [Int](repeating: 1, count: n)
        for i in 1..<n {
            power[i] = (power[i - 1] * 2) % mod
        }
        
        var answer = 0
        var left = 0
        var right = n - 1
        
        while left <= right {
            if nums[left] + nums[right] <= target {
                answer = (answer + power[right - left]) % mod
                left += 1
            } else {
                right -= 1
            }
        }
        
        return answer
    }
}

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

Задача: 901. Online Stock Span
Сложность: medium

Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.

Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.

Пример:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

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

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

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

3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.

😎 Решение:

class StockSpanner {
    private var stack: [(Int, Int)] = []

    func next(_ price: Int) -> Int {
        var span = 1
        while let last = stack.last, last.0 <= price {
            span += last.1
            stack.removeLast()
        }
        stack.append((price, span))
        return span
    }
}

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

Задача: 1514. Path with Maximum Probability
Сложность: medium

Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].

Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха.

Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.

Пример:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

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

1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1.

2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v].

3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз.
Верните max_prob[end].

😎 Решение

class Solution {
    func maxProbability(_ n: Int, _ edges: [[Int]], _ succProb: [Double], _ start: Int, _ end: Int) -> Double {
        var maxProb = [Double](repeating: 0, count: n)
        maxProb[start] = 1.0

        for _ in 0..<n-1 {
            var hasUpdate = false
            for j in 0..<edges.count {
                let u = edges[j][0]
                let v = edges[j][1]
                let pathProb = succProb[j]
                if maxProb[u] * pathProb > maxProb[v] {
                    maxProb[v] = maxProb[u] * pathProb
                    hasUpdate = true
                }
                if maxProb[v] * pathProb > maxProb[u] {
                    maxProb[u] = maxProb[v] * pathProb
                    hasUpdate = true
                }
            }
            if !hasUpdate {
                break
            }
        }

        return maxProb[end]
    }
}

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

Задача: 295. Find Median from Data Stream
Сложность: hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.

Например, для arr = [2, 3, 4] медиана равна 3.
Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5.

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

MedianFinder() инициализирует объект MedianFinder.
void addNum(int num) добавляет целое число num из потока данных в структуру данных.
double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.

Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

1⃣Храните числа в контейнере с возможностью изменения размера:
Создайте массив для хранения чисел.

2⃣Добавление нового числа:
Добавьте новое число в массив.

3⃣Вычисление и вывод медианы:
Отсортируйте массив.
Если размер массива нечетный, верните среднее значение массива.
Если размер массива четный, верните среднее арифметическое двух средних значений массива.

😎 Решение:

class MedianFinder {
    private var numbers: [Int] = []

    func addNum(_ num: Int) {
        numbers.append(num)
    }

    func findMedian() -> Double {
        numbers.sort()
        let n = numbers.count
        if n % 2 == 0 {
            return Double(numbers[n / 2 - 1] + numbers[n / 2]) / 2.0
        } else {
            return Double(numbers[n / 2])
        }
    }
}

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

Задача: 214. Shortest Palindrome
Сложность: hard

Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.

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

Пример:

Input: s = "aacecaaa"
Output: "aaacecaaa"

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

1⃣Создание обратной строки:
Создаем обратную строку rev от исходной строки s.

2⃣Итерация для поиска наибольшего палиндрома:
Перемещаемся по индексу i от 0 до n - 1.
Проверяем, является ли подстрока s от 0 до n - i равной подстроке rev от i до конца строки.
Если находим такое совпадение, возвращаем обратную подстроку от начала rev до i + исходная строка s.

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

😎 Решение:

class Solution {
    func shortestPalindrome(_ s: String) -> String {
        let n = s.count
        let rev = String(s.reversed())
        for i in 0..<n {
            let startIndex = s.index(s.startIndex, offsetBy: 0)
            let endIndex = s.index(s.startIndex, offsetBy: n - i)
            let revStartIndex = rev.index(rev.startIndex, offsetBy: i)
            let revEndIndex = rev.endIndex
            
            if s[startIndex..<endIndex] == rev[revStartIndex..<revEndIndex] {
                let prefix = rev[rev.startIndex..<revStartIndex]
                return prefix + s
            }
        }
        return ""
    }
}

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

Задача: 1022. Sum of Root To Leaf Binary Numbers
Сложность: easy

Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.

Пример:

Input: root = [1,0,1,0,1,0,1]
Output: 22

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

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

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

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

😎 Решение:

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

class Solution {
    func sumRootToLeaf(_ root: TreeNode?) -> Int {
        func dfs(_ node: TreeNode?, _ current_value: Int) -> Int {
            guard let node = node else { return 0 }
            let current_value = (current_value << 1) | node.val
            if node.left == nil && node.right == nil {
                return current_value
            }
            return dfs(node.left, current_value) + dfs(node.right, current_value)
        }
        
        return dfs(root, 0)
    }
}

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

Задача: 772. Basic Calculator III
Сложность: medium

Реализуйте базовый калькулятор для вычисления простого строкового выражения.

Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю.

Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].

Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval().

Пример:

Input: s = "1+1"
Output: 2

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

1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@".

2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+".

3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке.

😎 Решение:

class Solution {
    private func evaluate(_ operator: Character, _ first: String, _ second: String) -> String {
        let x = Int(first)!
        let y = Int(second)!
        var res = 0
        
        switch operator {
        case "+":
            res = x
        case "-":
            res = -x
        case "*":
            res = x * y
        default:
            res = x / y
        }
        
        return String(res)
    }
    
    func calculate(_ s: String) -> Int {
        var stack = [String]()
        var curr = ""
        var previousOperator: Character = "+"
        let s = s + "@"
        let operators: Set<Character> = ["+", "-", "*", "/"]
        
        for c in s {
            if c.isNumber {
                curr += String(c)
            } else if c == "(" {
                stack.append(String(previousOperator))
                previousOperator = "+"
            } else {
                if previousOperator == "*" || previousOperator == "/" {
                    stack.append(evaluate(previousOperator, stack.removeLast(), curr))
                } else {
                    stack.append(evaluate(previousOperator, curr, "0"))
                }
                
                curr = ""
                previousOperator = c
                if c == ")" {
                    var currentTerm = 0
                    while !operators.contains(stack.last!) {
                        currentTerm += Int(stack.removeLast())!
                    }
                    
                    curr = String(currentTerm)
                    previousOperator = stack.removeLast().first!
                }
            }
        }
        
        var ans = 0
        for num in stack {
            ans += Int(num)!
        }

        return ans
    }
}

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

Задача: 134. Gas Station
Сложность: medium

Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].

У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.

Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.

Пример:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

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

1⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0.

2⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i].
Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2.

3⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer.

😎 Решение:

func canCompleteCircuit(gas: [Int], cost: [Int]) -> Int {
    var currGain = 0
    var totalGain = 0
    var answer = 0

    for i in 0..<gas.count {
        let gain = gas[i] - cost[i]
        totalGain += gain
        currGain += gain
        if currGain < 0 {
            answer = i + 1
            currGain = 0
        }
    }
    return totalGain >= 0 ? answer : -1
}

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

Задача: 562. Longest Line of Consecutive One in Matrix
Сложность: medium

Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.

Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.

Пример:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

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

1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.

2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.

3⃣Верните максимальную длину.

😎 Решение:

class Solution {
    func longestLine(_ mat: [[Int]]) -> Int {
        if mat.isEmpty || mat[0].isEmpty {
            return 0
        }
        
        let m = mat.count
        let n = mat[0].count
        var maxLength = 0
        
        var horizontal = Array(repeating: Array(repeating: 0, count: n), count: m)
        var vertical = Array(repeating: Array(repeating: 0, count: n), count: m)
        var diagonal = Array(repeating: Array(repeating: 0, count: n), count: m)
        var antiDiagonal = Array(repeating: Array(repeating: 0, count: n), count: m)
        
        for i in 0..<m {
            for j in 0..<n {
                if mat[i][j] == 1 {
                    horizontal[i][j] = (j > 0 ? horizontal[i][j-1] : 0) + 1
                    vertical[i][j] = (i > 0 ? vertical[i-1][j] : 0) + 1
                    diagonal[i][j] = (i > 0 && j > 0 ? diagonal[i-1][j-1] : 0) + 1
                    antiDiagonal[i][j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1][j+1] : 0) + 1
                    
                    maxLength = max(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j])
                }
            }
        }
        
        return maxLength
    }
}

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

Задача: 207. Course Schedule
Сложность: medium

Всего у вас есть numCourses курсов, которые нужно пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.

Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните true, если вы можете завершить все курсы. В противном случае верните false.

Пример:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

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

1⃣Создайте массив indegree длины n, где indegree[x] хранит количество входящих рёбер в узел x. Создайте список смежности adj, в котором adj[x] содержит все узлы с входящим ребром от узла x, то есть соседей узла x. Создайте этот список смежности, итерируя prerequisites. Для каждого prerequisites добавьте ребро от prerequisites[1] к prerequisites[0] и увеличьте indegree prerequisites[0] на 1.

2⃣Инициализируйте очередь целых чисел q и начните алгоритм BFS, перемещаясь от листовых узлов к родительским узлам. Начните обход BFS, поместив все листовые узлы (indegree равное 0) в очередь. Создайте целочисленную переменную nodesVisited = 0 для подсчета количества посещенных узлов.

3⃣Пока очередь не пуста:
Извлеките первый узел из очереди.
Увеличьте nodesVisited на 1.
Для каждого соседа (узлы, которые имеют входящее ребро от узла) узла уменьшите indegree[neighbor] на 1, чтобы удалить ребро node -> neighbor.
Если indegree[neighbor] == 0, это означает, что neighbor ведет себя как листовой узел, поэтому добавьте neighbor в очередь.
Если количество посещенных узлов меньше общего количества узлов, то есть nodesVisited < n, верните false, так как должен быть цикл. В противном случае, если nodesVisited == numCourses, верните true. Можно сократить это до просто возвращения nodesVisited == numCourses.

😎 Решение:

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var indegree = [Int](repeating: 0, count: numCourses)
        var adj = [[Int]](repeating: [Int](), count: numCourses)
        
        for prerequisite in prerequisites {
            adj[prerequisite[1]].append(prerequisite[0])
            indegree[prerequisite[0]] += 1
        }
        
        var q = [Int]()
        for i in 0..<numCourses {
            if indegree[i] == 0 {
                q.append(i)
            }
        }
        
        var nodesVisited = 0
        while !q.isEmpty {
            let node = q.removeFirst()
            nodesVisited += 1
            
            for neighbor in adj[node] {
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0 {
                    q.append(neighbor)
                }
            }
        }
        
        return nodesVisited == numCourses
    }
}

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

Задача: 23. Merge k Sorted Lists
Сложность: medium

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его.

Пример:

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

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

1⃣Используем min-heap для хранения текущих головных узлов всех списков.

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

3⃣Повторяем, пока куча не пуста, возвращаем голову объединенного списка.

😎Решение:

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

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
    var heap = [ListNode]()
    
    for list in lists {
        if let node = list {
            heap.append(node)
        }
    }
    
    heap.sort { $0.val < $1.val }
    
    let dummy = ListNode(0)
    var current: ListNode? = dummy
    
    while !heap.isEmpty {
        let smallest = heap.removeFirst()
        current?.next = smallest
        current = smallest
        
        if let next = smallest.next {
            var index = heap.firstIndex { $0.val > next.val } ?? heap.count
            heap.insert(next, at: index)
        }
    }
    
    return dummy.next
}

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

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

На сетке размером m на n, заполненной неотрицательными числами, найдите путь от верхнего левого угла до нижнего правого, который минимизирует сумму всех чисел вдоль своего пути.

Примечание: Вы можете перемещаться только вниз или вправо в любой момент времени.

Пример:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

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

1⃣Инициализация дополнительной матрицы dp такого же размера, как и исходная матрица. В этой матрице dp(i, j) представляет минимальную сумму пути от индекса (i, j) до самого правого нижнего элемента. Начинаем с инициализации самого правого нижнего элемента dp как последнего элемента заданной матрицы.

2⃣Для каждого элемента, начиная с правого нижнего угла, мы обходим матрицу в обратном порядке и заполняем её требуемыми минимальными суммами. Важно отметить, что на каждом элементе мы можем перемещаться либо вправо, либо вниз.

3⃣Для заполнения минимальной суммы используется уравнение: dp(i, j) = grid(i, j) + min(dp(i+1, j), dp(i, j+1)), с учётом граничных условий.

😎 Решение:

func minPathSum(_ grid: [[Int]]) -> Int {
    var dp = Array(repeating: Array(repeating: 0, count: grid[0].count), count: grid.count)
    for i in stride(from: grid.count - 1, through: 0, by: -1) {
        for j in stride(from: grid[0].count - 1, through: 0, by: -1) {
            if i == grid.count - 1 && j != grid[0].count - 1 {
                dp[i][j] = grid[i][j] + dp[i][j + 1]
            } else if j == grid[0].count - 1 && i != grid.count - 1 {
                dp[i][j] = grid[i][j] + dp[i + 1][j]
            } else if j != grid[0].count - 1 && i != grid.count - 1 {
                dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1])
            } else {
                dp[i][j] = grid[i][j]
            }
        }
    }
    return dp[0][0]
}

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

Задача: 868. Binary Gap
Сложность: easy

Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0.

Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3.

Пример:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

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

1⃣Создайте список A индексов i, таких что в двоичном представлении числа n i-й бит установлен в 1.

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

3⃣Верните найденное максимальное расстояние.

😎 Решение:

class Solution {
    func binaryGap(_ N: Int) -> Int {
        var A = [Int]()
        for i in 0..<32 where (N >> i) & 1 == 1 {
            A.append(i)
        }
        var ans = 0
        for i in 0..<A.count - 1 {
            ans = max(ans, A[i + 1] - A[i])
        }
        return ans
    }
}

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

Задача: 510. Inorder Successor in BST II
Сложность: medium

Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null.

Последующий узла — это узел с наименьшим ключом, большим, чем node.val.

Вы будете иметь прямой доступ к узлу, но не к корню дерева. Каждый узел будет иметь ссылку на своего родителя. Ниже приведено определение для Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Пример:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

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

1⃣Проверка правого поддерева
Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order.

2⃣Поиск предка
Если у узла нет правого потомка, поднимайтесь по дереву до тех пор, пока узел не станет левым потомком своего родителя. Родитель этого узла будет следующим узлом в порядке in-order.

3⃣Возвращение результата
Верните найденный узел или null, если следующий узел не найден.

😎 Решение:

class Node {
    var val: Int
    var left: Node?
    var right: Node?
    var parent: Node?

    init(_ val: Int) {
        self.val = val
    }
}

class Solution {
    func inorderSuccessor(_ x: Node?) -> Node? {
        var x = x

        if let right = x?.right {
            x = right
            while let left = x?.left {
                x = left
            }
            return x
        }

        while let parent = x?.parent, x === parent.right {
            x = parent
        }
        return x?.parent
    }
}

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

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

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

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

func minSubsequences(_ source: String, _ target: String) -> Int {
    let sourceArray = Array(source)
    let targetArray = Array(target)
    var subsequencesCount = 0
    var targetIndex = 0

    while targetIndex < targetArray.count {
        var sourceIndex = 0
        subsequencesCount += 1
        let startIndex = targetIndex

        while sourceIndex < sourceArray.count && targetIndex < targetArray.count {
            if sourceArray[sourceIndex] == targetArray[targetIndex] {
                targetIndex += 1
            }
            sourceIndex += 1
        }

        if targetIndex == startIndex {
            return -1
        }
    }

    return subsequencesCount
}

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

Задача: 1095. Find in Mountain Array
Сложность: hard

Массив arr является горным массивом тогда и только тогда, когда:

Длина массива arr >= 3.
Существует некоторое i с 0 < i < arr.length - 1 такое, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1.

Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray:

MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0).
MountainArray.length() возвращает длину массива.
Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы.

Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

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

1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика.

2⃣Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем.

3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1.

😎 Решение:

class Solution {
    func findInMountainArray(_ target: Int, _ mountainArr: MountainArray) -> Int {
        let length = mountainArr.length()
        
        var low = 1
        var high = length - 2
        while low != high {
            let mid = (low + high) / 2
            if mountainArr.get(mid) < mountainArr.get(mid + 1) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        let peak = low
        
        low = 0
        high = peak
        while low < high {
            let mid = (low + high) / 2
            if mountainArr.get(mid) < target {
                low = mid + 1
            } else {
                high = mid
            }
        }
        if mountainArr.get(low) == target {
            return low
        }
        
        low = peak + 1
        high = length - 1
        while low < high {
            let mid = (low + high) / 2
            if mountainArr.get(mid) > target {
                low = mid + 1
            } else {
                high = mid
            }
        }
        if mountainArr.get(low) == target {
            return low
        }
        
        return -1
    }
}

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

Задача: 530. Minimum Absolute Difference in BST
Сложность: easy

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

Пример:

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

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

1⃣Обход дерева в порядке возрастания (инфиксный обход):
Создайте список inorderNodes для хранения значений узлов.
Выполните инфиксный обход дерева, добавляя значения узлов в список.

2⃣ Нахождение минимальной разницы:
Создайте переменную minDifference и инициализируйте её бесконечностью.
Пройдите по списку inorderNodes, начиная с индекса 1, и найдите минимальную абсолютную разницу между последовательными элементами.

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

😎 Решение:

class Solution {
    private var inorderNodes: [Int] = []

    func getMinimumDifference(_ root: TreeNode?) -> Int {
        inorderTraversal(root)
        var minDifference = Int.max
        for i in 1..<inorderNodes.count {
            minDifference = min(minDifference, inorderNodes[i] - inorderNodes[i - 1])
        }
        return minDifference
    }

    private func inorderTraversal(_ node: TreeNode?) {
        guard let node = node else { return }
        inorderTraversal(node.left)
        inorderNodes.append(node.val)
        inorderTraversal(node.right)
    }
}

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

Задача: 1135. Connecting Cities With Minimum Cost
Сложность: medium

Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.

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

Стоимость - это сумма использованных стоимостей соединений.

Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

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

1⃣Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.

2⃣Итерация по рёбрам и объединение:
Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST).

3⃣Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.

😎 Решение:

class DisjointSet {
    private var parent: [Int]

    init(_ n: Int) {
        parent = Array(0...n)
    }

    func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    func union(_ x: Int, _ y: Int) {
        let rootX = find(x)
        let rootY = find(y)
        if rootX != rootY {
            parent[rootY] = rootX
        }
    }
}

class Solution {
    func minimumCost(_ n: Int, _ connections: [[Int]]) -> Int {
        let sortedConnections = connections.sorted { $0[2] < $1[2] }
        let disjointSet = DisjointSet(n)
        var totalCost = 0
        var edgesUsed = 0

        for connection in sortedConnections {
            let x = connection[0]
            let y = connection[1]
            let cost = connection[2]

            if disjointSet.find(x) != disjointSet.find(y) {
                disjointSet.union(x, y)
                totalCost += cost
                edgesUsed += 1
                if edgesUsed == n - 1 {
                    return totalCost
                }
            }
        }
        return edgesUsed == n - 1 ? totalCost : -1
    }
}

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