Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

Даны три целочисленных массива arr1, arr2 и arr3, отсортированных в строго возрастающем порядке. Верните отсортированный массив, содержащий только те целые числа, которые присутствуют во всех трех массивах.

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

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

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

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

😎 Решение:

class Solution {
    func arraysIntersection(_ arr1: [Int], _ arr2: [Int], _ arr3: [Int]) -> [Int] {
        var counter = [Int: Int]()
        for e in arr1 {
            counter[e, default: 0] += 1
        }
        for e in arr2 {
            counter[e, default: 0] += 1
        }
        for e in arr3 {
            counter[e, default: 0] += 1
        }

        var ans = [Int]()
        for (key, value) in counter where value == 3 {
            ans.append(key)
        }

        return ans
    }
}

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

Задача: 1275. Find Winner on a Tic Tac Toe Game
Сложность: easy

В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные.
Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым.

Пример:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

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

1⃣Инициализируйте пустую 3x3 сетку.

2⃣Пройдите по списку ходов и обновите сетку в соответствии с ходами игроков A и B.

3⃣После каждого хода проверяйте, есть ли победитель. Если все ходы сделаны и нет победителя, проверьте, завершена ли игра вничью или еще есть ходы.

😎 Решение:

class Solution {
    func tictactoe(_ moves: [[Int]]) -> String {
        var grid = Array(repeating: Array(repeating: "", count: 3), count: 3)
        for (i, move) in moves.enumerated() {
            grid[move[0]][move[1]] = i % 2 == 0 ? "X" : "O"
        }

        for i in 0..<3 {
            if grid[i][0] == grid[i][1] && grid[i][1] == grid[i][2] && grid[i][0] != "" {
                return grid[i][0] == "X" ? "A" : "B"
            }
            if grid[0][i] == grid[1][i] && grid[1][i] == grid[2][i] && grid[0][i] != "" {
                return grid[0][i] == "X" ? "A" : "B"
            }
        }

        if grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2] && grid[0][0] != "" {
            return grid[0][0] == "X" ? "A" : "B"
        }
        if grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0] && grid[0][2] != "" {
            return grid[0][2] == "X" ? "A" : "B"
        }

        return moves.count == 9 ? "Draw" : "Pending"
    }
}

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

Задача: 126.Word Ladder II
Сложность: Hard

Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:

Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

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

1⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS).

2⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList.

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

😎 Решение:

class Solution {
    var adjList = [String: [String]]()
    var shortestPaths = [[String]]()

    func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [[String]] {
        var wordSet = Set(wordList), queue = [beginWord]
        var isEnqueued = [beginWord: true]
        while !queue.isEmpty {
            var visited = [String]()
            for currWord in queue {
                queue.removeFirst()
                for i in 0..<currWord.count {
                    var wordArray = Array(currWord)
                    let oldChar = wordArray[i]
                    for c in Character("a").asciiValue!...Character("z").asciiValue! {
                        wordArray[i] = Character(UnicodeScalar(c))
                        let newWord = String(wordArray)
                        if newWord == currWord || !wordSet.contains(newWord) { continue }
                        visited.append(newWord)
                        adjList[newWord, default: []].append(currWord)
                        if !isEnqueued[newWord, default: false] {
                            queue.append(newWord)
                            isEnqueued[newWord] = true
                        }
                    }
                    wordArray[i] = oldChar
                }
            }
            visited.forEach { wordSet.remove($0) }
        }
        
        func backtrack(_ path: [String], _ word: String) {
            if word == endWord {
                shortestPaths.append(path.reversed())
                return
            }
            for neighbor in adjList[word, default: []] {
                backtrack(path + [neighbor], neighbor)
            }
        }
        
        backtrack([beginWord], beginWord)
        return shortestPaths
    }
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 326. Power of Three
Сложность: easy

Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.

Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Проверка начального значения
Если n меньше или равно нулю, вернуть false, так как степени тройки всегда положительны.

2⃣Цикл деления на 3
Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3.

3⃣Проверка конечного значения
Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false.

😎 Решение:

class Solution {
    func isPowerOfThree(_ n: Int) -> Bool {
        if n <= 0 {
            return false
        }
        var num = n
        while num % 3 == 0 {
            num /= 3
        }
        return num == 1
    }
}

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

Задача: 83. Remove Duplicates from Sorted List
Сложность: easy

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

Пример:

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

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

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

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

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

😎 Решение:

func deleteDuplicates(_ head: ListNode?) -> ListNode? {
    var current = head
    while current != nil && current?.next != nil {
        if current?.next?.val == current?.val {
            current?.next = current?.next?.next
        } else {
            current = current?.next
        }
    }
    return head
}

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

Задача: 503. Next Greater Element II
Сложность: medium

Дан циклический массив целых чисел nums (т.е. следующий элемент после nums[nums.length - 1] это nums[0]), верните следующее большее число для каждого элемента в nums.

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

Пример:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

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

1⃣Инициализация
Создайте массив res той же длины, что и nums, и заполните его значениями -1.

2⃣Поиск следующего большего элемента
Для каждого элемента nums[i], используя индекс j, ищите следующий больший элемент среди следующих (циклически) n-1 элементов. Если найден больший элемент, обновите res[i] и прервите внутренний цикл.

3⃣Возврат результата
Верните массив res.

😎 Решение:

class Solution {
    func nextGreaterElements(_ nums: [Int]) -> [Int] {
        let n = nums.count
        var res = [Int](repeating: -1, count: n)
        
        for i in 0..<n {
            for j in 1..<n {
                if nums[(i + j) % n] > nums[i] {
                    res[i] = nums[(i + j) % n]
                    break
                }
            }
        }
        
        return res
    }
}

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

Задача: 200. Number of Islands
Сложность: medium

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

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

Пример:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

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

1⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS).

2⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый.

3⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.

😎 Решение:

class Solution {
    func dfs(_ grid: inout [[Character]], _ r: Int, _ c: Int) {
        let nr = grid.count
        let nc = grid[0].count

        if r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == "0" {
            return
        }

        grid[r][c] = "0"
        dfs(&grid, r - 1, c)
        dfs(&grid, r + 1, c)
        dfs(&grid, r, c - 1)
        dfs(&grid, r, c + 1)
    }

    func numIslands(_ grid: [[Character]]) -> Int {
        var grid = grid
        if grid.isEmpty {
            return 0
        }

        let nr = grid.count
        let nc = grid[0].count
        var numIslands = 0

        for r in 0..<nr {
            for c in 0..<nc {
                if grid[r][c] == "1" {
                    numIslands += 1
                    dfs(&grid, r, c)
                }
            }
        }

        return numIslands
    }
}

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

Задача: 508. Most Frequent Subtree Sum
Сложность: medium

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

Сумма поддерева узла определяется как сумма всех значений узлов, образованных поддеревом, укорененным в этом узле (включая сам узел).

Пример:

Input: root = [5,2,-3]
Output: [2,-3,4]

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

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

2⃣Обход дерева и вычисление сумм
Выполните обход дерева в порядке post-order. Используйте суммы поддеревьев левого и правого дочерних узлов для вычисления суммы текущего поддерева. Увеличьте частоту текущей суммы в sumFreq. Обновите maxFreq, если частота текущей суммы больше текущего maxFreq.

3⃣Сборка результата
Пройдитесь по sumFreq и добавьте все суммы с частотой, равной maxFreq, в массив maxFreqSums. Верните массив maxFreqSums.

😎 Решение:

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

class Solution {
    private var sumFreq = [Int: Int]()
    private var maxFreq = 0
    
    private func subtreeSum(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        let leftSum = subtreeSum(root.left)
        let rightSum = subtreeSum(root.right)
        let currSum = root.val + leftSum + rightSum
        sumFreq[currSum, default: 0] += 1
        maxFreq = max(maxFreq, sumFreq[currSum]!)
        return currSum
    }
    
    func findFrequentTreeSum(_ root: TreeNode?) -> [Int] {
        _ = subtreeSum(root)
        return sumFreq.filter { $0.value == maxFreq }.map { $0.key }
    }
}

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

Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.

Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.

Пример:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

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

1⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.

2⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.

3⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.

😎 Решение:

class TrieNode {
    var links = [TrieNode?](repeating: nil, count: 26)
    var isEnd = false

    func containsKey(_ ch: Character) -> Bool {
        return links[Int(ch.asciiValue! - Character("a").asciiValue!)] != nil
    }

    func get(_ ch: Character) -> TrieNode? {
        return links[Int(ch.asciiValue! - Character("a").asciiValue!)]
    }

    func put(_ ch: Character, _ node: TrieNode) {
        links[Int(ch.asciiValue! - Character("a").asciiValue!)] = node
    }

    func setEnd() {
        isEnd = true
    }
}

class Trie {
    private var root = TrieNode()

    func insert(_ word: String) {
        var node = root
        for ch in word {
            if !node.containsKey(ch) {
                node.put(ch, TrieNode())
            }
            node = node.get(ch)!
        }
        node.setEnd()
    }

    private func searchPrefix(_ word: String) -> TrieNode? {
        var node = root
        for ch in word {
            if node.containsKey(ch) {
                node = node.get(ch)!
            } else {
                return nil
            }
        }
        return node
    }

    func search(_ word: String) -> Bool {
        if let node = searchPrefix(word) {
            return node.isEnd
        }
        return false
    }

    func startsWith(_ prefix: String) -> Bool {
        return searchPrefix(prefix) != nil
    }
}

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

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

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

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

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

😎 Решение:

class Solution {
    func beautifulArray(_ n: Int) -> [Int] {
        func construct(_ n: Int) -> [Int] {
            if n == 1 {
                return [1]
            }
            let odd = construct((n + 1) / 2).map { 2 * $0 - 1 }
            let even = construct(n / 2).map { 2 * $0 }
            return odd + even
        }
        return construct(n)
    }
}

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

Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy

Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.

Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

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

1⃣Создать словарь для подсчета частоты каждого числа в массиве deck.

2⃣Найти наибольший общий делитель (НОД) всех частот.

3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы.

😎 Решение:

class Solution {
    func hasGroupsSizeX(_ deck: [Int]) -> Bool {
        let count = deck.reduce(into: [:]) { counts, num in
            counts[num, default: 0] += 1
        }
        let freqValues = Array(count.values)
        let g = freqValues.reduce(freqValues[0], gcd)
        return g > 1
    }
    
    private func gcd(_ a: Int, _ b: Int) -> Int {
        var a = a, b = b
        while b != 0 {
            let temp = a % b
            a = b
            b = temp
        }
        return a
    }
}

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

Задача: 218. The Skyline Problem
Сложность: hard

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

Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:

lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.

Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

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

1⃣Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights.

2⃣Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex).

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

😎 Решение:

class Solution {
    func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
        var edgeSet = Set<Int>()
        for building in buildings {
            edgeSet.insert(building[0])
            edgeSet.insert(building[1])
        }
        let edges = Array(edgeSet).sorted()
        var edgeIndexMap = [Int: Int]()
        for i in 0..<edges.count {
            edgeIndexMap[edges[i]] = i
        }
        var heights = [Int](repeating: 0, count: edges.count)
        for building in buildings {
            let left = building[0], right = building[1], height = building[2]
            let leftIndex = edgeIndexMap[left]!, rightIndex = edgeIndexMap[right]!
            for idx in leftIndex..<rightIndex {
                heights[idx] = max(heights[idx], height)
            }
        }
        var answer = [[Int]]()
        for i in 0..<heights.count {
            let currHeight = heights[i], currPos = edges[i]
            if answer.isEmpty || answer.last![1] != currHeight {
                answer.append([currPos, currHeight])
            }
        }
        return answer
    }
}

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

Задача: 322. Coin Change
Сложность: medium

Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

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

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

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

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

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        return coinChange(0, coins, amount)
    }

    private func coinChange(_ idxCoin: Int, _ coins: [Int], _ amount: Int) -> Int {
        if amount == 0 {
            return 0
        }
        if idxCoin < coins.count && amount > 0 {
            let maxVal = amount / coins[idxCoin]
            var minCost = Int.max
            for x in 0...maxVal {
                if amount >= x * coins[idxCoin] {
                    let res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin])
                    if res != -1 {
                        minCost = min(minCost, res + x)
                    }
                }
            }
            return minCost == Int.max ? -1 : minCost
        }
        return -1
    }
}

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

Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed
Сложность: hard

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

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

RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.
bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.
bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.
int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.
Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.

Пример:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

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

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

2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае.
Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае.

3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента.

😎 Решение:

class RandomizedCollection {
    private var dict: [Int: Set<Int>]
    private var list: [Int]

    init() {
        dict = [Int: Set<Int>]()
        list = [Int]()
    }

    func insert(_ val: Int) -> Bool {
        let exists = dict[val] != nil
        if !exists {
            dict[val] = Set<Int>()
        }
        dict[val]?.insert(list.count)
        list.append(val)
        return !exists
    }

    func remove(_ val: Int) -> Bool {
        guard let indices = dict[val], !indices.isEmpty else {
            return false
        }
        let index = indices.first!
        dict[val]?.remove(index)
        let lastElement = list.removeLast()
        if index < list.count {
            list[index] = lastElement
            dict[lastElement]?.remove(list.count)
            dict[lastElement]?.insert(index)
        }
        if dict[val]?.isEmpty ?? false {
            dict[val] = nil
        }
        return true
    }

    func getRandom() -> Int {
        return list.randomElement()!
    }
}

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

Задача: 1474. Delete N Nodes After M Nodes of a Linked List
Сложность: easy

Вам дано начало связанного списка и два целых числа m и n.

Пройдите по связанному списку и удалите некоторые узлы следующим образом:
Начните с головы как текущего узла.
Сохраните первые m узлов, начиная с текущего узла.
Удалите следующие n узлов.
Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.
Верните голову изменённого списка после удаления указанных узлов.

Пример:

Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List  (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.

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

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

2⃣Итерация по списку:
Итеративно удаляйте n узлов после m узлов, продолжая до конца списка.
Проходите m узлов, обновляя lastMNode на текущий узел. После m итераций lastMNode указывает на m-й узел.
Продолжайте итерацию по n узлам.

3⃣Удаление узлов:
Чтобы удалить n узлов, измените указатель next у lastMNode, чтобы он указывал на currentNode после пропуска n узлов.

😎 Решение:

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

class Solution {
    func deleteNodes(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
        var currentNode = head
        var lastMNode = head

        while currentNode != nil {
            var mCount = m
            var nCount = n

            while currentNode != nil && mCount > 0 {
                lastMNode = currentNode
                currentNode = currentNode?.next
                mCount -= 1
            }

            while currentNode != nil && nCount > 0 {
                currentNode = currentNode?.next
                nCount -= 1
            }

            lastMNode?.next = currentNode
        }
        return head
    }
}

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

Задача: 1266. Minimum Time Visiting All Points
Сложность: easy

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7

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

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

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

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

😎 Решение:

class Solution {
    func minTimeToVisitAllPoints(_ points: [[Int]]) -> Int {
        var time = 0
        for i in 0..<points.count - 1 {
            time += distance(points[i], points[i + 1])
        }
        return time
    }

    private func distance(_ p1: [Int], _ p2: [Int]) -> Int {
        return max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))
    }
}

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

Задача: 779. K-th Symbol in Grammar
Сложность: medium

Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10.

Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110.
Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк.

Пример:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

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

1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal.

2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal).

3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal).

😎 Решение:

class Solution {
    func depthFirstSearch(_ n: Int, _ k: Int, _ rootVal: Int) -> Int {
        if n == 1 {
            return rootVal
        }
        let totalNodes = 1 << (n - 1)
        if k > totalNodes / 2 {
            let nextRootVal = rootVal == 0 ? 1 : 0
            return depthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal)
        } else {
            let nextRootVal = rootVal == 0 ? 0 : 1
            return depthFirstSearch(n - 1, k, nextRootVal)
        }
    }

    func kthGrammar(_ n: Int, _ k: Int) -> Int {
        return depthFirstSearch(n, k, 0)
    }
}

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

Задача: 345. Reverse Vowels of a String
Сложность: easy

Дана строка s, переверните только все гласные в строке и верните её.

Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры.

Пример:

Input: s = "hello"
Output: "holle"

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

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

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

3⃣Завершение работы:
Когда указатели пересекутся, остановите процесс и верните строку.

😎 Решение:

class Solution {
    func reverseVowels(_ s: String) -> String {
        var s = Array(s)
        let vowels = Set("aeiouAEIOU")
        var left = 0, right = s.count - 1
        
        while left < right {
            if !vowels.contains(s[left]) {
                left += 1
            } else if !vowels.contains(s[right]) {
                right -= 1
            } else {
                s.swapAt(left, right)
                left += 1
                right -= 1
            }
        }
        
        return String(s)
    }
}

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

Задача: 102. Binary Tree Level Order Traversal
Сложность: medium

Дан корень бинарного дерева. Верните обход узлов дерева по уровням (то есть слева направо, уровень за уровнем).

Пример:

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

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

1⃣Самый простой способ решения задачи — использование рекурсии. Сначала убедимся, что дерево не пустое, а затем рекурсивно вызовем функцию helper(node, level), которая принимает текущий узел и его уровень в качестве аргументов.

2⃣Эта функция выполняет следующее:

Выходной список здесь называется levels, и, таким образом, текущий уровень — это просто длина этого списка len(levels). Сравниваем номер текущего уровня len(levels) с уровнем узла level. Если вы все еще на предыдущем уровне, добавьте новый, добавив новый список в levels.

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

Рекурсивно обработайте дочерние узлы, если они не равны None: helper(node.left / node.right, level + 1).

😎 Решение:

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 {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        var levels: [[Int]] = []
        if root == nil {
            return levels
        }

        func helper(_ node: TreeNode?, _ level: Int) {
            guard let node = node else { return }
            if level == levels.count {
                levels.append([Int]())
            }

            levels[level].append(node.val)

            helper(node.left, level + 1)
            helper(node.right, level + 1)
        }

        helper(root, 0)
        return levels
    }
}

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

Задача: 1023. Camelcase Matching
Сложность: medium

Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.

Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

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

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

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

3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.

😎 Решение:

class Solution {
    func camelMatch(_ queries: [String], _ pattern: String) -> [Bool] {
        func matches(_ query: String, _ pattern: String) -> Bool {
            var i = 0, j = 0
            let queryArray = Array(query), patternArray = Array(pattern)
            
            while i < queryArray.count {
                if j < patternArray.count && queryArray[i] == patternArray[j] {
                    j += 1
                } else if queryArray[i].isUppercase {
                    return false
                }
                i += 1
            }
            return j == patternArray.count
        }
        
        return queries.map { matches($0, pattern) }
    }
}

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