#medium
Задача: 250. Count Univalue Subtrees

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

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

Пример:

Input: root = [5,1,5,5,5,null,5]
Output: 4

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

1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.

2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, верните true.
Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false.

3️⃣Верните count.

😎 Решение:

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 {
    var count = 0
    
    func dfs(_ node: TreeNode?) -> Bool {
        guard let node = node else {
            return true
        }
        
        let isLeftUniValue = dfs(node.left)
        let isRightUniValue = dfs(node.right)
        
        if isLeftUniValue && isRightUniValue {
            if let left = node.left, left.val != node.val {
                return false
            }
            if let right = node.right, right.val != node.val {
                return false
            }
            count += 1
            return true
        }
        return false
    }
    
    func countUnivalSubtrees(_ root: TreeNode?) -> Int {
        dfs(root)
        return count
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 251. Flatten 2D Vector

Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.

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

Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.

Пример:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

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

1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента.

2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.

3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().

😎 Решение:

class Vector2D {
    private var nums: [Int]
    private var position: Int
    
    init(_ v: [[Int]]) {
        nums = v.flatMap { $0 }
        position = -1
    }
    
    func next() -> Int {
        position += 1
        return nums[position]
    }
    
    func hasNext() -> Bool {
        return position + 1 < nums.count
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 268. Missing Number

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1️⃣Сначала отсортируйте массив nums.

2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число.

😎 Решение:

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        let sortedNums = nums.sorted()
        if sortedNums.last != sortedNums.count {
            return sortedNums.count
        } else if sortedNums.first != 0 {
            return 0
        }
        for i in 1..<sortedNums.count {
            let expectedNum = sortedNums[i - 1] + 1
            if sortedNums[i] != expectedNum {
                return expectedNum
            }
        }
        return -1
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 269. Alien Dictionary

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

Вам дан список строк 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)
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 270. Closest Binary Search Tree Value

Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.

Пример:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

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

1️⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2️⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

3️⃣Выбрать наименьший из ближайших элементов:
Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них.

😎 Решение:

class Solution {
    func closestValue(_ root: TreeNode?, _ target: Double) -> Int {
        var closest = root!.val
        var node = root
        while node != nil {
            if abs(Double(node!.val) - target) < abs(Double(closest) - target) {
                closest = node!.val
            } else if abs(Double(node!.val) - target) == abs(Double(closest) - target) {
                closest = min(node!.val, closest)
            }
            node = target < Double(node!.val) ? node!.left : node!.right
        }
        return closest
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 272. Closest Binary Search Tree Value II

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

Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.

Пример:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

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

1️⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив:
Пройти по дереву в глубину, добавляя каждое значение узла в массив.

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

3️⃣Вернуть первые k значений из отсортированного массива:
Извлечь первые k элементов из отсортированного массива и вернуть их.

😎 Решение:

class Solution {
    func closestKValues(_ root: TreeNode?, _ target: Double, _ k: Int) -> [Int] {
        var arr = [Int]()
        dfs(root, &arr)
        arr.sort { abs(Double($0) - target) < abs(Double($1) - target) }
        return Array(arr.prefix(k))
    }
    
    private func dfs(_ node: TreeNode?, _ arr: inout [Int]) {
        guard let node = node else { return }
        arr.append(node.val)
        dfs(node.left, &arr)
        dfs(node.right, &arr)
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 214. Shortest Palindrome

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 273. Integer to English Words

Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

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

1️⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

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

3️⃣Формирование окончательного результата:
Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды).
Соединить все части в одну строку, удалив лишние пробелы.

😎 Решение:

class Solution {
    private let belowTwenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
    private let tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
    private let thousands = ["", "Thousand", "Million", "Billion"]
    
    func numberToWords(_ num: Int) -> String {
        if num == 0 { return "Zero" }
        var num = num
        var result = ""
        var i = 0
        
        while num > 0 {
            if num % 1000 != 0 {
                result = helper(num % 1000) + thousands[i] + " " + result
            }
            num /= 1000
            i += 1
        }
        return result.trimmingCharacters(in: .whitespaces)
    }
    
    private func helper(_ num: Int) -> String {
        if num == 0 { return "" }
        else if num < 20 { return belowTwenty[num] + " " }
        else if num < 100 { return tens[num / 10] + " " + helper(num % 10) }
        else { return belowTwenty[num / 100] + " Hundred " + helper(num % 100) }
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 215. Kth Largest Element in an Array

Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.

Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.

Пример:

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

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

1️⃣ Отсортируйте массив в порядке убывания:
Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее.

2️⃣ Найдите k-й по величине элемент:
После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0).

3️⃣ Верните результат:
Возвратите найденное значение как результат.

😎 Решение:

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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 216. Combination Sum III

Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:

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

Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

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

1️⃣ Инициализация и запуск рекурсивной функции:
Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов.
Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов.
Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов.

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

3️⃣ Возвращение результатов:
По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций.

😎 Решение:

class Solution {
    func backtrack(_ remain: Int, _ k: Int, _ comb: inout [Int], _ nextStart: Int, _ results: inout [[Int]]) {
        if remain == 0 && comb.count == k {
            results.append(comb)
            return
        } else if remain < 0 || comb.count == k {
            return
        }

        for i in nextStart..<9 {
            comb.append(i + 1)
            backtrack(remain - i - 1, k, &comb, i + 1, &results)
            comb.removeLast()
        }
    }

    func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
        var results = [[Int]]()
        var comb = [Int]()
        backtrack(n, k, &comb, 0, &results)
        return results
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 274. H-Index

Дан массив целых чисел 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
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 275. H-Index II

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

Пример:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 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[0: mid - 1] и citations[mid + 1: n].

2️⃣Сравнить количество статей с цитированиями больше или равными citations[mid]:
Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.
Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].
Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3️⃣Возвращение результата:
Продолжать процесс, пока не будет найден h-индекс.
Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎 Решение:

class Solution {
    func hIndex(_ citations: [Int]) -> Int {
        let n = citations.count
        var left = 0
        var right = n - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            if citations[mid] == n - mid {
                return n - mid
            } else if citations[mid] < n - mid {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return n - left
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 217. Contains Duplicate

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

Пример:

Input: nums = [1,2,3,4]
Output: false

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

1️⃣ Отсортируйте массив nums по возрастанию.

2️⃣ Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим.

3️⃣ Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false.

😎 Решение:

func containsDuplicate(_ nums: [Int]) -> Bool {
    let sortedNums = nums.sorted()
    for i in 0..<sortedNums.count - 1 {
        if sortedNums[i] == sortedNums[i + 1] {
            return true
        }
    }
    return false
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 276. Paint Fence

Вы красите забор из n столбцов, используя k различных цветов. Вы должны красить столбы, следуя этим правилам:
Каждый столб должен быть окрашен в один цвет.
Не может быть трех или более подряд идущих столбцов одного цвета.
Учитывая два целых числа n и k, верните количество способов покрасить забор.

Пример:

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

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

1️⃣Инициализация и определение вспомогательной функции:
Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов.
Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов.

2️⃣Реализация базы и проверка кэша:
В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2.
Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i].

3️⃣Расчет с использованием рекуррентного соотношения:
В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его.
Вызвать и вернуть totalWays(n).

😎 Решение:

class Solution {
    func numWays(_ n: Int, _ k: Int) -> Int {
        if n == 1 {
            return k
        }
        
        var twoPostsBack = k
        var onePostBack = k * k
        
        for _ in 3...n {
            let curr = (k - 1) * (onePostBack + twoPostsBack)
            twoPostsBack = onePostBack
            onePostBack = curr
        }
        
        return onePostBack
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 218. The Skyline Problem

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

Геометрическая информация о каждом здании задана в массиве 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
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 219. Contains Duplicate II

Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k.

Пример:

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

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

1️⃣ Создайте пустое множество set.

2️⃣ Пройдитесь по массиву nums:
Если текущий элемент уже есть в множестве, верните true.
Добавьте текущий элемент в множество.
Если размер множества больше k, удалите элемент, который был добавлен k шагов назад.

3️⃣ Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false.

😎 Решение:

class Solution {
    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
        var set = Set<Int>()
        for i in 0..<nums.count {
            if set.contains(nums[i]) {
                return true
            }
            set.insert(nums[i])
            if set.count > k {
                set.remove(nums[i - k])
            }
        }
        return false
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 314. Binary Tree Vertical Order Traversal

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

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

Пример:

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

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

1️⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2️⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

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

😎 Решение:

class Solution {
    func verticalOrder(_ root: TreeNode?) -> [[Int]] {
        var output = [[Int]]()
        guard let root = root else {
            return output
        }

        var columnTable = [Int: [Int]]()
        var queue: [(TreeNode, Int)] = [(root, 0)]

        while !queue.isEmpty {
            let (node, column) = queue.removeFirst()

            if columnTable[column] == nil {
                columnTable[column] = [Int]()
            }
            columnTable[column]?.append(node.val)

            if let left = node.left {
                queue.append((left, column - 1))
            }
            if let right = node.right {
                queue.append((right, column + 1))
            }
        }

        let sortedKeys = columnTable.keys.sorted()
        for key in sortedKeys {
            if let values = columnTable[key] {
                output.append(values)
            }
        }

        return output
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 315. Count of Smaller Numbers After Self

Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].

Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

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

1️⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.

2️⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте число на num + offset.
Запросите количество элементов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.

3️⃣Верните результат.

😎 Решение:

class Solution {
    func countSmaller(_ nums: [Int]) -> [Int] {
        let offset = 10000 
        let size = 2 * 10000 + 1
        var tree = [Int](repeating: 0, count: size * 2)
        var result = [Int]()
        
        for num in nums.reversed() {
            let smallerCount = query(0, num + offset, tree, size)
            result.append(smallerCount)
            update(num + offset, 1, tree, size)
        }
        
        return result.reversed()
    }

    private func update(_ index: Int, _ value: Int, _ tree: inout [Int], _ size: Int) {
        var idx = index + size
        tree[idx] += value
        while idx > 1 {
            idx /= 2
            tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]
        }
    }

    private func query(_ left: Int, _ right: Int, _ tree: [Int], _ size: Int) -> Int {
        var result = 0
        var l = left + size 
        var r = right + size
        while l < r {
            if l % 2 == 1 {
                result += tree[l]
                l += 1
            }
            l /= 2
            if r % 2 == 1 {
                r -= 1
                result += tree[r]
            }
            r /= 2
        }
        return result
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 220. Contains Duplicate III

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

Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.

Верните true, если такая пара существует, или false в противном случае.

Пример:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

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

1️⃣ Инициализация и вычисление корзин:
Рассчитать ширину корзины w = t + 1.
Инициализировать пустой хэш-таблицей buckets.
Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w.

2️⃣ Итерация и проверка корзин:
Перебрать все элементы массива nums.
Для каждого элемента nums[i]:
Определить его корзину с помощью getID.
Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true.
Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true.
Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину.
Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна.

3️⃣ Завершение:
Если ни одна пара "почти дубликатов" не найдена, вернуть false.

😎 Решение:

class Solution {
    func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
        if t < 0 { return false }
        var buckets = [Int: Int]()
        let w = t + 1

        for i in 0..<nums.count {
            let bucket = nums[i] < 0 ? (nums[i] + 1) / w - 1 : nums[i] / w
            if buckets[bucket] != nil { return true }
            if let val = buckets[bucket - 1], abs(nums[i] - val) < w { return true }
            if let val = buckets[bucket + 1], abs(nums[i] - val) < w { return true }
            buckets[bucket] = nums[i]
            if i >= k {
                buckets.removeValue(forKey: nums[i - k] < 0 ? (nums[i - k] + 1) / w - 1 : nums[i - k] / w)
            }
        }
        return false
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 221. Maximal Square

Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

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

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

2️⃣ Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.

3️⃣ По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата.

😎 Решение:

class Solution {
    func maximalSquare(_ matrix: [[Character]]) -> Int {
        let rows = matrix.count
        let cols = rows > 0 ? matrix[0].count : 0
        var dp = [Int](repeating: 0, count: cols + 1)
        var maxsqlen = 0
        var prev = 0
        
        for i in 1...rows {
            for j in 1...cols {
                let temp = dp[j]
                if matrix[i - 1][j - 1] == "1" {
                    dp[j] = min(dp[j - 1], min(prev, dp[j])) + 1
                    maxsqlen = max(maxsqlen, dp[j])
                } else {
                    dp[j] = 0
                }
                prev = temp
            }
        }
        
        return maxsqlen * maxsqlen
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
🤔 Задача: 222. Count Complete Tree Nodes

Учитывая корень полного двоичного дерева, верните количество узлов в дереве.
Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n. Разработайте алгоритм, который выполняется за время, меньшее, чем O(n).

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

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

1⃣Инициализация и проверка пустоты дерева
Если дерево пустое, вернуть 0.
Рассчитать глубину дерева d.

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

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

😎 Решение:

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 {
    func computeDepth(_ node: TreeNode?) -> Int {
        var d = 0
        var node = node
        while node?.left != nil {
            node = node?.left
            d += 1
        }
        return d
    }

    func exists(_ idx: Int, _ d: Int, _ node: TreeNode?) -> Bool {
        var left = 0
        var right = Int(pow(2.0, Double(d))) - 1
        var node = node
        for _ in 0..<d {
            let pivot = left + (right - left) / 2
            if idx <= pivot {
                node = node?.left
                right = pivot
            } else {
                node = node?.right
                left = pivot + 1
            }
        }
        return node != nil
    }

    func countNodes(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }

        let d = computeDepth(root)
        if d == 0 { return 1 }

        var left = 1
        var right = Int(pow(2.0, Double(d))) - 1
        while left <= right {
            let pivot = left + (right - left) / 2
            if exists(pivot, d, root) {
                left = pivot + 1
            } else {
                right = pivot - 1
            }
        }

        return Int(pow(2.0, Double(d))) - 1 + left
    }
}

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