🚨 60 минут до финала

Через час мы закроем краудфандинг easyoffer 2.0
Это последний шанс вписаться в самые выгодные условия.

👉 https://planeta.ru/campaigns/easyoffer

Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

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

1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.

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

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

😎 Решение:

class Solution {
    func minRemoveToMakeValid(_ s: String) -> String {
        var stack = [Int]()
        var s = Array(s)
        for i in 0..<s.count {
            if s[i] == "(" {
                stack.append(i)
            } else if s[i] == ")" {
                if !stack.isEmpty {
                    stack.removeLast()
                } else {
                    s[i] = "*"
                }
            }
        }
        while !stack.isEmpty {
            s[stack.removeLast()] = "*"
        }
        return String(s).replacingOccurrences(of: "*", with: "")
    }
}

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

Задача: 1122. Relative Sort Array
Сложность: easy

Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1.

Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания.

Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

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

1⃣Инициализация и подсчёт:
Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов.
Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1.

2⃣Заполнение countMap и remaining:
Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining.

3⃣Формирование результирующего массива:
Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap.
Отсортируйте массив remaining и добавьте его элементы в result.
Верните result в виде массива.

😎 Решение:

class Solution {
    func relativeSortArray(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
        var countMap = [Int: Int]()
        var remaining = [Int]()
        var result = [Int]()

        for value in arr2 {
            countMap[value] = 0
        }

        for value in arr1 {
            if let _ = countMap[value] {
                countMap[value]! += 1
            } else {
                remaining.append(value)
            }
        }

        remaining.sort()

        for value in arr2 {
            if let count = countMap[value] {
                for _ in 0..<count {
                    result.append(value)
                }
            }
        }

        result.append(contentsOf: remaining)
        return result
    }
}

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

Задача: 76. Minimum Window Substring
Сложность: hard

Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "".

Тестовые примеры будут сформированы таким образом, что ответ будет уникальным.

Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

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

1⃣Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S.

2⃣Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.

3⃣Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.

😎 Решение:

func minWindow(_ s: String, _ t: String) -> String {
    if s.isEmpty || t.isEmpty {
        return ""
    }

    var dictT = [Character: Int]()
    for char in t {
        dictT[char, default: 0] += 1
    }

    let required = dictT.count
    var l = 0
    var r = 0
    var formed = 0
    var windowCounts = [Character: Int]()
    var ans = (-1, 0, 0)
    
    let sChars = Array(s)
    
    while r < sChars.count {
        let c = sChars[r]
        windowCounts[c, default: 0] += 1

        if let tCount = dictT[c], windowCounts[c] == tCount {
            formed += 1
        }

        while l <= r && formed == required {
            let c = sChars[l]

            if ans.0 == -1 || r - l + 1 < ans.0 {
                ans = (r - l + 1, l, r)
            }

            windowCounts[c, default: 0] -= 1
            if let tCount = dictT[c], windowCounts[c] < tCount {
                formed -= 1
            }
            l += 1
        }
        r += 1
    }

    if ans.0 == -1 {
        return ""
    } else {
        let startIndex = s.index(s.startIndex, offsetBy: ans.1)
        let endIndex = s.index(s.startIndex, offsetBy: ans.2)
        return String(s[startIndex...endIndex])
    }
}

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

Задача: 1162. As Far from Land as Possible
Сложность: medium

Дана сетка размером n x n, содержащая только значения 0 и 1, где 0 представляет воду, а 1 представляет землю. Найдите ячейку с водой, такое что её расстояние до ближайшей ячейки с землёй максимально, и верните это расстояние. Если в сетке нет ни земли, ни воды, верните -1.

Расстояние, используемое в этой задаче, - это манхэттенское расстояние: расстояние между двумя ячейками (x0, y0) и (x1, y1) равно |x0 - x1| + |y0 - y1|.

Пример:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

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

1⃣Итерируйте по матрице и вставьте координаты ячеек с землёй в очередь. Инициализируйте переменную distance значением -1 для хранения текущего шага обхода в ширину (BFS). Также создайте копию матрицы visited для пометки ячеек с водой как посещённые, чтобы не вставлять их снова в очередь.

2⃣Выполните BFS: Обходите текущие элементы в очереди и для каждого элемента проверяйте координаты в четырёх направлениях, являются ли они ячейками с водой (0). Если да, вставьте их в очередь и измените их на ячейки с землёй (1) в матрице visited. После каждого пройденного уровня (внутренний цикл while завершён), увеличьте переменную distance.

3⃣Повторяйте, пока очередь не станет пустой. Верните значение distance. Если оно равно 0, это означает, что не было ячеек с водой и обход завершился после первого шага, поэтому верните -1. Если в матрице не было ячеек с землёй, цикл while вообще не начнётся, и переменная distance останется с начальным значением (-1).

😎 Решение

class Solution {
    let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    func maxDistance(_ grid: [[Int]]) -> Int {
        var visited = grid
        var q = [(Int, Int)]()
        
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                if grid[i][j] == 1 {
                    q.append((i, j))
                }
            }
        }
        
        var distance = -1
        while !q.isEmpty {
            let qSize = q.count
            for _ in 0..<qSize {
                let landCell = q.removeFirst()
                for dir in directions {
                    let x = landCell.0 + dir.0
                    let y = landCell.1 + dir.1
                    
                    if x >= 0 && y >= 0 && x < grid.count && y < grid[0].count && visited[x][y] == 0 {
                        visited[x][y] = 1
                        q.append((x, y))
                    }
                }
            }
            distance += 1
        }
        
        return distance == 0 ? -1 : distance
    }
}

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

Задача: 149. Max Points on a Line
Сложность: Hard

Дан массив точек, где points[i] = [xi, yi] представляет точку на плоскости XY. Верните максимальное количество точек, которые лежат на одной прямой.

Пример:

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

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

1⃣Итерация по всем точкам:
Проходим по всем точкам массива. Пусть текущая точка будет points[i]. Создаём хеш-таблицу cnt для подсчёта углов.

2⃣Расчёт углов и подсчёт:
Для каждой точки j, не равной i, рассчитываем арктангенс вектора points[j] - points[i] и добавляем это значение в хеш-таблицу.

3⃣Обновление ответа:
Пусть k будет максимальным количеством вхождений какого-либо значения угла в хеш-таблице. Обновляем ответ значением k + 1 (прибавляем 1, потому что точка points[i] также лежит на этой линии, и её нужно включить в ответ).

😎 Решение:

class Solution {
    func maxPoints(_ points: [[Int]]) -> Int {
        let n = points.count
        if n == 1 {
            return 1
        }
        var result = 2
        for i in 0..<n {
            var cnt = [Double: Int]()
            for j in 0..<n {
                if j != i {
                    let dy = Double(points[j][1] - points[i][1])
                    let dx = Double(points[j][0] - points[i][0])
                    let angle = atan2(dy, dx)
                    cnt[angle, default: 0] += 1
                }
            }
            for (_, count) in cnt {
                result = max(result, count + 1)
            }
        }
        return result
    }
}

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

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

Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).

Пример:

Input: nums = [3,6,9,12]
Output: 4

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

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

2⃣Заполнение массива dp:
Пройдитесь по каждому элементу массива nums.
Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].
Обновите dp[i][d] на основе значения dp[j][d].

3⃣Поиск максимальной длины:
Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d].

😎 Решение:

class Solution {
    func longestArithSeqLength(_ nums: [Int]) -> Int {
        if nums.isEmpty { return 0 }
        
        var dp = Array(repeating: [Int: Int](), count: nums.count)
        var max_length = 0
        
        for i in 0..<nums.count {
            for j in 0..<i {
                let diff = nums[i] - nums[j]
                if let length = dp[j][diff] {
                    dp[i][diff] = length + 1
                } else {
                    dp[i][diff] = 2 // Start a new sequence
                }
                max_length = max(max_length, dp[i][diff]!)
            }
        }
        
        return max_length
    }
}

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

Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

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

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

2⃣Используя родительскую информацию, найдем путь от каждого региона до корня.

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

😎 Решение:

class Solution {
    func findSmallestRegion(_ regions: [[String]], _ region1: String, _ region2: String) -> String {
        var parent = [String: String]()

        for regionList in regions {
            for i in 1..<regionList.count {
                parent[regionList[i]] = regionList[0]
            }
        }

        var ancestors1 = Set<String>()
        var r1 = region1
        while let p = parent[r1] {
            ancestors1.insert(r1)
            r1 = p
        }
        ancestors1.insert(r1)

        var r2 = region2
        while !ancestors1.contains(r2) {
            r2 = parent[r2]!
        }

        return r2
    }
}

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

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.

Пример:

Input: n = 2, start = 3
Output: [3,2,0,1]

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

1⃣Генерация Грей-кода:
Генерация Грей-кода для чисел от 0 до 2𝑛−1

2⃣Определение начальной позиции:
Находим индекс числа start в последовательности Грей-кода.

3⃣Построение перестановки:
Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду.

😎 Решение:

func grayCode(_ n: Int) -> [Int] {
    return (0..<1<<n).map { $0 ^ ($0 >> 1) }
}

func circularPermutation(_ n: Int, _ start: Int) -> [Int] {
    let gray = grayCode(n)
    if let startIndex = gray.firstIndex(of: start) {
        return Array(gray[startIndex...] + gray[..<startIndex])
    }
    return []
}

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

Задача: 226. Invert Binary Tree
Сложность: easy

Дан корень бинарного дерева, инвертируйте дерево и верните его корень.

Пример:

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

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

1⃣Рекурсивная инверсия поддеревьев:
Если текущий узел (root) пустой, возвращаем null.
Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right.
Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left.

2⃣Обмен поддеревьев:
Устанавливаем левое поддерево текущего узла равным правому поддереву.
Устанавливаем правое поддерево текущего узла равным левому поддереву.

3⃣Возврат корня:
Возвращаем текущий узел (root) как новый корень инвертированного дерева.

😎 Решение:

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

class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else {
            return nil
        }
        let right = invertTree(root.right)
        let left = invertTree(root.left)
        root.left = right
        root.right = left
        return root
    }
}

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

Задача: 250. Count Univalue Subtrees
Сложность: medium

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

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

Пример:

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

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

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

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

3⃣Верните count.

😎 Решение:

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

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

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

Задача: 660. Remove 9
Сложность: hard

Начните с целого числа 1, уберите любое число, которое содержит 9, такое как 9, 19, 29...

Теперь у вас будет новая последовательность целых чисел [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...].

Дано целое число n, верните n-е (начиная с 1) целое число в новой последовательности.

Пример:

Input: n = 9
Output: 10

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

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

2⃣Итерация и проверка:
Последовательно увеличивайте число и проверяйте, содержит ли оно цифру 9.
Если не содержит, увеличьте счетчик.

3⃣Поиск n-го числа:
Продолжайте процесс до тех пор, пока не найдете n-е число, не содержащее цифру 9.

😎 Решение:

class Solution {
    func newInteger(_ n: Int) -> Int {
        var count = 0
        var num = 0
        while count < n {
            num += 1
            if !String(num).contains("9") {
                count += 1
            }
        }
        return num
    }
}

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

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

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

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

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

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

class Solution {
    func isPossible(_ target: [Int]) -> Bool {
        var target = target
        var total = target.reduce(0, +)
        target.sort(by: >)
        
        while let maxVal = target.first, maxVal > 1 {
            total -= maxVal
            if maxVal < total || total == 0 || maxVal % total == 0 {
                return false
            }
            target[0] = maxVal % total
            total += target[0]
            target.sort(by: >)
        }
        return true
    }
}

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

Задача: 405. Convert a Number to Hexadecimal
Сложность: easy

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

Пример:

Input: num = 26
Output: "1a"

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

1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF.

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

3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0".

😎 Решение:

func toHex(_ num: Int) -> String {
    if num == 0 {
        return "0"
    }
    let hexChars = "0123456789abcdef"
    var num = num
    if num < 0 {
        num += 1 << 32
    }
    var result = ""
    while num > 0 {
        result.append(hexChars[hexChars.index(hexChars.startIndex, offsetBy: num % 16)])
        num /= 16
    }
    return String(result.reversed())
}

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

Задача: 1009. Complement of Base 10 Integer
Сложность: easy

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5
Output: 2

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

1⃣Определение длины двоичного представления:
Найдите длину двоичного представления числа n.

2⃣Создание маски:
Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

3⃣Вычисление дополнения:
Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа.

😎 Решение:

class Solution {
    func findComplement(_ num: Int) -> Int {
        let length = Int.bitWidth - num.leadingZeroBitCount
        let mask = (1 << length) - 1
        return num ^ mask
    }
}

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

Задача: 426. Convert Binary Search Tree to Sorted Doubly Linked List
Сложность: medium

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

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

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

Пример:

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

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

1⃣Инициализируйте первые и последние узлы как null.

2⃣Вызовите стандартную вспомогательную рекурсивную функцию helper(root):
Если узел не равен null:
Вызовите рекурсию для левого поддерева helper(node.left).
Если последний узел не равен null, свяжите последний узел и текущий узел.
Иначе инициализируйте первый узел.
Пометьте текущий узел как последний: last = node.
Вызовите рекурсию для правого поддерева helper(node.right).

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

😎 Решение:

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

class Solution {
    var first: Node? = nil
    var last: Node? = nil
    
    func helper(_ node: Node?) {
        guard let node = node else { return }
        
        helper(node.left)
        
        if let last = last {
            last.right = node
            node.left = last
        } else {
            first = node
        }
        
        last = node
        
        helper(node.right)
    }
    
    func treeToDoublyList(_ root: Node?) -> Node? {
        guard let root = root else { return nil }
        
        helper(root)
        
        last?.right = first
        first?.left = last
        
        return first
    }
}

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

Задача: 85. Maximal Rectangle
Сложность: hard

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

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

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

1⃣Вычисление максимальной ширины прямоугольника для каждой координаты: Для каждой ячейки в каждой строке сохраняем количество последовательных единиц. При прохождении по строке обновляем максимально возможную ширину в этой точке, используя формулу row[i] = row[i - 1] + 1, если row[i] == '1'.

2⃣Определение максимальной площади прямоугольника с нижним правым углом в данной точке: При итерации вверх по столбцу максимальная ширина прямоугольника от исходной точки до текущей точки является минимальным значением среди всех максимальных ширин, с которыми мы сталкивались. Используем формулу maxWidth = min(maxWidth, widthHere) и curArea = maxWidth * (currentRow - originalRow + 1), затем обновляем maxArea = max(maxArea, curArea).

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

😎 Решение:

func maximalRectangle(matrix: [[Character]]) -> Int {
    if matrix.isEmpty { return 0 }
    var maxArea = 0
    var dp = Array(repeating: Array(repeating: 0, count: matrix[0].count), count: matrix.count)

    for i in 0..<matrix.count {
        for j in 0..<matrix[0].count {
            if matrix[i][j] == "1" {
                dp[i][j] = j == 0 ? 1 : dp[i][j-1] + 1
                var width = dp[i][j]
                for k in stride(from: i, through: 0, by: -1) {
                    width = min(width, dp[k][j])
                    maxArea = max(maxArea, width * (i - k + 1))
                }
            }
        }
    }
    return maxArea
}

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

Задача: 336. Palindrome Pairs
Сложность: hard

Вам дан массив уникальных строк words, индексируемый с 0.

Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.

Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

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

2⃣ Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

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

😎 Решение:

class Solution {
    func palindromePairs(_ words: [String]) -> [[Int]] {
        var pairs = [[Int]]()
        
        for i in 0..<words.count {
            for j in 0..<words.count {
                if i == j { continue }
                let combined = words[i] + words[j]
                if combined == String(combined.reversed()) {
                    pairs.append([i, j])
                }
            }
        }
        
        return pairs
    }
}

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