Задача: 117. Populating Next Right Pointers in Each Node II
Сложность: medium

Вам дано бинарное дерево:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1⃣Инициализируйте очередь Q, которая будет использоваться во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда дело доходит до определения уровня конкретного узла. Можно добавить в очередь пару (узел, уровень), и каждый раз, когда мы добавляем детей узла, мы добавляем (node.left, parent_level+1) и (node.right, parent_level+1). Этот подход может оказаться неэффективным для нашего алгоритма, так как нам нужны все узлы на одном уровне, и потребуется дополнительная структура данных.

2⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня - использовать разграничение между уровнями. Обычно мы вставляем в очередь элемент NULL, который обозначает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого объема памяти, пропорционального количеству уровней в дереве.

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

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Так как на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

import Foundation

class Node {
    var value: Int
    var left: Node?
    var right: Node?
    var next: Node?

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

class Solution {
    func connect(_ root: Node?) -> Node? {
        guard let root = root else { return nil }
        
        var queue: [Node] = [root]
        
        while !queue.isEmpty {
            let size = queue.count
            for i in 0..<size {
                let node = queue.removeFirst()
                if i < size - 1 {
                    node.next = queue.first
                }
                
                if let leftChild = node.left {
                    queue.append(leftChild)
                }
                if let rightChild = node.right {
                    queue.append(rightChild)
                }
            }
        }
        
        return root
    }
}

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

Задача: 104. Maximum Depth of Binary Tree
Сложность: easy

Дан корень бинарного дерева, верните его максимальную глубину.

Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 3

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

1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2⃣Для данной задачи подойдет несколько способов.

3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.

😎 Решение:

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

func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    let leftHeight = maxDepth(root.left)
    let rightHeight = maxDepth(root.right)
    return 1 + max(leftHeight, rightHeight)
}

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

Задача: 292. Nim Game
Сложность: easy

Вы играете в следующую игру Nim со своим другом:

Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

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

1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎 Решение:

class Solution {
    func canWinNim(_ n: Int) -> Bool {
        return n % 4 != 0
    }
}

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

Задача: 24. Swap Nodes in Pairs
Сложность: medium

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

Пример:

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

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

1⃣Используем фиктивный узел (dummy), чтобы упростить обработку головы списка.

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

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

😎Решение:

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

func swapPairs(_ head: ListNode?) -> ListNode? {
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    
    while current?.next != nil && current?.next?.next != nil {
        let first = current?.next
        let second = current?.next?.next
        
        first?.next = second?.next
        second?.next = first
        current?.next = second
        
        current = first
    }
    
    return dummy.next
}

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

Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

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

😎 Решение:

class Solution {
    func calcEquation(_ equations: [[String]], _ values: [Double], _ queries: [[String]]) -> [Double] {
        var graph = [String: [String: Double]]()

        for (i, equation) in equations.enumerated() {
            let A = equation[0], B = equation[1]
            let value = values[i]
            graph[A, default: [String: Double]()][B] = value
            graph[B, default: [String: Double]()][A] = 1.0 / value
        }

        func bfs(_ start: String, _ end: String) -> Double {
            guard let _ = graph[start], let _ = graph[end] else { return -1.0 }
            var queue = [(start, 1.0)]
            var visited = Set<String>()
            
            while !queue.isEmpty {
                let (current, curProduct) = queue.removeFirst()
                if current == end { return curProduct }
                visited.insert(current)
                for (neighbor, value) in graph[current, default: [String: Double]()] {
                    if !visited.contains(neighbor) {
                        queue.append((neighbor, curProduct * value))
                    }
                }
            }
            return -1.0
        }

        var results = [Double]()
        for query in queries {
            let C = query[0], D = query[1]
            results.append(bfs(C, D))
        }
        return results
    }
}

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

Задача: 98. Validate Binary Search Tree
Сложность: medium

Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST).

Допустимое BST определяется следующим образом:

Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.
Правое поддерево узла содержит только узлы с ключами, большими, чем ключ узла.
Оба поддерева — левое и правое — также должны быть бинарными деревьями поиска.

Пример:

Input: root = [2,1,3]
Output: true

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

1⃣Давайте воспользуемся порядком узлов при симметричном обходе (inorder traversal):

Левый -> Узел -> Правый.

Постордер:

Здесь узлы перечисляются в порядке их посещения, и вы можете следовать последовательности 1-2-3-4-5 для сравнения различных стратегий.

Порядок "Левый -> Узел -> Правый" при симметричном обходе означает, что для BST каждый элемент должен быть меньше следующего.

2⃣Следовательно, алгоритм с временной сложностью O(N) и пространственной сложностью O(N) может быть простым:

Вычислить список симметричного обхода inorder.

Проверить, меньше ли каждый элемент в списке inorder следующего за ним.

Постордер:

3⃣Нужно ли сохранять весь список симметричного обхода?

На самом деле, нет. Достаточно последнего добавленного элемента inorder, чтобы на каждом шаге убедиться, что дерево является BST (или нет). Следовательно, можно объединить оба шага в один и уменьшить используемое пространство.

😎 Решение:

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

class Solution {
    private var prev: Int?
    
    private func inorder(_ root: TreeNode?) -> Bool {
        guard let root = root else {
            return true
        }
        
        if !inorder(root.left) {
            return false
        }
        
        if let prev = prev, root.val <= prev {
            return false
        }
        prev = root.val
        
        return inorder(root.right)
    }
    
    func isValidBST(_ root: TreeNode?) -> Bool {
        prev = nil  // Reset previous value
        return inorder(root)
    }
}

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

Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard

Дано n заказов, каждый из которых состоит из услуги забора и доставки.

Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).

Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

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

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

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

3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.

😎 Решение:

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

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

Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов.

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

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

1⃣Инициализация и построение частотного массива:
Создайте хеш-таблицу для отслеживания частот элементов массива arr.
Итеративно увеличивайте частоту элементов в хеш-таблице.

2⃣Сортировка и удаление элементов:
Создайте массив частот и заполните его значениями из хеш-таблицы.
Отсортируйте массив частот.
Инициализируйте переменную для отслеживания числа удаленных элементов и итеративно добавляйте частоты, пока количество удаленных элементов не превысит k.

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

😎 Решение:

class Solution {
    func findLeastNumOfUniqueInts(_ arr: [Int], _ k: Int) -> Int {
        var freqMap = [Int: Int]()
        for num in arr {
            freqMap[num, default: 0] += 1
        }
        
        var frequencies = Array(freqMap.values)
        frequencies.sort()
        
        var elementsRemoved = 0
        for i in 0..<frequencies.count {
            elementsRemoved += frequencies[i]
            if elementsRemoved > k {
                return frequencies.count - i
            }
        }
        
        return 0
    }
}

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

Задача: 240. Search a 2D Matrix II
Сложность: medium

Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства:

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

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

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

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

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

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

😎 Решение:

class Solution {
    private func binarySearch(_ matrix: [[Int]], _ target: Int, _ start: Int, _ vertical: Bool) -> Bool {
        var lo = start
        var hi = vertical ? matrix[0].count - 1 : matrix.count - 1

        while hi >= lo {
            let mid = (lo + hi) / 2
            if vertical {
                if matrix[start][mid] < target {
                    lo = mid + 1
                } else if matrix[start][mid] > target {
                    hi = mid - 1
                } else {
                    return true
                }
            } else {
                if matrix[mid][start] < target {
                    lo = mid + 1
                } else if matrix[mid][start] > target {
                    hi = mid - 1
                } else {
                    return true
                }
            }
        }
        return false
    }

    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if matrix.isEmpty || matrix[0].isEmpty {
            return false
        }

        let shorterDim = min(matrix.count, matrix[0].count)
        for i in 0..<shorterDim {
            if binarySearch(matrix, target, i, true) || binarySearch(matrix, target, i, false) {
                return true
            }
        }
        return false
    }
}

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

⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти

Вот отсортированная база с тонной материала (постепенно пополняется):

(363 видео, 87 книги) — Python
(415 видео, 68 книги) — Frontend
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++/C#
(343 видео, 87 книги) — Java/QA
(176 видео, 32 книги) — Git/Linux
(174 видео, 91 книги) — DevOps
(167 видео, 53 книги) — PHP/1С
(227 видео, 83 книги) — SQL/БД
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go/Rust
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(137 видео, 93 книги) — DS/ML
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(136 видео, 33 книги) — PM/HR

Скачивать ничего не нужно — все выложили в Telegram

Задача: 657. Robot Return to Origin
Сложность: easy

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

Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз).

Верните true, если робот возвращается в исходную точку после завершения всех своих движений, или false в противном случае.

Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода.

Пример:

Input: moves = "UD"
Output: true

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

1⃣Инициализация координат:
Начните с координат (0, 0).

2⃣Обработка движений:
Пройдите по строке moves и обновляйте координаты в зависимости от движения:
'R' увеличивает координату x на 1.
'L' уменьшает координату x на 1.
'U' увеличивает координату y на 1.
'D' уменьшает координату y на 1.

3⃣Проверка конечных координат:
Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    func judgeCircle(_ moves: String) -> Bool {
        var x = 0
        var y = 0
        for move in moves {
            switch move {
                case "R": x += 1
                case "L": x -= 1
                case "U": y += 1
                case "D": y -= 1
                default: break
            }
        }
        return x == 0 && y == 0
    }
}

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

Задача: 623. Add One Row to Tree
Сложность: medium

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

3⃣Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья.

😎 Решение:

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

func addOneRow(_ root: TreeNode?, _ val: Int, _ depth: Int) -> TreeNode? {
    if depth == 1 {
        return TreeNode(val, root, nil)
    }
    
    var queue: [TreeNode] = []
    if let root = root {
        queue.append(root)
    }
    var currentDepth = 1
    
    while !queue.isEmpty {
        if currentDepth == depth - 1 {
            for node in queue {
                node.left = TreeNode(val, node.left, nil)
                node.right = TreeNode(val, nil, node.right)
            }
            break
        }
        currentDepth += 1
        var nextQueue: [TreeNode] = []
        for node in queue {
            if let left = node.left {
                nextQueue.append(left)
            }
            if let right = node.right {
                nextQueue.append(right)
            }
        }
        queue = nextQueue
    }
    
    return root
}

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

Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).

2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).

3⃣Возврат результата:
Отсортировать ключи словаря по col и затем по row.
Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список.

😎 Решение:

class Solution {
    func verticalTraversal(_ root: TreeNode?) -> [[Int]] {
        var colTable = [Int: [(Int, Int)]]()
        var queue: [(TreeNode?, Int, Int)] = [(root, 0, 0)]
        
        while !queue.isEmpty {
            let (node, row, col) = queue.removeFirst()
            if let node = node {
                if colTable[col] != nil {
                    colTable[col]!.append((row, node.val))
                } else {
                    colTable[col] = [(row, node.val)]
                }
                queue.append((node.left, row + 1, col - 1))
                queue.append((node.right, row + 1, col + 1))
            }
        }
        
        var result = [[Int]]()
        for key in colTable.keys.sorted() {
            colTable[key]!.sort { $0 < $1 }
            result.append(colTable[key]!.map { $0.1 })
        }
        
        return result
    }
}

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

Задача: 229. Majority Element II
Сложность: medium

Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.

Пример:

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

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

1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика.

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

3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат.

😎 Решение:

class Solution {
    func majorityElement(_ nums: [Int]) -> [Int] {
        var count1 = 0, count2 = 0
        var candidate1: Int? = nil
        var candidate2: Int? = nil
        
        for n in nums {
            if let c1 = candidate1, c1 == n {
                count1 += 1
            } else if let c2 = candidate2, c2 == n {
                count2 += 1
            } else if count1 == 0 {
                candidate1 = n
                count1 = 1
            } else if count2 == 0 {
                candidate2 = n
                count2 = 1
            } else {
                count1 -= 1
                count2 -= 1
            }
        }
        
        count1 = 0
        count2 = 0
        
        for n in nums {
            if let c1 = candidate1, c1 == n {
                count1 += 1
            }
            if let c2 = candidate2, c2 == n {
                count2 += 1
            }
        }
        
        var result: [Int] = []
        let n = nums.count
        
        if let c1 = candidate1, count1 > n / 3 {
            result.append(c1)
        }
        if let c2 = candidate2, count2 > n / 3 {
            result.append(c2)
        }
        
        return result
    }
}

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