Задача: 414. Third Maximum Number
Сложность: easy

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

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

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

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

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

3⃣Если третье максимальное число существует, верните его. В противном случае, верните первое максимальное число.

😎 Решение:

func thirdMax(_ nums: [Int]) -> Int {
    var first: Int? = nil
    var second: Int? = nil
    var third: Int? = nil
    
    for num in nums {
        if num == first || num == second || num == third {
            continue
        }
        if first == nil || num > first! {
            third = second
            second = first
            first = num
        } else if second == nil || num > second! {
            third = second
            second = num
        } else if third == nil || num > third! {
            third = num
        }
    }
    
    return third ?? first!
}

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

Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard

Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.

Пример:

Input: n = 2, m = 3
Output: 3

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

1⃣Инициализация рекурсивной функции:
Функция принимает размеры прямоугольника n x m.

2⃣Базовый случай:
Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия.

3⃣Рекурсивный случай:
Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

class Solution {
    func tilingRectangle(_ n: Int, _ m: Int) -> Int {
        var dp = Array(repeating: Array(repeating: Int.max, count: m + 1), count: n + 1)
        
        for i in 1...min(n, m) {
            dp[i][i] = 1
        }
        
        for h in 1...n {
            for w in 1...m {
                if h == w { continue }
                for i in 1...h / 2 {
                    dp[h][w] = min(dp[h][w], dp[i][w] + dp[h - i][w])
                }
                for j in 1...w / 2 {
                    dp[h][w] = min(dp[h][w], dp[h][j] + dp[h][w - j])
                }
            }
        }
        return dp[n][m]
    }
}

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

Задача: 1035. Uncrossed Lines
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.

Пример:

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

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

1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS):
Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2.

2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.

3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].

😎 Решение:

class Solution {
    func maxUncrossedLines(_ nums1: [Int], _ nums2: [Int]) -> Int {
        let m = nums1.count, n = nums2.count
        var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)

        for i in 1...m {
            for j in 1...n {
                if nums1[i - 1] == nums2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }

        return dp[m][n]
    }
}

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

Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    func wordPatternMatch(_ pattern: String, _ s: String) -> Bool {
        var symbolMap = [Character: String]()
        var wordSet = Set<String>()
        return isMatch(s, 0, pattern, 0, &symbolMap, &wordSet)
    }

    private func isMatch(_ s: String, _ sIndex: Int, _ pattern: String, _ pIndex: Int,
                         _ symbolMap: inout [Character: String], _ wordSet: inout Set<String>) -> Bool {
        if pIndex == pattern.count {
            return sIndex == s.count
        }
        let symbol = pattern[pattern.index(pattern.startIndex, offsetBy: pIndex)]
        if let word = symbolMap[symbol] {
            if !s.hasPrefix(word, from: sIndex) {
                return false
            }
            return isMatch(s, sIndex + word.count, pattern, pIndex + 1, &symbolMap, &wordSet)
        }
        for k in sIndex + 1...s.count {
            let newWord = String(s[s.index(s.startIndex, offsetBy: sIndex)..<s.index(s.startIndex, offsetBy: k)])
            if wordSet.contains(newWord) {
                continue
            }
            symbolMap[symbol] = newWord
            wordSet.insert(newWord)
            if isMatch(s, k, pattern, pIndex + 1, &symbolMap, &wordSet) {
                return true
            }
            symbolMap[symbol] = nil
            wordSet.remove(newWord)
        }
        return false
    }
}

extension String {
    func hasPrefix(_ prefix: String, from index: Int) -> Bool {
        return self[index..<index + prefix.count] == prefix
    }

    subscript (bounds: Range<Int>) -> Substring {
        let start = index(startIndex, offsetBy: bounds.lowerBound)
        let end = index(startIndex, offsetBy: bounds.upperBound)
        return self[start..<end]
    }
}

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

Задача: 934. Shortest Bridge
Сложность: medium

Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.

Пример:

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

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

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

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

3⃣Вернуть длину кратчайшего пути.

😎 Решение:

class Solution {
    func shortestBridge(_ grid: [[Int]]) -> Int {
        let n = grid.count
        var grid = grid
        
        func neighbors(_ x: Int, _ y: Int) -> [(Int, Int)] {
            return [(-1, 0), (1, 0), (0, -1), (0, 1)].map { (dx, dy) in (x + dx, y + dy) }.filter { (nx, ny) in 0 <= nx && nx < n && 0 <= ny && ny < n }
        }
        
        func bfs(_ queue: [(Int, Int)]) -> Int {
            var queue = queue
            var visited = Set(queue)
            var steps = 0
            while !queue.isEmpty {
                var newQueue = [(Int, Int)]()
                for (x, y) in queue {
                    for (nx, ny) in neighbors(x, y) {
                        if !visited.contains((nx, ny)) {
                            if grid[nx][ny] == 1 {
                                return steps
                            }
                            visited.insert((nx, ny))
                            newQueue.append((nx, ny))
                        }
                    }
                }
                queue = newQueue
                steps += 1
            }
            return -1
        }
        
        func findFirstIsland() -> [(Int, Int)] {
            for i in 0..<n {
                for j in 0..<n {
                    if grid[i][j] == 1 {
                        var queue = [(i, j)]
                        grid[i][j] = -1
                        var island = [(i, j)]
                        while !queue.isEmpty {
                            let (x, y) = queue.removeFirst()
                            for (nx, ny) in neighbors(x, y) {
                                if grid[nx][ny] == 1 {
                                    grid[nx][ny] = -1
                                    queue.append((nx, ny))
                                    island.append((nx, ny))
                                }
                            }
                        }
                        return island
                    }
                }
            }
            return []
        }
        
        let island = findFirstIsland()
        return bfs(island)
    }
}

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

Задача: №17. Letter Combinations of a Phone Number
Сложность: medium

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Пример:

Input: digits = "23"  
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]  

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

1⃣Создать отображение цифр в буквы, как на телефонной клавиатуре.

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

3⃣Вернуть итоговый список комбинаций.

😎 Решение:

class Solution {
    private let mat: [Character: [String]] = [
        "2": ["a","b","c"], "3": ["d","e","f"], "4": ["g","h","i"],
        "5": ["j","k","l"], "6": ["m","n","o"], "7": ["p","q","r","s"],
        "8": ["t","u","v"], "9": ["w","x","y","z"]
    ]

    func letterCombinations(_ digits: String) -> [String] {
        guard !digits.isEmpty else { return [] }
        var res = [""]
        
        for digit in digits {
            guard let letters = mat[digit] else { continue }
            res = res.flatMap { prefix in letters.map { prefix + $0 } }
        }
        
        return res
    }
}

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

Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

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

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

class Solution {
    func atMostNGivenDigitSet(_ digits: [String], _ n: Int) -> Int {
        let s = String(n)
        let K = s.count
        var dp = [Int](repeating: 0, count: K + 1)
        dp[K] = 1

        for i in stride(from: K - 1, through: 0, by: -1) {
            for d in digits {
                let sc = s[s.index(s.startIndex, offsetBy: i)]
                if d < String(sc) {
                    dp[i] += Int(pow(Double(digits.count), Double(K - i - 1)))
                } else if d == String(sc) {
                    dp[i] += dp[i + 1]
                }
            }
        }

        var total = dp[0]
        for i in 1..<K {
            total += Int(pow(Double(digits.count), Double(i)))
        }

        return total
    }
}

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

Задача: 594. Longest Harmonious Subsequence
Сложность: easy

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

Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.

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

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

2⃣На каждой итерации проверьте, существуют ли в словаре элементы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности.

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

😎 Решение:

class Solution {
    func findLHS(_ nums: [Int]) -> Int {
        var countDict = [Int: Int]()
        var res = 0
        
        for num in nums {
            countDict[num, default: 0] += 1
            if let countPlusOne = countDict[num + 1] {
                res = max(res, countDict[num]! + countPlusOne)
            }
            if let countMinusOne = countDict[num - 1] {
                res = max(res, countDict[num]! + countMinusOne)
            }
        }
        
        return res
    }
}

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

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

Мы играем в угадайку. Правила игры следующие:

Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.

Пример:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

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

1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента.

2⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость.

3⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы.

😎 Решение:

class Solution {
    func calculate(_ low: Int, _ high: Int) -> Int {
        if low >= high {
            return 0
        }
        var minres = Int.max
        for i in low...high {
            let res = i + max(calculate(i + 1, high), calculate(low, i - 1))
            minres = min(res, minres)
        }
        return minres
    }

    func getMoneyAmount(_ n: Int) -> Int {
        return calculate(1, n)
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив previousEnd.next = node.
Настройте указатели узла: node.prev = previousEnd и node.next = tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.

2⃣Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev.
Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.

3⃣Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val.
put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.

😎 Решение:

class Node {
    var key: Int
    var value: Int
    var next: Node?
    var prev: Node?

    init(_ key: Int, _ value: Int) {
        self.key = key
        self.value = value
    }
}

class LRUCache {
    private var capacity: Int
    private var dict = [Int: Node]()
    private let head: Node
    private let tail: Node

    init(_ capacity: Int) {
        self.capacity = capacity
        head = Node(-1, -1)
        tail = Node(-1, -1)
        head.next = tail
        tail.prev = head
    }

    func get(_ key: Int) -> Int {
        guard let node = dict[key] else {
            return -1
        }
        remove(node)
        add(node)
        return node.value
    }

    func put(_ key: Int, _ value: Int) {
        if let node = dict[key] {
            remove(node)
        }
        let newNode = Node(key, value)
        add(newNode)
        dict[key] = newNode
        if dict.count > capacity {
            if let nodeToDelete = head.next {
                remove(nodeToDelete)
                dict.removeValue(forKey: nodeToDelete.key)
            }
        }
    }

    private func add(_ node: Node) {
        let prev = tail.prev
        prev?.next = node
        node.prev = prev
        node.next = tail
        tail.prev = node
    }

    private func remove(_ node: Node) {
        let prev = node.prev
        let next = node.next
        prev?.next = next
        next?.prev = prev
    }
}

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

Задача: 553. Optimal Division
Сложность: medium

Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой.

Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4".
Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным.

Верните соответствующее выражение, которое имеет максимальное значение в строковом формате.

Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

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

1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе.

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

3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его.

😎 Решение:

class Solution {
    private func addStrings(_ num1: [Int], _ num2: [Int]) -> [Int] {
        var ans = [Int]()
        var carry = 0
        let n1 = num1.count
        let n2 = num2.count

        for i in 0..<max(n1, n2) + 1 {
            let digit1 = i < n1 ? num1[i] : 0
            let digit2 = i < n2 ? num2[i] : 0
            let sum = digit1 + digit2 + carry
            carry = sum / 10
            ans.append(sum % 10)
        }
        return ans
    }

    private func multiplyOneDigit(_ firstNumber: String, _ secondNumberDigit: Character, _ numZeros: Int) -> [Int] {
        var currentResult = [Int](repeating: 0, count: numZeros)
        var carry = 0

        for digit in firstNumber {
            let multiplication = (secondNumberDigit.wholeNumberValue! * digit.wholeNumberValue!) + carry
            carry = multiplication / 10
            currentResult.append(multiplication % 10)
        }
        if carry != 0 {
            currentResult.append(carry)
        }
        return currentResult
    }

    func multiply(_ firstNumber: String, _ secondNumber: String) -> String {
        if firstNumber == "0" || secondNumber == "0" {
            return "0"
        }

        let firstNumber = String(firstNumber.reversed())
        let secondNumber = String(secondNumber.reversed())

        var ans = [Int](repeating: 0, count: firstNumber.count + secondNumber.count)

        for (i, digit) in secondNumber.enumerated() {
            ans = addStrings(multiplyOneDigit(firstNumber, digit, i), ans)
        }

        while ans.last == 0 {
            ans.removeLast()
        }

        return ans.reversed().map { String($0) }.joined()
    }
}

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

Задача: 680. Valid Palindrome II
Сложность: easy

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

Пример:

Input: s = "aba"
Output: true

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

1⃣Создайте вспомогательную функцию checkPalindrome, которая принимает строку s и два указателя i и j. Эта функция возвращает логическое значение, указывающее, является ли подстрока s.substring(i, j) палиндромом.

2⃣Инициализируйте два указателя: i = 0 и j = s.length() - 1. Пока i < j, проверьте, совпадают ли символы в индексах i и j. Если нет, это значит, что нам нужно удалить один из этих символов.

3⃣Попробуйте оба варианта, используя checkPalindrome. Верните true, если либо checkPalindrome(s, i, j - 1), либо checkPalindrome(s, i + 1, j) возвращает true. Если мы выходим из цикла while, это значит, что исходная строка является палиндромом. Поскольку нам не нужно было использовать удаление, следует вернуть true.

😎 Решение:

class Solution {
    private func checkPalindrome(_ s: String, _ i: Int, _ j: Int) -> Bool {
        var i = i
        var j = j
        let sArray = Array(s)
        
        while i < j {
            if sArray[i] != sArray[j] {
                return false
            }
            i += 1
            j -= 1
        }
        
        return true
    }
    
    func validPalindrome(_ s: String) -> Bool {
        var i = 0
        var j = s.count - 1
        let sArray = Array(s)
        
        while i < j {
            if sArray[i] != sArray[j] {
                return checkPalindrome(s, i, j - 1) || checkPalindrome(s, i + 1, j)
            }
            i += 1
            j -= 1
        }
        
        return true
    }
}

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

Задача: 1480. Running Sum of 1d Array
Сложность: easy

Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]).

Верните массив текущих сумм для nums.

Пример:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

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

1⃣Инициализация:
Определите массив result.
Инициализируйте первый элемент массива result первым элементом входного массива nums.

2⃣Вычисление текущих сумм:
На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result.

3⃣Повторение для всех индексов:
Повторите шаг 2 для всех индексов от 1 до n-1.

😎 Решение:

class Solution {
    func runningSum(_ nums: [Int]) -> [Int] {
        var result = [Int](repeating: 0, count: nums.count)
        result[0] = nums[0]
        for i in 1..<nums.count {
            result[i] = result[i - 1] + nums[i]
        }
        return result
    }
}

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

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

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

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

class Solution {
    func isCompleteTree(_ root: TreeNode?) -> Bool {
        if root == nil {
            return true
        }

        var queue = [TreeNode?]()
        queue.append(root)
        var nullNodeFound = false

        while !queue.isEmpty {
            let node = queue.removeFirst()
            
            if node == nil {
                nullNodeFound = true
            } else {
                if nullNodeFound {
                    return false
                }
                queue.append(node?.left)
                queue.append(node?.right)
            }
        }
        return true
    }
}

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

Задача: 941. Valid Mountain Array
Сложность: easy

Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Пример:

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

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

1⃣Убедиться, что длина массива не меньше 3.

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

3⃣Вернуть true, если оба условия выполнены, иначе вернуть false.

😎 Решение:

class Solution {
    func validMountainArray(_ arr: [Int]) -> Bool {
        if arr.count < 3 {
            return false
        }
        
        var i = 1
        while i < arr.count && arr[i] > arr[i - 1] {
            i += 1
        }
        
        if i == 1 || i == arr.count {
            return false
        }
        
        while i < arr.count && arr[i] < arr[i - 1] {
            i += 1
        }
        
        return i == arr.count
    }
}

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

Задача: 25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

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

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

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

2⃣Используем фиктивный узел (dummy) для удобного управления указателями.

3⃣Переворачиваем группы по k узлов, изменяя связи в списке.

😎Решение:

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

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil || k == 1 {
        return head
    }
    
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    var next: ListNode?
    var prev: ListNode? = dummy
    
    var count = 0
    while current?.next != nil {
        current = current?.next
        count += 1
    }
    
    while count >= k {
        current = prev?.next
        next = current?.next
        for _ in 1..<k {
            current?.next = next?.next
            next?.next = prev?.next
            prev?.next = next
            next = current?.next
        }
        prev = current
        count -= k
    }
    
    return dummy.next
}

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

Задача: 131. Palindrome Partitioning
Сложность: Medium

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

Пример:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

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

1⃣Инициация рекурсивного обхода:
В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start.
Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки.

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

3⃣Возврат (Backtracking) и сохранение результатов:
Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат.

😎 Решение:

class Solution {
    func partition(_ s: String) -> [[String]] {
        var result = [[String]]()
        var currentList = [String]()
        dfs(&result, s, 0, &currentList)
        return result
    }

    private func dfs(_ result: inout [[String]], _ s: String, _ start: Int, _ currentList: inout [String]) {
        if start >= s.count {
            result.append(currentList)
        }
        for end in start..<s.count {
            if isPalindrome(s, start, end) {
                let range = s.index(s.startIndex, offsetBy: start)...s.index(s.startIndex, offsetBy: end)
                currentList.append(String(s[range]))
                dfs(&result, s, end + 1, &currentList)
                currentList.removeLast()
            }
        }
    }

    private func isPalindrome(_ s: String, _ low: Int, _ high: Int) -> Bool {
        var low = low
        var high = high
        let sArray = Array(s)
        while low < high {
            if sArray[low] != sArray[high] {
                return false
            }
            low += 1
            high -= 1
        }
        return true
    }
}

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

Задача: 409. Longest Palindrome
Сложность: easy

Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.

Пример:

Input: s = "abccccdd"
Output: 7

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

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

2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.

3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа.

😎 Решение:

func longestPalindrome(_ s: String) -> Int {
    var charCount = [Character: Int]()
    for char in s {
        charCount[char, default: 0] += 1
    }
    var length = 0
    var oddFound = false
    for count in charCount.values {
        if count % 2 == 0 {
            length += count
        } else {
            length += count - 1
            oddFound = true
        }
    }
    return oddFound ? length + 1 : length
}

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

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

Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.

Пример:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

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

1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].

2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].

3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].

😎 Решение:

class SnapshotArray {
    var snapId = 0
    var historyRecords: [Int: [Int: Int]]
    
    init(_ length: Int) {
        historyRecords = [Int: [Int: Int]]()
        for i in 0..<length {
            historyRecords[i] = [0: 0]
        }
    }

    func set(_ index: Int, _ val: Int) {
        historyRecords[index]![snapId] = val
    }

    func snap() -> Int {
        defer { snapId += 1 }
        return snapId
    }

    func get(_ index: Int, _ snapId: Int) -> Int {
        let record = historyRecords[index]!
        let keys = Array(record.keys).sorted()
        for key in keys.reversed() {
            if key <= snapId {
                return record[key]!
            }
        }
        return 0
    }
}

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

Задача: 1518. Water Bottles
Сложность: easy

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

Операция питья полной бутылки воды превращает её в пустую бутылку.

Даны два целых числа numBottles и numExchange. Верните максимальное количество бутылок с водой, которые вы можете выпить.

Пример:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

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

1⃣Инициализируйте переменную ответа consumedBottles значением 0.

2⃣Продолжайте выполнять следующие действия, пока количество numBottles больше или равно numExchange:
— Выпейте numExchange количество полных бутылок, т.е. добавьте numExchange к consumedBottles.
— Уменьшите numExchange от доступных полных бутылок numBottles.
— Обменяйте пустые бутылки на одну полную бутылку, т.е. увеличьте numBottles на одну.

3⃣Верните consumedBottles + numBottles.

😎 Решение

class Solution {
    func numWaterBottles(_ numBottles: Int, _ numExchange: Int) -> Int {
        var numBottles = numBottles
        var consumedBottles = 0

        while numBottles >= numExchange {
            consumedBottles += numExchange
            numBottles -= numExchange
            numBottles += 1
        }

        return consumedBottles + numBottles
    }
}

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