Задача: 1119. Remove Vowels from a String
Сложность: easy

Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.

Пример:

Input: s = "leetcodeisacommunityforcoders"
Output: "ltcdscmmntyfrcdrs"

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

1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае.

2⃣Инициализируйте пустую строку ans.

3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans.

😎 Решение:

class Solution {
    func removeVowels(_ s: String) -> String {
        var ans = ""
        for char in s {
            if !isVowel(char) {
                ans.append(char)
            }
        }
        return ans
    }
    
    private func isVowel(_ c: Character) -> Bool {
        return "aeiou".contains(c)
    }
}

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

Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

import Foundation

func countOfAtoms(_ formula: String) -> String {
    var stack = [Dictionary<String, Int>]()
    stack.append(Dictionary<String, Int>())
    let formula = Array(formula)
    var i = 0
    let n = formula.count
    
    while i < n {
        if formula[i] == "(" {
            stack.append(Dictionary<String, Int>())
            i += 1
        } else if formula[i] == ")" {
            let top = stack.removeLast()
            i += 1
            var multiplicity = 0
            while i < n && formula[i].isNumber {
                multiplicity = multiplicity * 10 + Int(String(formula[i]))!
                i += 1
            }
            multiplicity = multiplicity == 0 ? 1 : multiplicity
            for (name, count) in top {
                stack[stack.count - 1][name, default: 0] += count * multiplicity
            }
        } else {
            var start = i
            i += 1
            while i < n && formula[i].isLowercase {
                i += 1
            }
            let name = String(formula[start..<i])
            start = i
            var multiplicity = 0
            while i < n && formula[i].isNumber {
                multiplicity = multiplicity * 10 + Int(String(formula[i]))!
                i += 1
            }
            multiplicity = multiplicity == 0 ? 1 : multiplicity
            stack[stack.count - 1][name, default: 0] += multiplicity
        }
    }
    
    let last = stack.removeLast()
    var result = ""
    for key in last.keys.sorted() {
        result += key
        if last[key]! > 1 {
            result += "\(last[key]!)"
        }
    }
    return result
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

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

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

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

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

😎 Решение:

func prevPermOpt1(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count
    var i = n - 2
    while i >= 0 && arr[i] <= arr[i + 1] {
        i -= 1
    }
    if i == -1 {
        return arr
    }
    
    var j = n - 1
    while arr[j] >= arr[i] || (j < n - 1 && arr[j] == arr[j + 1]) {
        j -= 1
    }
    
    arr.swapAt(i, j)
    
    return arr
}

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

Задача: 913. Cat and Mouse
Сложность: hard

В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.

Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

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

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

2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).

3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

class Solution {
    func catMouseGame(_ graph: [[Int]]) -> Int {
        let n = graph.count
        let DRAW = 0, MOUSE = 1, CAT = 2
        var dp = Array(repeating: Array(repeating: Array(repeating: DRAW, count: 2), count: n), count: n)
        var queue = [(Int, Int, Int, Int)]()
        
        for i in 1..<n {
            dp[0][i][0] = MOUSE
            dp[0][i][1] = MOUSE
            dp[i][i][0] = CAT
            dp[i][i][1] = CAT
            queue.append((0, i, 0, MOUSE))
            queue.append((0, i, 1, MOUSE))
            queue.append((i, i, 0, CAT))
            queue.append((i, i, 1, CAT))
        }
        
        func parents(_ mouse: Int, _ cat: Int, _ turn: Int) -> [(Int, Int, Int)] {
            if turn == 1 {
                return graph[mouse].map { ($0, cat, 0) }
            } else {
                return graph[cat].compactMap { $0 > 0 ? (mouse, $0, 1) : nil }
            }
        }
        
        while !queue.isEmpty {
            let (mouse, cat, turn, winner) = queue.removeFirst()
            for (m, c, t) in parents(mouse, cat, turn) {
                if dp[m][c][t] == DRAW {
                    if (t == 0 && winner == MOUSE) || (t == 1 && winner == CAT) {
                        dp[m][c][t] = winner
                        queue.append((m, c, t, winner))
                    } else {
                        let degrees = parents(m, c, t).count
                        if degrees == 0 {
                            dp[m][c][t] = winner
                            queue.append((m, c, t, winner))
                        }
                    }
                }
            }
        }
        
        return dp[1][2][0]
    }
}

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

Задача: 1523. Count Odd Numbers in an Interval Range
Сложность: easy

Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).

Пример:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

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

1⃣Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен.

2⃣Если low нечётное, увеличьте его на 1.

3⃣Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0.

😎 Решение:

class Solution {
    func countOdds(_ low: Int, _ high: Int) -> Int {
        var low = low
        if (low & 1) == 0 {
            low += 1
        }
        return low > high ? 0 : (high - low) / 2 + 1
    }
}

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

Задача: 647. Palindromic Substrings
Сложность: medium

Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "abc"
Output: 3

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

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

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

3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.

😎 Решение:

func countSubstrings(_ s: String) -> Int {
    let sArray = Array(s)
    var totalCount = 0
    
    func expandAroundCenter(_ left: Int, _ right: Int) -> Int {
        var left = left
        var right = right
        var count = 0
        while left >= 0 && right < sArray.count && sArray[left] == sArray[right] {
            count += 1
            left -= 1
            right += 1
        }
        return count
    }
    
    for i in 0..<sArray.count {
        totalCount += expandAroundCenter(i, i)
        totalCount += expandAroundCenter(i, i + 1)
    }
    return totalCount
}

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

Задача: 257. Binary Tree Paths
Сложность: easy

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

Лист — это узел без детей.

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2⃣Начните с корневого узла, пустого пути и пустого списка путей.

3⃣Верните список всех путей от корня до листа.

😎 Решение:

class Solution {
    func construct_paths(_ root: TreeNode?, _ path: String, _ paths: inout [String]) {
        if let root = root {
            var path = path + "\(root.val)"
            if root.left == nil && root.right == nil {
                paths.append(path)
            } else {
                path += "->"
                construct_paths(root.left, path, &paths)
                construct_paths(root.right, path, &paths)
            }
        }
    }

    func binaryTreePaths(_ root: TreeNode?) -> [String] {
        var paths = [String]()
        construct_paths(root, "", &paths)
        return paths
    }
}

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

Задача: 1351. Count Negative Numbers in a Sorted Matrix
Сложность: easy

Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid.

Пример:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

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

1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице.

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

3⃣Вернуть count.

😎 Решение:

class Solution {
    func countNegatives(_ grid: [[Int]]) -> Int {
        var count = 0
        for row in grid {
            for element in row {
                if element < 0 {
                    count += 1
                }
            }
        }
        return count
    }
}

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

Задача: 79. Word Search
Сложность: medium

Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.

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

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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

1⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки.

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

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

😎 Решение:

func exist(_ board: inout [[Character]], _ word: String) -> Bool {
    let rows = board.count
    let cols = board[0].count

    func backtrack(_ row: Int, _ col: Int, _ index: Int) -> Bool {
        if index == word.count { return true }
        if row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word[word.index(word.startIndex, offsetBy: index)] {
            return false
        }
        
        board[row][col] = "#"  
        let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        var result = false
        
        for (rowOffset, colOffset) in directions {
            result = backtrack(row + rowOffset, col + colOffset, index + 1)
            if result { break }
        }
        
        board[row][col] = word[word.index(word.startIndex, offsetBy: index)]  
        return result
    }

    for row in 0..<rows {
        for col in 0..<cols {
            if backtrack(row, col, 0) { return true }
        }
    }
    return false
}

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

Задача: 1256. Encode Number
Сложность: medium

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: num = 23
Output: "1000"

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

1⃣На основе предоставленной таблицы можно выявить закономерность для преобразования целого числа n в строку f(n)

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

3⃣Таким образом, можно вывести, что:
Для каждого значения n > 0, функция f(n) представляет собой двоичное представление числа (n - 1).

😎 Решение:

class Solution {
    func encode(_ num: Int) -> String {
        if num == 0 { return "" }
        return String(num - 1, radix: 2)
    }
}

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

Задача: 274. H-Index
Сложность: medium

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.

Пример:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1⃣Отсортировать массив цитирований по убыванию:
Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива.

2⃣Найти наибольшее значение i, для которого citations[i] > i:
Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i.
Это значение будет индексом, при котором количество цитирований статьи больше индекса.

3⃣Рассчитать h-индекс:
h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге.

😎 Решение:

class Solution {
    func hIndex(_ citations: [Int]) -> Int {
        let n = citations.count
        var papers = [Int](repeating: 0, count: n + 1)
        for c in citations {
            papers[min(n, c)] += 1
        }
        var k = n
        var s = papers[n]
        while k > s {
            k -= 1
            s += papers[k]
        }
        return k
    }
}

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

Задача: 622. Design Circular Queue
Сложность: medium

Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.

Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

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

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

2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу.

3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди.

😎 Решение:

class MyCircularQueue {
    private var queue: [Int]
    private var front: Int
    private var rear: Int
    private var size: Int
    private var capacity: Int

    init(_ k: Int) {
        self.queue = Array(repeating: -1, count: k)
        self.front = 0
        self.rear = -1
        self.size = 0
        self.capacity = k
    }
    
    func enQueue(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        rear = (rear + 1) % capacity
        queue[rear] = value
        size += 1
        return true
    }
    
    func deQueue() -> Bool {
        if isEmpty() {
            return false
        }
        front = (front + 1) % capacity
        size -= 1
        return true
    }
    
    func Front() -> Int {
        return isEmpty() ? -1 : queue[front]
    }
    
    func Rear() -> Int {
        return isEmpty() ? -1 : queue[rear]
    }
    
    func isEmpty() -> Bool {
        return size == 0
    }
    
    func isFull() -> Bool {
        return size == capacity
    }
}

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

Задача: 738. Monotone Increasing Digits
Сложность: medium

Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами.

Пример:

Input: n = 10
Output: 9

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

1⃣Преобразуйте число в строку для удобства обработки.

2⃣Найдите позицию, где последовательность перестает быть монотонной.

3⃣Уменьшите соответствующую цифру и установите все последующие цифры в 9.

😎 Решение:

func monotoneIncreasingDigits(_ n: Int) -> Int {
    var digits = Array(String(n))
    var mark = digits.count
    
    for i in stride(from: digits.count - 1, to: 0, by: -1) {
        if digits[i] < digits[i - 1] {
            mark = i
            digits[i - 1] = Character(String(digits[i - 1].wholeNumberValue! - 1))
        }
    }
    
    for i in mark..<digits.count {
        digits[i] = "9"
    }
    
    return Int(String(digits))!
}

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

Задача: 367. Valid Perfect Square
Сложность: hard

Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае.

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

Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt.

Пример:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

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

1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2.

2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num:
Если guess_squared == num, вернуть True.
Если guess_squared > num, сдвинуть правую границу right = x - 1.
В противном случае сдвинуть левую границу left = x + 1.

3⃣Если вышли из цикла, вернуть False.

😎 Решение:

class Solution {
    func isPerfectSquare(_ num: Int) -> Bool {
        if num < 2 { return true }

        var x = num / 2
        while x * x > num {
            x = (x + num / x) / 2
        }
        return x * x == num
    }
}

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

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

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

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

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

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval {
    var start: Int
    var end: Int
    init(_ start: Int, _ end: Int) {
        self.start = start
        self.end = end
    }
}

func employeeFreeTime(_ schedule: [[Interval]]) -> [Interval] {
    var intervals = [Interval]()
    for employee in schedule {
        intervals.append(contentsOf: employee)
    }
    
    intervals.sort { $0.start < $1.start }
    
    var merged = [Interval]()
    for interval in intervals {
        if merged.isEmpty || merged.last!.end < interval.start {
            merged.append(interval)
        } else {
            merged.last!.end = max(merged.last!.end, interval.end)
        }
    }
    
    var freeTime = [Interval]()
    for i in 1..<merged.count {
        if merged[i].start > merged[i-1].end {
            freeTime.append(Interval(merged[i-1].end, merged[i].start))
        }
    }
    
    return freeTime
}

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

Задача: №43. Multiply Strings
Сложность: medium

При наличии двух неотрицательных целых чисел num1 и num2, представленных в виде строк, вернуть произведение num1 и num2, также представленное в виде строки.
Примечание: Нельзя использовать встроенные библиотеки BigInteger или напрямую преобразовывать входные данные в integer.

Пример:

Input: num1 = "123", num2 = "456"  
Output: "56088"  

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

1⃣Преобразовать строки в массивы цифр в перевернутом порядке.

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

3⃣Преобразовать результат обратно в строку, удаляя ведущие нули.

😎 Решение:

class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        guard num1 != "0", num2 != "0" else { return "0" }
        
        let n1 = num1.map { Int(String($0))! }.reversed()
        let n2 = num2.map { Int(String($0))! }.reversed()
        var res = Array(repeating: 0, count: num1.count + num2.count)
        
        for i in 0..<n1.count {
            for j in 0..<n2.count {
                res[i + j] += n1[i] * n2[j]
                res[i + j + 1] += res[i + j] / 10
                res[i + j] %= 10
            }
        }
        
        while res.count > 1, res.last == 0 {
            res.removeLast()
        }
        
        return res.reversed().map(String.init).joined()
    }
}

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

Задача: 129. Sum Root to Leaf Numbers
Сложность: Medium

Вам дан корень бинарного дерева, содержащего только цифры от 0 до 9.

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

Например, путь от корня до листа 1 -> 2 -> 3 представляет число 123.
Верните общую сумму всех чисел от корня до листа. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Листовой узел — это узел без детей.

Пример:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

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

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

2⃣Обход дерева:
Используйте стек для глубинного обхода дерева (DFS), обновляя currNumber путём умножения на 10 и добавления значения узла. Для каждого листа добавляйте currNumber к rootToLeaf.

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

😎 Решение:

class Solution {
    func sumNumbers(_ root: TreeNode?) -> Int {
        var rootToLeaf = 0, currNumber = 0
        var stack: [(TreeNode?, Int)] = []
        stack.append((root, 0))
        
        while !stack.isEmpty {
            let p = stack.removeLast()
            let node = p.0
            currNumber = p.1
            
            if let root = node {
                currNumber = currNumber * 10 + root.val
              
                if root.left == nil && root.right == nil {
                    rootToLeaf += currNumber
                } else {
                    if let right = root.right {
                        stack.append((right, currNumber))
                    }
                    if let left = root.left {
                        stack.append((left, currNumber))
                    }
                }
            }
        }
        return rootToLeaf
    }
}

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

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

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

Задача: 269. Alien Dictionary
Сложность: hard

Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.

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

Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".

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

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

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

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

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

import Foundation

class Solution {
    func alienOrder(_ words: [String]) -> String {
        var adjList = [Character: Set<Character>]()
        var inDegree = [Character: Int]()
        
        for word in words {
            for char in word {
                inDegree[char] = 0
            }
        }
        
        for (firstWord, secondWord) in zip(words, words.dropFirst()) {
            for (c, d) in zip(firstWord, secondWord) {
                if c != d {
                    if !adjList[c, default: []].contains(d) {
                        adjList[c, default: []].insert(d)
                        inDegree[d, default: 0] += 1
                    }
                    break
                }
            }
            if secondWord.count < firstWord.count && firstWord.hasPrefix(secondWord) {
                return ""
            }
        }
        
        var output = [Character]()
        var queue = [Character]()
        
        for (char, degree) in inDegree where degree == 0 {
            queue.append(char)
        }
        
        while !queue.isEmpty {
            let c = queue.removeFirst()
            output.append(c)
            for d in adjList[c] ?? [] {
                inDegree[d]! -= 1
                if inDegree[d] == 0 {
                    queue.append(d)
                }
            }
        }
        
        if output.count < inDegree.count {
            return ""
        }
        
        return String(output)
    }
}

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

Задача: 119. Pascal's Triangle ll
Сложность: easy

Для данного целого числа rowIndex верните rowIndex-ю строку (с индексацией с нуля) треугольника Паскаля.

Пример:

Input: rowIndex = 3
Output: [1,3,3,1]

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

1⃣Давайте представим, что у нас есть функция getNum(rowIndex, colIndex), которая дает нам число с индексом colIndex в строке с индексом rowIndex. Мы могли бы просто построить k-ю строку, повторно вызывая getNum(...) для столбцов от 0 до k.

2⃣Мы можем сформулировать нашу интуицию в следующую рекурсию:

getNum(rowIndex, colIndex) = getNum(rowIndex - 1, colIndex - 1) + getNum(rowIndex - 1, colIndex)

3⃣Рекурсия заканчивается в некоторых известных базовых случаях:

Первая строка - это просто одинокая 1, то есть getNum(0, ...) = 1

Первое и последнее число каждой строки равно 1, то есть getNum(k, 0) = getNum(k, k) = 1

😎 Решение:

class Solution {
    func getNum(_ row: Int, _ col: Int) -> Int {
        if row == 0 col==0 row == col {
            return 1
        }
        return getNum(row - 1, col - 1) + getNum(row - 1, col)
    }

    func getRow(_ rowIndex: Int) -> [Int] {
        var ans = [Int]()
        for i in 0...rowIndex {
            ans.append(getNum(rowIndex, i))
        }
        return ans
    }
}

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

Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard

Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.

Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.

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

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

Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

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

1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.

2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.

3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.

😎 Решение:

class Solution {
    var memo: [[Int]] = []
    var done: Int = 0
    var n: Int = 0
    let MOD = 1000000007
    var hatsToPeople: [Int: [Int]] = [:]

    func numberWays(_ hats: [[Int]]) -> Int {
        n = hats.count
        for (i, hatList) in hats.enumerated() {
            for hat in hatList {
                hatsToPeople[hat, default: []].append(i)
            }
        }
        done = (1 << n) - 1
        memo = Array(repeating: Array(repeating: -1, count: done), count: 41)
        return dp(1, 0)
    }

    private func dp(_ hat: Int, _ mask: Int) -> Int {
        if mask == done { return 1 }
        if hat > 40 { return 0 }
        if memo[hat][mask] != -1 { return memo[hat][mask] }
        
        var ans = dp(hat + 1, mask)
        if let people = hatsToPeople[hat] {
            for person in people {
                if (mask & (1 << person)) == 0 {
                    ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD
                }
            }
        }
        memo[hat][mask] = ans
        return ans
    }
}

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