Задача: 1021. Remove Outermost Parentheses
Сложность: easy

Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())".
Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s.

Пример:

Input: s = "(()())(())"
Output: "()()()"

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

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

2⃣Обработка строки:
Итерируйте по каждому символу строки.
Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат.
Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат.

3⃣Возврат результата:
Верните результат, содержащий строку без крайних скобок из каждой примитивной строки.

😎 Решение:

class Solution {
    func removeOuterParentheses(_ s: String) -> String {
        var result = ""
        var level = 0
        
        for char in s {
            if char == "(" {
                if level > 0 {
                    result.append(char)
                }
                level += 1
            } else {
                level -= 1
                if level > 0 {
                    result.append(char)
                }
            }
        }
        
        return result
    }
}

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

Задача: 955. Delete Columns to Make Sorted II
Сложность: medium

Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.

Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

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

1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

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

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

😎 Решение:

class Solution {
    func minDeletionSize(_ strs: [String]) -> Int {
        let n = strs.count
        let m = strs[0].count
        var deleteCount = [Bool](repeating: false, count: m)
        
        func isSorted() -> Bool {
            for i in 0..<n - 1 {
                for j in 0..<m {
                    if deleteCount[j] { continue }
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] >
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        return false
                    }
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] <
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        break
                    }
                }
            }
            return true
        }
        
        while !isSorted() {
            for j in 0..<m {
                if deleteCount[j] { continue }
                for i in 0..<n - 1 {
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] >
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        deleteCount[j] = true
                        break
                    }
                }
                if deleteCount[j] { break }
            }
        }
        
        return deleteCount.filter { $0 }.count
    }
}

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

Задача: 278. First Bad Version
Сложность: easy

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

Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.

Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.

Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

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

1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.

2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.

3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.

😎 Решение:

class Solution {
    func firstBadVersion(_ n: Int) -> Int {
        var left = 1
        var right = n
        while left < right {
            let mid = left + (right - left) / 2
            if isBadVersion(mid) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

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

Задача: 1236. Web Crawler
Сложность: medium

Учитывая url startUrl и интерфейс HtmlParser, реализуйте веб-краулер для просмотра всех ссылок, которые находятся под тем же именем хоста, что и startUrl.Верните все ссылки, полученные вашим краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все ссылки с веб-страницы с заданным url. Не просматривайте одну и ту же ссылку дважды. Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Как показано в примере url выше, имя хоста - example.org. Для простоты можно считать, что все урлы используют протокол http без указания порта. Например, урлы https://leetcode.com/problems и https://leetcode.com/contest находятся под одним и тем же именем хоста, а урлы https://example.org/test и https://example.com/abc не находятся под одним и тем же именем хоста.

Пример:

Input:
urls = [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.google.com",
  "https://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "https://news.yahoo.com/news/topics/"
Output: [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.yahoo.com/us"
]

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

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

2⃣Использование очереди для BFS:
Начинаем с начального URL и помещаем его в очередь.
Пока очередь не пуста, извлекаем текущий URL, получаем все ссылки с этой страницы, и для каждой ссылки проверяем, принадлежит ли она тому же имени хоста.

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

😎 Решение:

class HtmlParser {
    func getUrls(_ url: String) -> [String] {
        return []
    }
}

func extractHostname(_ url: String) -> String {
    if let host = URL(string: url)?.host {
        return host
    }
    return ""
}

func crawl(_ startUrl: String, _ htmlParser: HtmlParser) -> [String] {
    let hostname = extractHostname(startUrl)
    var visited = Set<String>()
    var queue = [startUrl]
    visited.insert(startUrl)
    
    while !queue.isEmpty {
        let url = queue.removeFirst()
        for nextUrl in htmlParser.getUrls(url) {
            if !visited.contains(nextUrl) && extractHostname(nextUrl) == hostname {
                visited.insert(nextUrl)
                queue.append(nextUrl)
            }
        }
    }
    
    return Array(visited)
}

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

Задача: 305. Number of Islands II
Сложность: hard

Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.

Пример:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

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

1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.

2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.

3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.

😎 Решение

class UnionFind {
    private var parent: [Int], rank: [Int], count = 0
    init(_ size: Int) { parent = Array(repeating: -1, count: size); rank = Array(repeating: 0, count: size) }
    func addLand(_ x: Int) { if parent[x] < 0 { parent[x] = x; count += 1 } }
    func isLand(_ x: Int) -> Bool { return parent[x] >= 0 }
    func find(_ x: Int) -> Int { if parent[x] != x { parent[x] = find(parent[x]) }; return parent[x] }
    func unionSet(_ x: Int, _ y: Int) { let xset = find(x), yset = find(y)
        if xset != yset { if rank[xset] < rank[yset] { parent[xset] = yset }
        else { parent[yset] = xset; if rank[xset] == rank[yset] { rank[xset] += 1 } }; count -= 1 } }
}

class Solution {
    func numIslands2(_ m: Int, _ n: Int, _ positions: [[Int]]) -> [Int] {
        let dsu = UnionFind(m * n), dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        var answer = [Int]()
        for pos in positions {
            let land = pos[0] * n + pos[1]
            dsu.addLand(land)
            for (dx, dy) in dirs {
                let x = pos[0] + dx, y = pos[1] + dy, neighbor = x * n + y
                if x >= 0 && x < m && y >= 0 && y < n && dsu.isLand(neighbor) { dsu.unionSet(land, neighbor) }
            }
            answer.append(dsu.count)
        }
        return answer
    }
}

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

Задача: 1120. Maximum Average Subtree
Сложность: medium

Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.

Поддерево дерева — это любой узел этого дерева плюс все его потомки.

Среднее значение дерева — это сумма его значений, деленная на количество узлов.

Пример:

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

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

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

2⃣Постобход (postorder traversal):
Реализуйте функцию maxAverage, которая выполняет постобход дерева, вычисляя nodeCount, valueSum и maxAverage для каждого узла, начиная с дочерних узлов и продвигаясь к родительским узлам.

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

😎 Решение:

class Solution {
    class State {
        var nodeCount: Int
        var valueSum: Int
        var maxAverage: Double
        
        init(_ nodes: Int, _ sum: Int, _ maxAvg: Double) {
            self.nodeCount = nodes
            self.valueSum = sum
            self.maxAverage = maxAvg
        }
    }
    
    func maximumAverageSubtree(_ root: TreeNode?) -> Double {
        return maxAverage(root).maxAverage
    }
    
    private func maxAverage(_ root: TreeNode?) -> State {
        guard let node = root else {
            return State(0, 0, 0)
        }
        
        let left = maxAverage(node.left)
        let right = maxAverage(node.right)
        
        let nodeCount = left.nodeCount + right.nodeCount + 1
        let sum = left.valueSum + right.valueSum + node.val
        let currentAverage = Double(sum) / Double(nodeCount)
        let maxAverage = max(currentAverage, max(left.maxAverage, right.maxAverage))
        
        return State(nodeCount, sum, maxAverage)
    }
}

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

Задача: 1161. Maximum Level Sum of a Binary Tree
Сложность: medium

Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее.

Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна.

Пример:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

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

1⃣Создайте целочисленную переменную maxSum для отслеживания максимальной суммы значений узлов на любом уровне, начав с большого отрицательного значения. Создайте переменную ans для хранения ответа на задачу. Создайте переменную level для хранения текущего уровня, через который мы проходим, и инициализируйте её значением 0. Инициализируйте очередь q типа TreeNode и добавьте в неё корень.

2⃣Выполните обход в ширину (BFS) до тех пор, пока очередь не станет пустой: увеличьте level на 1 и инициализируйте sumAtCurrentLevel = 0 для вычисления суммы всех значений узлов на этом уровне. Проходите через все узлы на уровне, используя только q.size() количество узлов. Внутри этого внутреннего цикла извлекайте все узлы на текущем уровне один за другим, добавляя их значения к sumAtCurrentLevel и добавляя левых и правых детей (если они существуют) в очередь. Поймите, что после прохождения всех узлов на уровне в очереди остаются только узлы уровня +1.

3⃣После прохождения всех узлов на уровне проверьте, больше ли sumAtCurrentLevel, чем maxSum. Если maxSum < sumAtCurrentLevel, обновите переменную ответа на ans = level и установите maxSum = sumAtCurrentLevel. Верните ans.

😎 Решение

class Solution {
    func maxLevelSum(_ root: TreeNode?) -> Int {
        var maxSum = Int.min
        var ans = 0, level = 0
        var q = [TreeNode]()
        
        if let root = root {
            q.append(root)
        }
        
        while !q.isEmpty {
            level += 1
            var sumAtCurrentLevel = 0
            for _ in 0..<q.count {
                let node = q.removeFirst()
                sumAtCurrentLevel += node.val
                if let left = node.left {
                    q.append(left)
                }
                if let right = node.right {
                    q.append(right)
                }
            }
            
            if maxSum < sumAtCurrentLevel {
                maxSum = sumAtCurrentLevel
                ans = level
            }
        }
        
        return ans
    }
}

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

Задача: 68. Text Justification
Сложность: hard

Дан массив строк words и ширина maxWidth. Необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов и была полностью (слева и справа) выровнена.

Слова следует упаковывать жадным способом; то есть стараться поместить как можно больше слов в каждую строку. Дополнительные пробелы ' ' следует добавлять по мере необходимости, чтобы каждая строка имела ровно maxWidth символов.

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

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

Примечание:
Слово определяется как последовательность символов, не содержащих пробелы.
Длина каждого слова гарантированно больше 0 и не превышает maxWidth.
Входной массив words содержит хотя бы одно слово.

Пример:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

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

1⃣Создайте два вспомогательных метода getWords и createLine, описанные выше.

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

3⃣Пока i < words.length, выполните следующие шаги:
Получите слова, которые должны быть в текущей строке, как currentLine = getWords(i).
Увеличьте i на currentLine.length.
Создайте строку, вызвав createLine(line, i), и добавьте её в ans.
Верните ans.

😎 Решение:

func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] {
    var ans = [String]()
    var i = 0

    while i < words.count {
        let currentLine = getWords(&i, words, maxWidth)
        ans.append(createLine(currentLine, i, words, maxWidth))
    }
    return ans

    func getWords(_ i: inout Int, _ words: [String], _ maxWidth: Int) -> [String] {
        var currentLine = [String]()
        var currLength = 0
        while i < words.count && currLength + words[i].count <= maxWidth {
            currentLine.append(words[i])
            currLength += words[i].count + 1
            i += 1
        }
        return currentLine
    }

    func createLine(_ line: [String], _ i: Int, _ words: [String], _ maxWidth: Int) -> String {
        var baseLength = -1
        for word in line {
            baseLength += word.count + 1
        }
        let extraSpaces = maxWidth - baseLength
        var result = line
        if line.count == 1 || i == words.count {
            return line.joined(separator: " ") + String(repeating: " ", count: extraSpaces)
        }
        let wordCount = line.count - 1
        let spacesPerWord = extraSpaces / wordCount
        let needsExtraSpace = extraSpaces % wordCount
        for j in 0..<needsExtraSpace {
            result[j] += " "
        }
        for j in 0..<wordCount {
            result[j] += String(repeating: " ", count: spacesPerWord)
        }
        return result.joined(separator: " ")
    }
}

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

Задача: 679. 24 Game
Сложность: hard

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.

Вы ограничены следующими правилами:

Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

class Solution {
    func generatePossibleResults(_ a: Double, _ b: Double) -> [Double] {
        var res = [a + b, a - b, b - a, a * b]
        if a != 0 {
            res.append(b / a)
        }
        if b != 0 {
            res.append(a / b)
        }
        return res
    }
    
    func checkIfResultReached(_ list: [Double]) -> Bool {
        if list.count == 1 {
            return abs(list[0] - 24) <= 0.1
        }
        
        for i in 0..<list.count {
            for j in i + 1..<list.count {
                var newList = [Double]()
                for k in 0..<list.count {
                    if k != i && k != j {
                        newList.append(list[k])
                    }
                }
                
                for res in generatePossibleResults(list[i], list[j]) {
                    newList.append(res)
                    if checkIfResultReached(newList) {
                        return true
                    }
                    newList.removeLast()
                }
            }
        }
        return false
    }
    
    func judgePoint24(_ cards: [Int]) -> Bool {
        let list = cards.map { Double($0) }
        return checkIfResultReached(list)
    }
}

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

Задача: 155. Min Stack
Сложность: medium

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

Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.

Вы должны реализовать решение с временной сложностью O(1) для каждой функции.

Пример:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

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

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

2⃣Работа со стеком:
Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.

3⃣Доступ к элементам:
Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.

😎 Решение:

func last<T>(_ array: [T]) -> T? {
    return array.last
}

class MinStack {
    private var stack: [(value: Int, min: Int)] = []

    func push(_ x: Int) {
        if stack.isEmpty {
            stack.append((x, x))
            return
        }
        
        let currentMin = stack.last!.min
        stack.append((x, min(currentMin, x)))
    }

    func pop() {
        stack.popLast()
    }

    func top() -> Int? {
        return stack.last?.value
    }

    func getMin() -> Int? {
        return stack.last?.min
    }
}

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

Задача: 300. Longest Increasing Subsequence
Сложность: medium

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

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

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

1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.


2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).


3⃣Верните максимальное значение из dp.

😎 Решение:

class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        var dp = [Int](repeating: 1, count: nums.count)
        
        for i in 1..<nums.count {
            for j in 0..<i {
                if nums[i] > nums[j] {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
        }
        
        return dp.max() ?? 0
    }
}

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

Задача: 916. Word Subsets
Сложность: medium

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

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

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎 Решение:

class Solution {
    func wordSubsets(_ words1: [String], _ words2: [String]) -> [String] {
        var maxCount = [Character: Int]()
        
        for word in words2 {
            var count = [Character: Int]()
            for char in word {
                count[char, default: 0] += 1
            }
            for (char, cnt) in count {
                maxCount[char] = max(maxCount[char, default: 0], cnt)
            }
        }
        
        var result = [String]()
        for word in words1 {
            var count = [Character: Int]()
            for char in word {
                count[char, default: 0] += 1
            }
            if maxCount.allSatisfy({ count[$0.key, default: 0] >= $0.value }) {
                result.append(word)
            }
        }
        
        return result
    }
}

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

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

😎 Решение:

class DSU {
    var parent: [Int]
    
    init(_ N: Int) {
        parent = Array(0..<N)
    }
    
    func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    
    func union(_ x: Int, _ y: Int) {
        parent[find(x)] = find(y)
    }
}

class Solution {
    func regionsBySlashes(_ grid: [String]) -> Int {
        let N = grid.count
        let dsu = DSU(4 * N * N)
        
        for r in 0..<N {
            for c in 0..<N {
                let root = 4 * (r * N + c)
                let val = Array(grid[r])[c]
                
                if val != "\\" {
                    dsu.union(root + 0, root + 1)
                    dsu.union(root + 2, root + 3)
                }
                if val != "/" {
                    dsu.union(root + 0, root + 2)
                    dsu.union(root + 1, root + 3)
                }
                
                if r + 1 < N {
                    dsu.union(root + 3, (root + 4 * N) + 0)
                }
                if r - 1 >= 0 {
                    dsu.union(root + 0, (root - 4 * N) + 3)
                }
                if c + 1 < N {
                    dsu.union(root + 2, (root + 4) + 1)
                }
                if c - 1 >= 0 {
                    dsu.union(root + 1, (root - 4) + 2)
                }
            }
        }
        
        var ans = 0
        for x in 0..<(4 * N * N) {
            if dsu.find(x) == x {
                ans += 1
            }
        }
        
        return ans
    }
}

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

Задача: 236. Lowest Common Ancestor of a Binary Tree
Сложность: medium

Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

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

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях.

2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву.

3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q.

😎 Решение:

class Solution {
    private var ans: TreeNode?

    init() {
        self.ans = nil
    }

    private func recurseTree(_ currentNode: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> Bool {
        guard let currentNode = currentNode else { return false }

        let left = recurseTree(currentNode.left, p, q) ? 1 : 0
        let right = recurseTree(currentNode.right, p, q) ? 1 : 0
        let mid = (currentNode === p || currentNode === q) ? 1 : 0

        if mid + left + right >= 2 {
            self.ans = currentNode
        }

        return (mid + left + right > 0)
    }

    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> TreeNode? {
        _ = recurseTree(root, p, q)
        return self.ans
    }
}

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

Задача: 212. Word Search II
Сложность: hard

Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.

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

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

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

2⃣Запуск обхода в глубину (Backtracking) с каждой ячейки:
Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).

3⃣Обход соседних ячеек:
В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.

😎 Решение:

class TrieNode {
    var children = [Character: TrieNode]()
    var word: String? = nil
}

class Solution {
    private var board: [[Character]] = []
    private var result = [String]()

    func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
        let root = TrieNode()
        for word in words {
            var node = root
            for letter in word {
                if node.children[letter] == nil {
                    node.children[letter] = TrieNode()
                }
                node = node.children[letter]!
            }
            node.word = word
        }

        self.board = board
        for row in 0..<board.count {
            for col in 0..<board[0].count {
                if root.children[board[row][col]] != nil {
                    backtracking(row, col, root)
                }
            }
        }

        return result
    }

    private func backtracking(_ row: Int, _ col: Int, _ parent: TrieNode) {
        let letter = board[row][col]
        guard let currNode = parent.children[letter] else { return }

        if let word = currNode.word {
            result.append(word)
            currNode.word = nil
        }

        board[row][col] = "#"

        let rowOffset = [-1, 0, 1, 0]
        let colOffset = [0, 1, 0, -1]
        for i in 0..<4 {
            let newRow = row + rowOffset[i]
            let newCol = col + colOffset[i]
            if newRow >= 0, newRow < board.count, newCol >= 0, newCol < board[0].count, currNode.children[board[newRow][newCol]] != nil {
                backtracking(newRow, newCol, currNode)
            }
        }

        board[row][col] = letter

        if currNode.children.isEmpty {
            parent.children[letter] = nil
        }
    }
}

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

Задача: 590. N-ary Tree Postorder Traversal
Сложность: easy

Дано корневое дерево с n-арной структурой, верните обход дерева в постфиксном порядке для значений его узлов.

Сериализация входных данных n-арного дерева представлена в обходе уровней. Каждая группа детей разделяется значением null (см. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

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

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

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

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

😎 Решение:

class Node {
    var val: Int
    var children: [Node]
    init(_ val: Int) {
        self.val = val
        self.children = []
    }
}

class Solution {
    func postorder(_ root: Node?) -> [Int] {
        guard let root = root else { return [] }
        var stack: [Node] = [root]
        var output: [Int] = []
        
        while !stack.isEmpty {
            let node = stack.removeLast()
            output.insert(node.val, at: 0)
            for child in node.children {
                stack.append(child)
            }
        }
        return output
    }
}

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

Задача: 605. Can Place Flowers
Сложность: easy

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

Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

class Solution {
    func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
        var flowerbed = flowerbed
        var count = 0
        for i in 0..<flowerbed.count {
            if flowerbed[i] == 0 {
                let emptyLeft = i == 0 || flowerbed[i - 1] == 0
                let emptyRight = i == flowerbed.count - 1 || flowerbed[i + 1] == 0
                if emptyLeft && emptyRight {
                    flowerbed[i] = 1
                    count += 1
                }
            }
        }
        return count >= n
    }
}

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

Задача: 436. Find Right Interval
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.

Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.

Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.

Пример:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

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

1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.

2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.

3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.

😎 Решение:

class Solution {
    func findRightInterval(_ intervals: [[Int]]) -> [Int] {
        var endIntervals = intervals
        var hash = [Int: Int]()
        for i in 0..<intervals.count {
            hash[intervals[i][0]] = i
        }
        intervals.sort { $0[0] < $1[0] }
        endIntervals.sort { $0[1] < $1[1] }
        var j = 0
        var res = [Int](repeating: 0, count: intervals.count)
        for i in 0..<endIntervals.count {
            while j < intervals.count && intervals[j][0] < endIntervals[i][1] {
                j += 1
            }
            res[hash[endIntervals[i][0]]!] = j == intervals.count ? -1 : hash[intervals[j][0]]!
        }
        return res
    }
}

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

Задача: 1338. Reduce Array Size to The Half
Сложность: medium

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

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

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

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

2⃣Отсортировать список подсчета в порядке убывания.

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

😎 Решение:

class Solution {
    func minSetSize(_ arr: [Int]) -> Int {
        var arr = arr
        arr.sort()
        
        var counts: [Int] = []
        var currentRun = 1
        for i in 1..<arr.count {
            if arr[i] == arr[i - 1] {
                currentRun += 1
                continue
            }
            counts.append(currentRun)
            currentRun = 1
        }
        counts.append(currentRun)
        
        counts.sort(by: >)
        
        var numbersRemovedFromArr = 0
        var setSize = 0
        for count in counts {
            numbersRemovedFromArr += count
            setSize += 1   
            if numbersRemovedFromArr >= arr.count / 2 {
                break
            }
        }
        
        return setSize
    }
}

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