Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

Input: n = 2, trust = [[1,2]]
Output: 2

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

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

2⃣Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.

3⃣Создание нового дерева:
После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева.

😎 Решение:

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

class Solution {
    func insertIntoMaxTree(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        guard let root = root else { return TreeNode(val) }
        if val > root.val {
            return TreeNode(val, root, nil)
        }
        root.right = insertIntoMaxTree(root.right, val)
        return root
    }
}

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

Задача: 1216. Valid Palindrome III
Сложность: hard

Дана строка s и целое число k. Верните true, если s является k-палиндромом.
Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.

Пример:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

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

1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j.

2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo.

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

😎 Решение:

class Solution {
    var memo: [[Int?]] = []

    func isValidPalindrome(_ s: String, _ k: Int) -> Bool {
        let n = s.count
        memo = Array(repeating: Array(repeating: nil, count: n), count: n)
        let sArray = Array(s)
        return isValidPalindromeHelper(sArray, 0, n - 1) <= k
    }

    private func isValidPalindromeHelper(_ s: [Character], _ i: Int, _ j: Int) -> Int {
        if i == j {
            return 0
        }
        if i == j - 1 {
            return s[i] != s[j] ? 1 : 0
        }
        if let res = memo[i][j] {
            return res
        }
        if s[i] == s[j] {
            memo[i][j] = isValidPalindromeHelper(s, i + 1, j - 1)
        } else {
            memo[i][j] = 1 + min(isValidPalindromeHelper(s, i + 1, j), isValidPalindromeHelper(s, i, j - 1))
        }
        return memo[i][j]!
    }
}

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

Задача: 986. Interval List Intersections
Сложность: medium

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

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

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

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

Пример:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

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

1⃣Инициализация указателей:
Завести два указателя i и j, указывающие на начало firstList и secondList соответственно.

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

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

😎 Решение:

func intervalIntersection(_ firstList: [[Int]], _ secondList: [[Int]]) -> [[Int]] {
    var i = 0, j = 0
    var result = [[Int]]()

    while i < firstList.count && j < secondList.count {
        let start = max(firstList[i][0], secondList[j][0])
        let end = min(firstList[i][1], secondList[j][1])
        
        if start <= end {
            result.append([start, end])
        }
        
        if firstList[i][1] < secondList[j][1] {
            i += 1
        } else {
            j += 1
        }
    }
    
    return result
}

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

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

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

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов.

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

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

3⃣Верните minDiff, которое хранит минимальную разницу между наибольшими и наименьшими значениями после удаления до трех элементов.

😎 Решение

class Solution {
    func minDifference(_ nums: [Int]) -> Int {
        let numsSize = nums.count
        
        if numsSize <= 4 { return 0 }
        
        let sortedNums = nums.sorted()
        
        var minDiff = Int.max
        
        for left in 0..<4 {
            let right = numsSize - 4 + left
            minDiff = min(minDiff, sortedNums[right] - sortedNums[left])
        }
        
        return minDiff
    }
}

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

Задача: 1020. Number of Enclaves
Сложности: medium

Вам дана двоичная матричная сетка m x n, где 0 обозначает морскую ячейку, а 1 - сухопутную. Ход состоит из перехода от одной сухопутной ячейки к другой соседней (в 4-х направлениях) или выхода за границу сетки. Верните количество сухопутных ячеек в сетке, для которых мы не можем выйти за границу сетки за любое количество ходов.

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    func numEnclaves(_ grid: [[Int]]) -> Int {
        var grid = grid
        let m = grid.count
        let n = grid[0].count
        
        func dfs(_ x: Int, _ y: Int) {
            if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1 {
                return
            }
            grid[x][y] = 0
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        }
        
        for i in 0..<m {
            if grid[i][0] == 1 {
                dfs(i, 0)
            }
            if grid[i][n - 1] == 1 {
                dfs(i, n - 1)
            }
        }
        
        for j in 0..<n {
            if grid[0][j] == 1 {
                dfs(0, j)
            }
            if grid[m - 1][j] == 1 {
                dfs(m - 1, j)
            }
        }
        
        var count = 0
        for i in 0..<m {
            for j in 0..<n {
                if grid[i][j] == 1 {
                    count += 1
                }
            }
        }
        
        return count
    }
}

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

Задача: 682. Baseball Game
Сложность: medium

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

Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих:

Целое число x.
Записать новый счет, равный x.
'+'.
Записать новый счет, который является суммой двух предыдущих очков.
'D'.
Записать новый счет, который в два раза больше предыдущего очка.
'C'.
Аннулировать предыдущее очко, удалив его из записи.
Верните сумму всех очков в записи после применения всех операций.

Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны.

Пример:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

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

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

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

3⃣После обработки всех операций верните сумму всех значений в стеке.

😎 Решение:

class Solution {
    func calPoints(_ ops: [String]) -> Int {
        var stack = [Int]()
        
        for op in ops {
            if op == "+" {
                let top = stack.removeLast()
                let newTop = top + stack.last!
                stack.append(top)
                stack.append(newTop)
            } else if op == "C" {
                stack.removeLast()
            } else if op == "D" {
                stack.append(2 * stack.last!)
            } else {
                stack.append(Int(op)!)
            }
        }
        
        return stack.reduce(0, +)
    }
}

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

Задача: 369. Plus One Linked List
Сложность: medium

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

Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

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

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

1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.

2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).

😎 Решение:

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

class Solution {
    func plusOne(_ head: ListNode?) -> ListNode? {
        let sentinel = ListNode(0)
        sentinel.next = head
        var notNine = sentinel

        var current = head
        while current != nil {
            if current!.val != 9 {
                notNine = current!
            }
            current = current!.next
        }

        notNine.val += 1
        notNine = notNine.next

        while notNine != nil {
            notNine!.val = 0
            notNine = notNine!.next
        }

        return sentinel.val == 0 ? sentinel.next : sentinel
    }
}

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

Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium

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

Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

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

1⃣Создайте двумерный массив для хранения длин общих подмассивов.

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

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

😎 Решение:

func findLength(_ nums1: [Int], _ nums2: [Int]) -> Int {
    var dp = Array(repeating: Array(repeating: 0, count: nums2.count + 1), count: nums1.count + 1)
    var maxLength = 0
    for i in (0..<nums1.count).reversed() {
        for j in (0..<nums2.count).reversed() {
            if nums1[i] == nums2[j] {
                dp[i][j] = dp[i + 1][j + 1] + 1
                maxLength = max(maxLength, dp[i][j])
            }
        }
    }
    return maxLength
}

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

Задача: 730. Count Different Palindromic Subsequences
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

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

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

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

func countPalindromicSubsequences(_ s: String) -> Int {
    let MOD = 1_000_000_007
    let n = s.count
    var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
    let sArray = Array(s)
    
    for i in 0..<n {
        dp[i][i] = 1
    }
    
    for length in 2...n {
        for i in 0...(n - length) {
            let j = i + length - 1
            if sArray[i] == sArray[j] {
                var l = i + 1
                var r = j - 1
                while l <= r && sArray[l] != sArray[i] {
                    l += 1
                }
                while l <= r && sArray[r] != sArray[j] {
                    r -= 1
                }
                if l > r {
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 2
                } else if l == r {
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 1
                } else {
                    dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1]
                }
            } else {
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
            }
            dp[i][j] = (dp[i][j] + MOD) % MOD
        }
    }
    
    return dp[0][n - 1]
}

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

Задача: 374. Guess Number Higher or Lower
Сложность: easy

Мы играем в игру "Угадай число". Правила игры следующие:

Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.

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

Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:

-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.

Пример:

Input: n = 10, pick = 6
Output: 6

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

1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.

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

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

😎 Решение:

class Solution: GuessGame {
    func guessNumber(_ n: Int) -> Int {
        var low = 1
        var high = n
        while low <= high {
            let mid = low + (high - low) / 2
            let res = guess(mid)
            if res == 0 {
                return mid
            } else if res < 0 {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
        return -1
    }
}

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

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

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

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

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

1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎 Решение:

class Solution {
    func reorganizeString(_ s: String) -> String {
        var charCounts = [Int](repeating: 0, count: 26)
        for c in s {
            charCounts[Int(c.asciiValue! - Character("a").asciiValue!)] += 1
        }
        
        var pq = PriorityQueue<(Int, Character)>(by: { $0.0 > $1.0 })
        for i in 0..<26 {
            if charCounts[i] > 0 {
                pq.push((charCounts[i], Character(UnicodeScalar(i + Int(Character("a").asciiValue!))!)))
            }
        }
        
        var result = ""
        while !pq.isEmpty {
            let first = pq.pop()!
            if result.isEmpty || first.1 != result.last {
                result.append(first.1)
                if first.0 > 1 {
                    pq.push((first.0 - 1, first.1))
                }
            } else {
                if pq.isEmpty {
                    return ""
                }
                let second = pq.pop()!
                result.append(second.1)
                if second.0 > 1 {
                    pq.push((second.0 - 1, second.1))
                }
                pq.push(first)
            }
        }
        
        return result
    }
}

struct PriorityQueue<T> {
    private var elements: [T]
    private let priorityFunction: (T, T) -> Bool
    
    init(by priorityFunction: @escaping (T, T) -> Bool) {
        self.elements = []
        self.priorityFunction = priorityFunction
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    func peek() -> T? {
        return elements.first
    }
    
    mutating func push(_ element: T) {
        elements.append(element)
        elements.sort(by: priorityFunction)
    }
    
    mutating func pop() -> T? {
        return isEmpty ? nil : elements.removeFirst()
    }
}

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

Задача: 925. Long Pressed Name
Сложность: easy

Ваш друг набирает на клавиатуре свое имя. Иногда, при наборе символа c, клавиша может быть долго нажата, и символ будет набран 1 или более раз. Вы исследуете набранные символы клавиатуры. Верните True, если возможно, что это было имя вашего друга, при этом некоторые символы (возможно, ни один) не были долго нажаты.

Пример:

Input: name = "alex", typed = "aaleex"
Output: true

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

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

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

3⃣Вернуть True, если все символы имени были обработаны, иначе False.

😎 Решение:

class Solution {
    func isLongPressedName(_ name: String, _ typed: String) -> Bool {
        let nameArray = Array(name)
        let typedArray = Array(typed)
        var i = 0
        var j = 0
        
        while j < typedArray.count {
            if i < nameArray.count && nameArray[i] == typedArray[j] {
                i += 1
            } else if j == 0 || typedArray[j] != typedArray[j - 1] {
                return false
            }
            j += 1
        }
        
        return i == nameArray.count
    }
}

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

Задача: 360. Sort Transformed Array
Сложность: medium

Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.

Пример:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

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

1⃣Преобразование и сортировка
Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed.

2⃣Поразрядная сортировка
Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed.

3⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

class Solution {
    func sortTransformedArray(_ nums: [Int], _ a: Int, _ b: Int, _ c: Int) -> [Int] {
        var transformed = nums.map { a * $0 * $0 + b * $0 + c }
        radixSort(&transformed)
        return transformed
    }

    private func radixSort(_ array: inout [Int]) {
        let maxElement = array.map { abs($0) }.max() ?? 0
        var placeValue = 1

        while maxElement / placeValue > 0 {
            countingSortByDigit(&array, placeValue)
            placeValue *= 10
        }

        let negatives = array.filter { $0 < 0 }.sorted()
        let positives = array.filter { $0 >= 0 }.sorted()
        array = negatives + positives
    }

    private func countingSortByDigit(_ array: inout [Int], _ placeValue: Int) {
        var output = Array(repeating: 0, count: array.count)
        var count = Array(repeating: 0, count: 10)

        for num in array {
            let digit = (abs(num) / placeValue) % 10
            count[digit] += 1
        }

        for i in 1..<10 {
            count[i] += count[i - 1]
        }

        for num in array.reversed() {
            let digit = (abs(num) / placeValue) % 10
            output[count[digit] - 1] = num
            count[digit] -= 1
        }

        array = output
    }
}

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

Задача: 654. Maximum Binary Tree
Сложность: medium

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

Пример:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

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

1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением.

2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения.

3⃣Рекурсивно постройте правое поддерево для подмассива справа от максимального значения.

😎 Решение:

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

func constructMaximumBinaryTree(_ nums: [Int]) -> TreeNode? {
    guard !nums.isEmpty else { return nil }
    let maxIndex = nums.firstIndex(of: nums.max()!)!
    let root = TreeNode(nums[maxIndex])
    root.left = constructMaximumBinaryTree(Array(nums[..<maxIndex]))
    root.right = constructMaximumBinaryTree(Array(nums[(maxIndex + 1)...]))
    return root
}

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

Задача: 896. Monotonic Array
Сложность: easy

Массив является монотонным, если он либо монотонно возрастает, либо монотонно убывает. Массив nums является монотонно возрастающим, если для всех i <= j, nums[i] <= nums[j]. Массив nums является монотонно убывающим, если для всех i <= j, nums[i] >= nums[j]. Если задан целочисленный массив nums, верните true, если данный массив монотонный, или false в противном случае.

Пример:

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

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

1⃣Определить два флага: increasing и decreasing.

2⃣Пройтись по массиву: Если текущий элемент больше следующего, установить increasing в false. Если текущий элемент меньше следующего, установить decreasing в false.

3⃣Вернуть true, если хотя бы один из флагов true, иначе вернуть false.

😎 Решение:

func isMonotonic(_ nums: [Int]) -> Bool {
    var increasing = true
    var decreasing = true
    for i in 1..<nums.count {
        if nums[i] > nums[i - 1] {
            decreasing = false
        }
        if nums[i] < nums[i - 1] {
            increasing = false
        }
    }
    return increasing || decreasing
}

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

Задача: 731. My Calendar II
Сложность: medium

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

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

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

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

😎 Решение:

class MyCalendarTwo {
    var events: [(Int, Int)]
    var overlaps: [(Int, Int)]
    
    init() {
        events = []
        overlaps = []
    }
    
    func book(_ start: Int, _ end: Int) -> Bool {
        for (os, oe) in overlaps {
            if start < oe && end > os {
                return false
            }
        }
        for (es, ee) in events {
            if start < ee && end > es {
                overlaps.append((max(start, es), min(end, ee)))
            }
        }
        events.append((start, end))
        return true
    }
}

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

Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium

Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.

Пример:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7

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

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

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

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

😎 Решение:

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

class Solution {
    func maxAncestorDiff(_ root: TreeNode?) -> Int {
        func dfs(_ node: TreeNode?, _ min_val: Int, _ max_val: Int) -> Int {
            guard let node = node else { return max_val - min_val }
            let min_val = min(min_val, node.val)
            let max_val = max(max_val, node.val)
            let left = dfs(node.left, min_val, max_val)
            let right = dfs(node.right, min_val, max_val)
            return max(left, right)
        }
        return dfs(root, root!.val, root!.val)
    }
}

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

Задача: 217. Contains Duplicate
Сложность: easy

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

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

Задача: 988. Smallest String Starting From Leaf
Сложность: medium

Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.

Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.

Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.

Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.

Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

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

1⃣Инициализация и подготовка:
Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк).
Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы.

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

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

😎 Решение:

class Solution {
    var ans = "~"
    
    func smallestFromLeaf(_ root: TreeNode?) -> String {
        dfs(root, "")
        return ans
    }
    
    func dfs(_ node: TreeNode?, _ path: String) {
        guard let node = node else { return }
        let currentPath = String(UnicodeScalar(node.val + 97)!) + path
        if node.left == nil && node.right == nil {
            ans = min(ans, currentPath)
        }
        dfs(node.left, currentPath)
        dfs(node.right, currentPath)
    }
}

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

Задача: 1011. Capacity To Ship Packages Within D Days
Сложность: medium

На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней.

Пример:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

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

1⃣Определение диапазона возможных ответов:
Минимальная грузоподъемность должна быть не меньше максимального веса одного пакета (чтобы хотя бы один пакет можно было загрузить).
Максимальная грузоподъемность - это сумма всех весов (если все пакеты будут отправлены за один день).

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

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

😎 Решение:

class Solution {
    func shipWithinDays(_ weights: [Int], _ D: Int) -> Int {
        func canShipInDays(_ capacity: Int) -> Bool {
            var days = 1
            var total = 0
            for weight in weights {
                if total + weight > capacity {
                    days += 1
                    total = 0
                }
                total += weight
            }
            return days <= D
        }
        
        var left = weights.max()!
        var right = weights.reduce(0, +)
        
        while left < right {
            let mid = (left + right) / 2
            if canShipInDays(mid) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        
        return left
    }
}

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