Swift | LeetCode

Задача: 1019. Next Greater Node In Linked List
Сложность: medium

Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.

Пример:

Input: head = [2,1,5]
Output: [5,5,0]

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

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

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

3⃣Заполнение оставшихся значений:
Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента.

😎 Решение:

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

class Solution {
    func nextLargerNodes(_ head: ListNode?) -> [Int] {
        var values = [Int]()
        var current = head
        while current != nil {
            values.append(current!.val)
            current = current?.next
        }
        
        var answer = [Int](repeating: 0, count: values.count)
        var stack = [Int]()
        
        for i in 0..<values.count {
            while !stack.isEmpty && values[stack.last!] < values[i] {
                answer[stack.removeLast()] = values[i]
            }
            stack.append(i)
        }
        
        return answer
    }
}

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        var x = abs(a), y = abs(b)
        if x < y {
            return getSum(b, a)
        }
        let sign = a > 0 ? 1 : -1

        if a * b >= 0 {
            while y != 0 {
                let carry = (x & y) << 1
                x ^= y
                y = carry
            }
        } else {
            while y != 0 {
                let borrow = ((~x) & y) << 1
                x ^= y
                y = borrow
            }
        }
        return x * sign
    }
}

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

Задача: 1245. Tree Diameter
Сложность: medium

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

Пример:

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

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

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

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Solution {
    func treeDiameter(_ edges: [[Int]]) -> Int {
        if edges.isEmpty { return 0 }

        var graph = [Int: [Int]]()
        for edge in edges {
            graph[edge[0], default: []].append(edge[1])
            graph[edge[1], default: []].append(edge[0])
        }

        var farthestNode = 0

        func dfs(_ node: Int, _ parent: Int) -> Int {
            var maxDepth = 0
            for neighbor in graph[node]! {
                if neighbor != parent {
                    let depth = dfs(neighbor, node)
                    if depth + 1 > maxDepth {
                        maxDepth = depth + 1
                        farthestNode = neighbor
                    }
                }
            }
            return maxDepth
        }

        _ = dfs(0, -1)
        let startNode = farthestNode

        _ = dfs(startNode, -1)
        return dfs(farthestNode, -1)
    }
}

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

Задача: 560. Subarray Sum Equals K
Сложность: medium

Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.

Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

Input: nums = [1,1,1], k = 2
Output: 2

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

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

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

😎 Решение:

class Solution {
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var count = 0
        for start in 0..<nums.count {
            for end in (start + 1)...nums.count {
                var sum = 0
                for i in start..<end {
                    sum += nums[i]
                }
                if sum == k {
                    count += 1
                }
            }
        }
        return count
    }
}

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

Задача: №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 <= a, b, c, d < n
- a, b, c и d различны.
- nums[a] + nums[b] + nums[c] + nums[d] == target

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

Пример:

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

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

1⃣Отсортировать массив для удобного пропуска дубликатов и эффективного поиска.

2⃣Использовать два вложенных цикла для выбора первых двух чисел и два указателя для поиска оставшихся двух чисел.

3⃣Обрабатывать дубликаты, чтобы избежать повторяющихся четверок.

😎 Решение:

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

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

Задача: 717. 1-bit and 2-bit Characters
Сложность: easy

У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.

Пример:

Input: bits = [1,0,0]
Output: true

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

1⃣Инициализируйте индекс для итерации по массиву.

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

3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат.

😎 Решение:

func isOneBitCharacter(_ bits: [Int]) -> Bool {
    var i = 0
    while i < bits.count - 1 {
        i += bits[i] + 1
    }
    return i == bits.count - 1
}

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

Задача: 225. Implement Stack using Queues
Сложность: easy

Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).

Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.

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

Пример:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

1⃣Реализация методов push и pop:
Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.
Метод pop удаляет элемент из q1 и обновляет значение top.

2⃣Реализация методов top и empty:
Метод top возвращает верхний элемент стека.
Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.

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

😎 Решение:

class MyStack {
    private var q1 = [Int]()
    private var q2 = [Int]()
    private var topElement: Int = 0

    func push(_ x: Int) {
        q2.append(x)
        topElement = x
        while !q1.isEmpty {
            q2.append(q1.removeFirst())
        }
        (q1, q2) = (q2, q1)
    }

    func pop() {
        q1.removeFirst()
        if !q1.isEmpty {
            topElement = q1.first!
        }
    }

    func empty() -> Bool {
        return q1.isEmpty
    }

    func top() -> Int {
        return topElement
    }
}

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

Задача: 908. Smallest Range I
Сложность: easy

Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем.

Пример:

Input: nums = [1], k = 0
Output: 0

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

1⃣Найти минимальное и максимальное значения массива nums.

2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции.

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

😎 Решение:

class Solution {
    func smallestRangeI(_ nums: [Int], _ k: Int) -> Int {
        let minVal = nums.min()!
        let maxVal = nums.max()!
        return max(0, (maxVal - k) - (minVal + k))
    }
}

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

Задача: 339. Nested List Weight Sum
Сложность: medium

Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками.

Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.

Верните сумму каждого целого числа в nestedList, умноженного на его глубину.

Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

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

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

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

3⃣ Возврат результата:
Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму.

😎 Решение:

class Solution {
    func depthSum(_ nestedList: [NestedInteger]) -> Int {
        return dfs(nestedList, 1)
    }
    
    private func dfs(_ list: [NestedInteger], _ depth: Int) -> Int {
        var total = 0
        for nested in list {
            if nested.isInteger() {
                total += nested.getInteger() * depth
            } else {
                total += dfs(nested.getList(), depth + 1)
            }
        }
        return total
    }
}

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

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

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

Задача: 77. Combinations
Сложность: medium

Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].

Ответ можно вернуть в любом порядке.

Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

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

1⃣Инициализировать массив ответов ans и массив для построения комбинаций curr.

2⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:
Если длина curr равна k, добавить копию curr в ans и вернуться.
Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.
Итерировать num от firstNum до firstNum + available включительно.
Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.

3⃣Вызвать backtrack с изначально пустым curr и firstNum = 1.
Вернуть ans.

😎 Решение:

func combine(_ n: Int, _ k: Int) -> [[Int]] {
    var ans = [[Int]]()
    func backtrack(_ curr: inout [Int], _ firstNum: Int) {
        if curr.count == k {
            ans.append(curr)
            return
        }
        let need = k - curr.count
        let remain = n - firstNum + 1
        let available = remain - need
        for num in firstNum...(firstNum + available) {
            curr.append(num)
            backtrack(&curr, num + 1)
            curr.removeLast()
        }
    }
    var initial = [Int]()
    backtrack(&initial, 1)
    return ans
}

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

Задача: 842. Split Array into Fibonacci Sequence
Сложность: medium

Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.

Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.

Пример:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

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

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

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

3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор.

😎 Решение:

class Solution {
    func splitIntoFibonacci(_ S: String) -> [Int] {
        let N = S.count
        let sArray = Array(S)
        
        for i in 0..<min(10, N) {
            if sArray[0] == "0" && i > 0 { break }
            let a = Int(String(sArray[0...i]))!
            if a >= Int32.max { break }

            outerLoop: for j in (i+1)..<min(i+10, N) {
                if sArray[i+1] == "0" && j > i+1 { break }
                let b = Int(String(sArray[i+1...j]))!
                if b >= Int32.max { break }

                var fib = [a, b]
                var k = j + 1
                while k < N {
                    let next = fib[fib.count - 2] + fib[fib.count - 1]
                    if next > Int32.max { break }
                    let nextS = String(next)
                    if sArray[k...].starts(with: Array(nextS)) {
                        k += nextS.count
                        fib.append(next)
                    } else {
                        continue outerLoop
                    }
                }
                if fib.count >= 3 { return fib }
            }
        }

        return []
    }
}

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

Задача: 170. Two Sum III - Data structure design
Сложность: easy

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

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

- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.
- void add(int number) добавляет число в структуру данных.
- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.

Пример:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

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

1⃣Инициализация указателей:
Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.

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

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

😎 Решение:

class TwoSum {
    private var nums = [Int: Int]()

    init() {}

    func add(_ number: Int) {
        nums[number, default: 0] += 1
    }

    func find(_ value: Int) -> Bool {
        for (num, count) in nums {
            let complement = value - num
            if (complement != num && nums[complement] != nil) ||
               (complement == num && count > 1) {
                return true
            }
        }
        return false
    }
}

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

Задача: 661. Image Smoother
Сложность: easy

Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.

Пример:

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

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

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

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

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

😎 Решение:

class Solution {
    func imageSmoother(_ img: [[Int]]) -> [[Int]] {
        let m = img.count
        let n = img[0].count
        var result = Array(repeating: Array(repeating: 0, count: n), count: m)
        
        for i in 0..<m {
            for j in 0..<n {
                var count = 0
                var total = 0
                for ni in max(0, i - 1)...min(m - 1, i + 1) {
                    for nj in max(0, j - 1)...min(n - 1, j + 1) {
                        total += img[ni][nj]
                        count += 1
                    }
                }
                result[i][j] = total / count
            }
        }
        
        return result
    }
}

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

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

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

Задача: 254. Factor Combinations
Сложность: medium

Числа можно рассматривать как произведение их множителей.

Например, 8 = 2 x 2 x 2 = 2 x 4.
Дано целое число n, верните все возможные комбинации его множителей. Вы можете вернуть ответ в любом порядке.

Обратите внимание, что множители должны быть в диапазоне [2, n - 1].

Пример:

Input: n = 1
Output: []

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

1⃣Определите вспомогательную функцию backtracking, которая принимает два параметра: factors (список множителей) и ans (список списков для сохранения всех комбинаций множителей). Начните вызов backtracking с factors, содержащим только n, и пустым списком ans.

2⃣Основная логика функции backtracking:
Если размер factors больше 1, добавьте его копию в ans, так как это одно из желаемых решений.
Получите последний элемент factors (lastFactor) и удалите его из factors.
Если factors пуст, итерируйте i от 2. В противном случае, итерируйте i от последнего значения в factors. Итерируйте, пока i <= lastFactor / i.
Для каждого i, если lastFactor % i == 0, добавьте i и lastFactor / i в factors и вызовите backtracking(factors, ans).
Восстановите список (откат) factors, удалив последние два элемента из factors.
Восстановите список (откат) factors, добавив обратно lastFactor.

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

😎 Решение:

class Solution {
    private func backtracking(_ factors: inout [Int], _ ans: inout [[Int]]) {
        if factors.count > 1 {
            ans.append(factors)
        }
        let lastFactor = factors.removeLast()
        for i in (factors.isEmpty ? 2 : factors.last!)...lastFactor {
            if i * i > lastFactor { break }
            if lastFactor % i == 0 {
                factors.append(i)
                factors.append(lastFactor / i)
                backtracking(&factors, &ans)
                factors.removeLast()
                factors.removeLast()
            }
        }
        factors.append(lastFactor)
    }

    func getFactors(_ n: Int) -> [[Int]] {
        var ans: [[Int]] = []
        var factors: [Int] = [n]
        backtracking(&factors, &ans)
        return ans
    }
}

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

Задача: 443. String Compression
Сложность: medium

Дан массив символов chars, сжать его, используя следующий алгоритм:

Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:

Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.

После того как вы закончите модификацию входного массива, верните новую длину массива.

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

Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

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

1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0.

2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе.

3⃣Верните res.

😎 Решение:

class Solution {
    func compress(_ chars: inout [Character]) -> Int {
        var i = 0
        var res = 0
        while i < chars.count {
            var groupLength = 1
            while i + groupLength < chars.count && chars[i + groupLength] == chars[i] {
                groupLength += 1
            }
            chars[res] = chars[i]
            res += 1
            if groupLength > 1 {
                let strRepr = String(groupLength)
                for ch in strRepr {
                    chars[res] = ch
                    res += 1
                }
            }
            i += groupLength
        }
        return res
    }
}

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

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

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

Задача: 1004. Max Consecutive Ones III
Сложность: medium

Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.

Пример:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

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

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

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

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

😎 Решение:

class Solution {
    func longestOnes(_ nums: [Int], _ k: Int) -> Int {
        var left = 0
        var maxOnes = 0
        var zeroCount = 0

        for right in 0..<nums.count {
            if nums[right] == 0 {
                zeroCount += 1
            }

            while zeroCount > k {
                if nums[left] == 0 {
                    zeroCount -= 1
                }
                left += 1
            }

            maxOnes = max(maxOnes, right - left + 1)
        }

        return maxOnes
    }
}

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

Задача: 172. Factorial Trailing Zeroes
Сложность: medium

Дано целое число n, верните количество конечных нулей в n!.

Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Пример:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

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

1⃣Вычислите факториал n:
Инициализируйте переменную nFactorial значением 1.
Для каждого i от 2 до n включительно умножайте nFactorial на i.

2⃣Подсчитайте количество конечных нулей в nFactorial:
Инициализируйте переменную zeroCount значением 0.
Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1.

3⃣Верните значение zeroCount как количество конечных нулей в n!.

😎 Решение:

func trailingZeroes(_ n: Int) -> Int {
    var nFactorial = 1
    for i in 2...n {
        nFactorial *= i
    }

    var zeroCount = 0
    var nFactorialBigInt = nFactorial

    while nFactorialBigInt % 10 == 0 {
        nFactorialBigInt /= 10
        zeroCount += 1
    }

    return zeroCount
}

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