Задача: 279. Perfect Squares
Сложность: medium

Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.

Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

class Solution {
    func numSquares(_ n: Int) -> Int {
        var dp = [Int](repeating: Int.max, count: n + 1)
        dp[0] = 0
        
        let maxSquareIndex = Int(Double(n).squareRoot()) + 1
        var squareNums = [Int](repeating: 0, count: maxSquareIndex)
        for i in 1..<maxSquareIndex {
            squareNums[i] = i * i
        }
        
        for i in 1...n {
            for s in 1..<maxSquareIndex {
                if i < squareNums[s] {
                    break
                }
                dp[i] = min(dp[i], dp[i - squareNums[s]] + 1)
            }
        }
        
        return dp[n]
    }
}

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

Задача: 625. Minimum Factorization
Сложность: medium

Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.

Пример:

Input: num = 48
Output: 68

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

1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.

2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.

3⃣Постройте результат, собирая найденные множители в обратном порядке. Если результат больше 32-битного целого числа, верните 0.

😎 Решение:

func smallestFactorization(_ num: Int) -> Int {
    if num == 1 {
        return 1
    }
    
    var num = num
    var factors = [Int]()
    
    for i in stride(from: 9, through: 2, by: -1) {
        while num % i == 0 {
            factors.append(i)
            num /= i
        }
    }
    
    if num > 1 {
        return 0
    }
    
    var result: Int64 = 0
    for factor in factors.reversed() {
        result = result * 10 + Int64(factor)
        if result > Int32.max {
            return 0
        }
    }
    
    return Int(result)
}

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

Задача: 1046. Last Stone Weight
Сложность: easy

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

1⃣Создай максимальную кучу из массива камней.

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

3⃣Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0, если камней не осталось.

😎 Решение:

func lastStoneWeight(_ stones: [Int]) -> Int {
    var maxHeap = Heap(array: stones, sort: >)
    
    while maxHeap.count > 1 {
        let first = maxHeap.remove()!
        let second = maxHeap.remove()!
        if first != second {
            maxHeap.insert(first - second)
        }
    }
    
    return maxHeap.peek() ?? 0
}

struct Heap<Element: Equatable> {
    var elements: [Element]
    let sort: (Element, Element) -> Bool
    
    init(array: [Element], sort: @escaping (Element, Element) -> Bool) {
        self.elements = array
        self.sort = sort
        buildHeap()
    }
    
    var isEmpty: Bool { return elements.isEmpty }
    var count: Int { return elements.count }
    func peek() -> Element? { return elements.first }
    
    mutating func buildHeap() {
        for index in (0 ..< count / 2).reversed() {
            siftDown(from: index)
        }
    }
    
    mutating func insert(_ value: Element) {
        elements.append(value)
        siftUp(from: elements.count - 1)
    }
    
    mutating func remove() -> Element? {
        guard !isEmpty else { return nil }
        elements.swapAt(0, count - 1)
        defer { siftDown(from: 0) }
        return elements.removeLast()
    }
    
    mutating func siftDown(from index: Int) {
        var parent = index
        while true {
            let left = 2 * parent + 1
            let right = 2 * parent + 2
            var candidate = parent
            if left < count && sort(elements[left], elements[candidate]) {
                candidate = left
            }
            if right < count && sort(elements[right], elements[c

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

Задача: 631. Design Excel Sum Formula
Сложность: hard

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

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

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

2⃣Метод установки значений
Реализуйте метод set, который будет изменять значение ячейки в матрице.

3⃣Метод вычисления суммы
Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек.

😎 Решение:

class Excel {
    private var mat: [[Int]]
    private var formulas: [String: [String]]

    init(_ height: Int, _ width: Character) {
        mat = Array(repeating: Array(repeating: 0, count: Int(width.asciiValue! - Character("A").asciiValue!) + 1), count: height)
        formulas = [String: [String]]()
    }

    func set(_ row: Int, _ column: Character, _ val: Int) {
        mat[row - 1][Int(column.asciiValue! - Character("A").asciiValue!)] = val
        formulas.removeValue(forKey: "\(row)\(column)")
    }

    func get(_ row: Int, _ column: Character) -> Int {
        let key = "\(row)\(column)"
        if let _ = formulas[key] {
            return evaluateFormula(key)
        }
        return mat[row - 1][Int(column.asciiValue! - Character("A").asciiValue!)]
    }

    func sum(_ row: Int, _ column: Character, _ numbers: [String]) -> Int {
        let key = "\(row)\(column)"
        formulas[key] = numbers
        return evaluateFormula(key)
    }

    private func evaluateFormula(_ key: String) -> Int {
        guard let numbers = formulas[key] else { return 0 }
        var total = 0
        for number in numbers {
            if let rangeIndex = number.firstIndex(of: ":") {
                let start = String(number.prefix(upTo: rangeIndex))
                let end = String(number.suffix(from: number.index(after: rangeIndex)))
                let startRow = Int(start.suffix(start.count - 1))!
                let startCol = start.prefix(1).first!
                let endRow = Int(end.suffix(end.count - 1))!
                let endCol = end.prefix(1).first!
                for r in startRow...endRow {
                    for c in startCol.asciiValue!...endCol.asciiValue! {
                        total += get(r, Character(UnicodeScalar(c)))
                    }
                }
            } else {
                let row = Int(number.suffix(number.count - 1))!
                let col = number.prefix(1).first!
                total += get(row, col)
            }
        }
        return total
    }
}

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

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

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