Задача: 39. Combination Sum
Сложность: medium

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

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

Тестовые случаи сгенерированы таким образом, что количество уникальных комбинаций, дающих в сумме target, меньше 150 комбинаций для данного ввода.

Пример:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

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

1⃣Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии.
Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов.
Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же.

2⃣Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список.
Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе.

3⃣Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n].
Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами.
Конкретно, мы добавляем текущего кандидата в комбинацию.
С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate.
Для следующего исследования мы все еще начинаем с текущего курсора start.
В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации.

😎 Решение:

class Solution {
    func backtrack(_ remain: Int, _ comb: inout [Int], _ start: Int, _ candidates: [Int], _ results: inout [[Int]]) {
        if remain == 0 {
            results.append(comb)
            return
        } else if remain < 0 {
            return
        }

        for i in start..<candidates.count {
            comb.append(candidates[i])
            backtrack(remain - candidates[i], &comb, i, candidates, &results)
            comb.removeLast()
        }
    }

    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var results = [[Int]]()
        var comb = [Int]()

        backtrack(target, &comb, 0, candidates, &results)
        return results
    }
}

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

Задача: 254. Factor Combinations
Сложность: medium

Числа можно рассматривать как произведение их множителей.

Например, 8 = 2 x 2 x 2 = 2 x 4.
Дано целое число n, верните все возможные комбинации его множителей. Вы можете вернуть ответ в любом порядке.

Обратите внимание, что множители должны быть в диапазоне [2, n - 1].

Пример:

Input: n = 1
Output: []

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

1⃣Определите вспомогательную функцию backtracking, которая принимает два параметра: factors (список множителей) и ans (список списков для сохранения всех комбинаций множителей). Начните вызов backtracking с factors, содержащим только n, и пустым списком ans.

2⃣Основная логика функции backtracking:
Если размер factors больше 1, добавьте его копию в ans, так как это одно из желаемых решений.
Получите последний элемент factors (lastFactor) и удалите его из factors.
Если factors пуст, итерируйте i от 2. В противном случае, итерируйте i от последнего значения в factors. Итерируйте, пока i <= lastFactor / i.
Для каждого i, если lastFactor % i == 0, добавьте i и lastFactor / i в factors и вызовите backtracking(factors, ans).
Восстановите список (откат) factors, удалив последние два элемента из factors.
Восстановите список (откат) factors, добавив обратно lastFactor.

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

😎 Решение:

class Solution {
    private func backtracking(_ factors: inout [Int], _ ans: inout [[Int]]) {
        if factors.count > 1 {
            ans.append(factors)
        }
        let lastFactor = factors.removeLast()
        for i in (factors.isEmpty ? 2 : factors.last!)...lastFactor {
            if i * i > lastFactor { break }
            if lastFactor % i == 0 {
                factors.append(i)
                factors.append(lastFactor / i)
                backtracking(&factors, &ans)
                factors.removeLast()
                factors.removeLast()
            }
        }
        factors.append(lastFactor)
    }

    func getFactors(_ n: Int) -> [[Int]] {
        var ans: [[Int]] = []
        var factors: [Int] = [n]
        backtracking(&factors, &ans)
        return ans
    }
}

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

Задача: 1416. Restore The Array
Сложность: hard

Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей.

Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

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

1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x).

2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе:
Если s[start] == 0, вернуть 0.
Если start = m, вернуть 1.
Инициализировать count = 0, чтобы считать количество возможных массивов.
Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1).
Обновить dp[start] значением dfs(start).

3⃣Вернуть dfs(0).

😎 Решение:

class Solution {
    let mod = 1_000_000_007

    func dfs(_ dp: inout [Int], _ start: Int, _ s: String, _ k: Int) -> Int {
        if dp[start] != 0 {
            return dp[start]
        }
        if start == s.count {
            return 1
        }
        if s[s.index(s.startIndex, offsetBy: start)] == "0" {
            return 0
        }
        
        var count = 0
        for end in start..<s.count {
            let startIndex = s.index(s.startIndex, offsetBy: start)
            let endIndex = s.index(s.startIndex, offsetBy: end + 1)
            let currNumber = String(s[startIndex..<endIndex])
            if Int(currNumber)! > k {
                break
            }
            count = (count + dfs(&dp, end + 1, s, k)) % mod
        }
        
        dp[start] = count
        return count
    }

    func numberOfArrays(_ s: String, _ k: Int) -> Int {
        var dp = Array(repeating: 0, count: s.count + 1)
        return dfs(&dp, 0, s, k)
    }
}

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

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

2⃣Определение границ компонента:
Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет.

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

class Solution {
    func colorBorder(_ grid: [[Int]], _ row: Int, _ col: Int, _ color: Int) -> [[Int]] {
        var grid = grid
        let m = grid.count, n = grid[0].count
        let original_color = grid[row][col]
        var visited = Set<[Int]>()
        var borders = [[Int]]()

        func dfs(_ r: Int, _ c: Int) {
            visited.insert([r, c])
            var is_border = false
            for (dr, dc) in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
                let nr = r + dr, nc = c + dc
                if nr >= 0 && nr < m && nc >= 0 && nc < n {
                    if !visited.contains([nr, nc]) {
                        if grid[nr][nc] == original_color {
                            dfs(nr, nc)
                        } else {
                            is_border = true
                        }
                    }
                } else {
                    is_border = true
                }
            }
            if is_border || r == 0 || r == m - 1 || c == 0 || c == n - 1 {
                borders.append([r, c])
            }
        }

        dfs(row, col)
        for border in borders {
            grid[border[0]][border[1]] = color
        }

        return grid
    }
}

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

Задача: 939. Minimum Area Rectangle
Сложность: medium

Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0.

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    func minAreaRect(_ points: [[Int]]) -> Int {
        var pointSet = Set(points.map { "\($0[0]),\($0[1])" })
        var minArea = Int.max
        
        for i in 0..<points.count {
            for j in i+1..<points.count {
                let x1 = points[i][0], y1 = points[i][1]
                let x2 = points[j][0], y2 = points[j][1]
                if x1 != x2 && y1 != y2 && pointSet.contains("\(x1),\(y2)") && pointSet.contains("\(x2),\(y1)") {
                    minArea = min(minArea, abs(x2 - x1) * abs(y2 - y1))
                }
            }
        }
        
        return minArea == Int.max ? 0 : minArea
    }
}

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

Задача: 363. Max Sum of Rectangle No Larger Than K
Сложность: hard

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

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

Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

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

1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.

2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.

3⃣Вернуть максимальную найденную сумму.

😎 Решение:

class Solution {
    var result = Int.min

    func updateResult(_ nums: [Int], _ k: Int) {
        var sum = 0
        var sortedSum = Set<Int>()
        sortedSum.insert(0)

        for num in nums {
            sum += num
            if let x = sortedSum.first(where: { $0 >= sum - k }) {
                result = max(result, sum - x)
            }
            sortedSum.insert(sum)
        }
    }

    func maxSumSubmatrix(_ matrix: [[Int]], _ k: Int) -> Int {
        let rows = matrix.count
        let cols = matrix[0].count
        var rowSum = [Int](repeating: 0, count: cols)

        for i in 0..<rows {
            rowSum = [Int](repeating: 0, count: cols)
            for row in i..<rows {
                for col in 0..<cols {
                    rowSum[col] += matrix[row][col]
                }
                updateResult(rowSum, k)
                if result == k {
                    return result
                }
            }
        }
        return result
    }
}

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

Задача: 687. Longest Univalue Path
Сложность: medium

Дано корень бинарного дерева, верните длину самого длинного пути, на котором все узлы имеют одинаковое значение. Этот путь может проходить через корень или не проходить.

Длина пути между двумя узлами представлена количеством рёбер между ними.

Пример:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

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

1⃣Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла.

2⃣Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0.

3⃣Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans..

😎 Решение:

class Solution {
    var ans = 0

    func solve(_ root: TreeNode?, _ parent: Int) -> Int {
        guard let root = root else { return 0 }

        let left = solve(root.left, root.val)
        let right = solve(root.right, root.val)
        
        ans = max(ans, left + right)
        
        return root.val == parent ? max(left, right) + 1 : 0
    }

    func longestUnivaluePath(_ root: TreeNode?) -> Int {
        solve(root, -1)
        return ans
    }
}

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

Задача: 1282. Group the People Given the Group Size They Belong To
Сложность: medium

Есть n человек, которые разделены на неизвестное количество групп. Каждый человек имеет уникальный ID от 0 до n - 1.

Вам дан целочисленный массив groupSizes, где groupSizes[i] - это размер группы, в которой находится человек i. Например, если groupSizes[1] = 3, то человек 1 должен быть в группе размером 3.

Верните список групп таким образом, чтобы каждый человек i находился в группе размером groupSizes[i].

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

Пример:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

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

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

2⃣Итерируйте по массиву groupSizes, для каждого индекса i:
Вставьте индекс i в список szToGroup[groupSizes[i]].
Если размер списка становится равным groupSizes[i], добавьте его в ans и очистите массив для ключа groupSizes[i] в хэш-таблице szToGroup.

3⃣Верните ans.


😎 Решение:

class Solution {
    func groupThePeople(_ groupSizes: [Int]) -> [[Int]] {
        var ans = [[Int]]()
        var szToGroup = [Int: [Int]]()
        
        for i in 0..<groupSizes.count {
            let size = groupSizes[i]
            if szToGroup[size] == nil {
                szToGroup[size] = [Int]()
            }
            szToGroup[size]!.append(i)
            
            if szToGroup[size]!.count == size {
                ans.append(szToGroup[size]!)
                szToGroup[size] = [Int]()
            }
        }
        
        return ans
    }
}

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

Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy

Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false.

Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

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

2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.

3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.

😎 Решение:

class Solution {
    func kLengthApart(_ nums: [Int], _ k: Int) -> Bool {
        var count = k
        for num in nums {
            if num == 1 {
                if count < k {
                    return false
                }
                count = 0
            } else {
                count += 1
            }
        }
        return true
    }
}

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

Задача: 520. Detect Capital
Сложность: easy

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

class Solution {
    func detectCapitalUse(_ word: String) -> Bool {
        let pattern = "^[A-Z]*$|^[a-z]*$|^[A-Z][a-z]*$"
        let regex = try! NSRegularExpression(pattern: pattern)
        let range = NSRange(location: 0, length: word.utf16.count)
        return regex.firstMatch(in: word, options: [], range: range) != nil
    }
}

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

Задача: 1675. Minimize Deviation in Array
Сложность: hard

Вам дан массив nums из n положительных целых чисел.

Вы можете выполнять два типа операций над любым элементом массива любое количество раз:
Если элемент четный, разделите его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на последнем элементе, и массив станет [1,2,3,2].
Если элемент нечетный, умножьте его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на первом элементе, и массив станет [2,2,3,4].
Отклонение массива — это максимальная разница между любыми двумя элементами в массиве.

Верните минимальное отклонение, которое может иметь массив после выполнения некоторого числа операций.

Пример:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

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

1⃣Инициализируйте max-heap под названием evens. Если элемент массива четный, добавьте его в evens; если элемент нечетный, умножьте его на 2 и добавьте в evens. Одновременно отслеживайте минимальный элемент в evens.

2⃣Извлекайте максимальный элемент из evens, обновляйте минимальное отклонение, используя максимальный элемент и текущий минимальный элемент. Если максимальный элемент четный, делите его на 2 и снова добавляйте в evens.

3⃣Повторяйте шаг 2 до тех пор, пока максимальный элемент в evens не станет нечетным. Верните минимальное отклонение.

😎 Решение:

class Solution {
    func minimumDeviation(_ nums: [Int]) -> Int {
        var evens = PriorityQueue<Int>(ascending: false)
        var minimum = Int.max
        
        for num in nums {
            if num % 2 == 0 {
                evens.push(num)
                minimum = min(minimum, num)
            } else {
                evens.push(num * 2)
                minimum = min(minimum, num * 2)
            }
        }
        
        var minDeviation = Int.max
        
        while let currentValue = evens.pop() {
            minDeviation = min(minDeviation, currentValue - minimum)
            if currentValue % 2 == 0 {
                evens.push(currentValue / 2)
                minimum = min(minimum, currentValue / 2)
            } else {
                break
            }
        }
        
        return minDeviation
    }
}

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

Задача: 535. Encode and Decode TinyURL
Сложность: medium

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

Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.

Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

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

2⃣ Кодирование:
Сгенерируйте случайный 6-символьный код.
Если такой код уже существует в хэш-таблице, повторите генерацию.
Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице.
Верните полный короткий URL.

3⃣ Декодирование:
Удалите префикс короткого URL, чтобы получить код.
Используйте код для поиска длинного URL в хэш-таблице.
Верните длинный URL.

😎 Решение:

class Codec {
    private let alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    private var map = [String: String]()
    private var rand = SystemRandomNumberGenerator()
    
    private func getRand() -> String {
        var result = ""
        for _ in 0..<6 {
            result.append(alphabet.randomElement()!)
        }
        return result
    }
    
    func encode(_ longUrl: String) -> String {
        var key = getRand()
        while map[key] != nil {
            key = getRand()
        }
        map[key] = longUrl
        return "https://tinyurl.com/" + key
    }
    
    func decode(_ shortUrl: String) -> String {
        let key = String(shortUrl.dropFirst("https://tinyurl.com/".count))
        return map[key] ?? ""
    }
}

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

Задача: 239. Sliding Window Maximum
Сложность: hard

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

Верните максимальные значения скользящего окна.

Пример:

Input: nums = [1], k = 1
Output: [1]

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

1⃣Инициализация и заполнение первой части окна:
Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов.
Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента:
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]].

2⃣Сканирование оставшейся части массива:
Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента:
Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна.
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]].

3⃣Возвращение результата:
Верните список res, содержащий максимальные элементы для каждого скользящего окна.

😎 Решение:

class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var dq = [Int]()
        var res = [Int]()
        
        for i in 0..<k {
            while !dq.isEmpty && nums[i] >= nums[dq.last!] {
                dq.removeLast()
            }
            dq.append(i)
        }
        res.append(nums[dq.first!])
        
        for i in k..<nums.count {
            if dq.first == i - k {
                dq.removeFirst()
            }
            while !dq.isEmpty && nums[i] >= nums[dq.last!] {
                dq.removeLast()
            }
            dq.append(i)
            res.append(nums[dq.first!])
        }
        
        return res
    }
}

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

Задача: 747. Largest Number At Least Twice of Others
Сложность: easy

Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.

Пример:

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

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

1⃣Найдите максимальный элемент в массиве и его индекс.

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

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

😎 Решение:

func dominantIndex(_ nums: [Int]) -> Int {
    guard let maxVal = nums.max() else { return -1 }
    let maxIndex = nums.firstIndex(of: maxVal)!
    for num in nums {
        if num != maxVal && maxVal < 2 * num {
            return -1
        }
    }
    return maxIndex
}

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

Задача: 628. Maximum Product of Three Numbers
Сложность: easy

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

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

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

1⃣Отсортируйте массив nums.

2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива.

3⃣Верните максимальное из двух найденных произведений.

😎 Решение:

func maximumProduct(_ nums: [Int]) -> Int {
    let nums = nums.sorted()
    let n = nums.count
    let max1 = nums[n - 1] * nums[n - 2] * nums[n - 3]
    let max2 = nums[0] * nums[1] * nums[n - 1]
    return max(max1, max2)
}

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

Задача: 989. Add to Array-Form of Integer
Сложность: easy

Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.

Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.

Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

1⃣Инициализация переменных:
Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k).
Завести переменную carry для хранения переноса и инициализировать ее нулем.
Создать пустой массив result для хранения результата.

2⃣Сложение массивов:
Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry).
Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1.
Если сумма меньше 10, установите carry в 0.
Добавьте результат текущего сложения в массив result

3⃣Обработка оставшихся цифр и переноса:
Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом.
Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result.
Переверните массив result обратно и верните его.

😎 Решение:

func addToArrayForm(_ num: [Int], _ k: Int) -> [Int] {
    var num = num.reversed()
    var k = Array(String(k)).map { Int(String($0))! }.reversed()
    var carry = 0
    var result = [Int]()
    var i = 0
    
    while i < num.count || i < k.count || carry > 0 {
        let n = i < num.count ? num[i] : 0
        let m = i < k.count ? k[i] : 0
        let total = n + m + carry
        carry = total / 10
        result.append(total % 10)
        i += 1
    }
    
    return result.reversed()
}

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

Задача: 77. Combinations
Сложность: medium

Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].

Ответ можно вернуть в любом порядке.

Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

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

1⃣Инициализировать массив ответов ans и массив для построения комбинаций curr.

2⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:
Если длина curr равна k, добавить копию curr в ans и вернуться.
Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.
Итерировать num от firstNum до firstNum + available включительно.
Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.

3⃣Вызвать backtrack с изначально пустым curr и firstNum = 1.
Вернуть ans.

😎 Решение:

func combine(_ n: Int, _ k: Int) -> [[Int]] {
    var ans = [[Int]]()
    func backtrack(_ curr: inout [Int], _ firstNum: Int) {
        if curr.count == k {
            ans.append(curr)
            return
        }
        let need = k - curr.count
        let remain = n - firstNum + 1
        let available = remain - need
        for num in firstNum...(firstNum + available) {
            curr.append(num)
            backtrack(&curr, num + 1)
            curr.removeLast()
        }
    }
    var initial = [Int]()
    backtrack(&initial, 1)
    return ans
}

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

Задача: 737. Sentence Similarity II
Сложность: medium

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

func areSentencesSimilar(_ sentence1: [String], _ sentence2: [String], _ similarPairs: [[String]]) -> Bool {
    if sentence1.count != sentence2.count {
        return false
    }
    
    var graph = [String: [String]]()
    for pair in similarPairs {
        let (x, y) = (pair[0], pair[1])
        graph[x, default: []].append(y)
        graph[y, default: []].append(x)
    }
    
    func dfs(_ word1: String, _ word2: String, _ visited: inout Set<String>) -> Bool {
        if word1 == word2 {
            return true
        }
        visited.insert(word1)
        for neighbor in graph[word1, default: []] {
            if !visited.contains(neighbor) && dfs(neighbor, word2, &visited) {
                return true
            }
        }
        return false
    }
    
    for (w1, w2) in zip(sentence1, sentence2) {
        if w1 != w2 {
            var visited = Set<String>()
            if !dfs(w1, w2, &visited) {
                return false
            }
        }
    }
    
    return true
}

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

Задача: 1802. Maximum Value at a Given Index in a Bounded Array
Сложность: medium

Даны три положительных целых числа: n, index и maxSum. Вам нужно построить массив nums (индексация с нуля), который удовлетворяет следующим условиям:

- nums.length == n
- nums[i] является положительным целым числом, где 0 <= i < n.
- abs(nums[i] - nums[i+1]) <= 1, где 0 <= i < n-1.
- Сумма всех элементов массива nums не превышает maxSum.
- nums[index] максимально возможен.

Верните значение nums[index] в построенном массиве.

Обратите внимание, что abs(x) равно x, если x >= 0, и -x в противном случае.

Пример:

Input: n = 4, index = 2,  maxSum = 6
Output: 2

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

1⃣Определите функцию getSum(index, value) для вычисления минимальной суммы массива при условии, что nums[index] = value.

2⃣Инициализируйте диапазон поиска [left, right] значениями left = 1 и right = maxSum. Выполните бинарный поиск: вычислите mid = (left + right + 1) / 2 и проверьте, если getSum(index, mid) <= maxSum. Если условие выполняется, установите left = mid, иначе установите right = mid - 1.

3⃣Верните left по завершении бинарного поиска.

😎 Решение:

class Solution {
    private func getSum(_ index: Int, _ value: Int, _ n: Int) -> Int64 {
        var count: Int64 = 0
        if value > index {
            count += Int64(value + value - index) * Int64(index + 1) / 2
        } else {
            count += Int64(value + 1) * Int64(value) / 2 + Int64(index - value + 1)
        }
        if value >= n - index {
            count += Int64(value + value - n + 1 + index) * Int64(n - index) / 2
        } else {
            count += Int64(value + 1) * Int64(value) / 2 + Int64(n - index - value)
        }
        return count - Int64(value)
    }

    func maxValue(_ n: Int, _ index: Int, _ maxSum: Int) -> Int {
        var left = 1, right = maxSum
        while left < right {
            let mid = (left + right + 1) / 2
            if getSum(index, mid, n) <= maxSum {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return left
    }
}

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

Задача: 100. Same Tree
Сложность: easy

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они. Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.
Пример:
Input: p = [1,2,3], q = [1,2,3] Output: true

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

1⃣Если оба узла — nil, возвращаем true

2⃣Если один из них — nil, или значения не совпадают, возвращаем false

3⃣Рекурсивно проверяем левое и правое поддерево

😎 Решение:

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

class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }
        if p == nil || q == nil {
            return false
        }
        if p!.val != q!.val {
            return false
        }
        return isSameTree(p!.left, q!.left) && isSameTree(p!.right, q!.right)
    }
}

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