اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Swift | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر1 349
مشترکین
-224 ساعت
-47 روز
-1630 روز
آرشیو پست ها
1 348
Задача: 724. Find Pivot Index
Сложность: easy
Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.
Пример:
Input: nums = [1,7,3,6,5,6] Output: 3👨💻 Алгоритм: 1⃣Вычислите сумму всех элементов массива. 2⃣Пройдите по массиву, вычисляя текущую сумму элементов слева и проверяя, равна ли она разности между общей суммой и текущей суммой справа. 3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1. 😎 Решение:
func pivotIndex(_ nums: [Int]) -> Int {
let totalSum = nums.reduce(0, +)
var leftSum = 0
for i in 0..<nums.count {
if leftSum == totalSum - leftSum - nums[i] {
return i
}
leftSum += nums[i]
}
return -1
}1 348
Задача: 1260. Shift 2D Grid
Сложность: easy
Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз.
Пример:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[9,1,2],[3,4,5],[6,7,8]]👨💻 Алгоритм: 1⃣Преобразовать двумерную сетку в одномерный массив. 2⃣Выполнить сдвиг элементов в одномерном массиве. 3⃣Преобразовать одномерный массив обратно в двумерную сетку. 😎 Решение:
class Solution {
func shiftGrid(_ grid: [[Int]], _ k: Int) -> [[Int]] {
let m = grid.count
let n = grid[0].count
let total = m * n
var k = k % total
if k == 0 {
return grid
}
var flatArray = [Int]()
for row in grid {
flatArray.append(contentsOf: row)
}
let newArray = Array(flatArray[total - k..<total]) + Array(flatArray[0..<total - k])
var newGrid = [[Int]]()
for i in 0..<m {
let newRow = Array(newArray[i * n..<(i + 1) * n])
newGrid.append(newRow)
}
return newGrid
}
}1 348
Задача: 526. Beautiful Arrangement
Сложность: medium
Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.
Пример:
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1
👨💻 Алгоритм:
1⃣ Инициализация и подготовка массива:
Создайте массив чисел от 1 до N и инициализируйте счетчик красивых перестановок.
Создайте функцию для перестановки элементов массива.
2⃣ Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.
3⃣ Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.
😎 Решение:
class Solution {
var count = 0
func countArrangement(_ N: Int) -> Int {
var nums = Array(1...N)
permute(&nums, 0)
return count
}
func permute(_ nums: inout [Int], _ l: Int) {
if l == nums.count {
count += 1
}
for i in l..<nums.count {
nums.swapAt(i, l)
if nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0 {
permute(&nums, l + 1)
}
nums.swapAt(i, l)
}
}
}1 348
Задача: 99. Recover Binary Search Tree
Сложность: medium
Вам дан корень бинарного дерева поиска (BST), в котором значения ровно двух узлов дерева были поменяны местами по ошибке. Восстановите дерево, не изменяя его структуру.
Пример:
Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.👨💻 Алгоритм: 1⃣Создайте симметричный обход дерева. Это должен быть почти отсортированный список, в котором поменяны местами только два элемента. 2⃣Определите два поменянных местами элемента x и y в почти отсортированном массиве за линейное время. 3⃣Повторно пройдите по дереву. Измените значение x на y и значение y на x. 😎 Решение:
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 {
private var prev: TreeNode?
private var first: TreeNode?
private var second: TreeNode?
private func inorder(_ root: TreeNode?) {
guard let root = root else { return }
inorder(root.left)
if let prev = prev, prev.val > root.val {
if first == nil {
first = prev
}
second = root
}
prev = root
inorder(root.right)
}
func recoverTree(_ root: TreeNode?) {
inorder(root)
if let first = first, let second = second {
swap(&first.val, &second.val)
}
}
}1 348
Задача: 318. Maximum Product of Word Lengths
Сложность: medium
Дан массив строк
words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.
Пример:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".👨💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:
class Solution {
func maxProduct(_ words: [String]) -> Int {
let n = words.count
var masks = [Int](repeating: 0, count: n)
var lens = [Int](repeating: 0, count: n)
for i in 0..<n {
var bitmask = 0
for ch in words[i] {
bitmask |= 1 << (ch.asciiValue! - Character("a").asciiValue!)
}
masks[i] = bitmask
lens[i] = words[i].count
}
var maxVal = 0
for i in 0..<n {
for j in i+1..<n {
if masks[i] & masks[j] == 0 {
maxVal = max(maxVal, lens[i] * lens[j])
}
}
}
return maxVal
}
}1 348
Задача: 672. Bulb Switcher II
Сложность: medium
Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.
Пример:
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2class Solution {
func flipLights(_ n: Int, _ m: Int) -> Int {
var seen = Set<Int>()
let n = min(n, 6)
let shift = max(0, 6 - n)
for cand in 0..<16 {
let bcount = cand.nonzeroBitCount
if bcount % 2 == m % 2 && bcount <= m {
var lights = 0
if ((cand >> 0) & 1) > 0 { lights ^= 0b111111 >> shift }
if ((cand >> 1) & 1) > 0 { lights ^= 0b010101 >> shift }
if ((cand >> 2) & 1) > 0 { lights ^= 0b101010 >> shift }
if ((cand >> 3) & 1) > 0 { lights ^= 0b100100 >> shift }
seen.insert(lights)
}
}
return seen.count
}
}1 348
Задача: 112. Path Sum
Сложность: easy
Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum.
Лист — это узел без детей.
Пример:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown.👨💻 Алгоритм: 1⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val. 2⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом. 3⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами. 😎 Решение:
class Solution {
func hasPathSum(_ root: TreeNode?, _ sum: Int) -> Bool {
guard let root = root else { return false }
var nodeStack = [TreeNode]()
var sumStack = [Int]()
nodeStack.append(root)
sumStack.append(sum - root.val)
while !nodeStack.isEmpty {
let node = nodeStack.removeLast()
let currSum = sumStack.removeLast()
if node.left == nil && node.right == nil && currSum == 0 {
return true
}
if let right = node.right {
nodeStack.append(right)
sumStack.append(currSum - right.val)
}
if let left = node.left {
nodeStack.append(left)
sumStack.append(currSum - left.val)
}
}
return false
}
}1 348
Задача: 984. String Without AAA or BBB
Сложность: medium
Даны два целых числа a и b, верните любую строку s, такую что:
s имеет длину a + b и содержит ровно a букв 'a' и ровно b букв 'b'.
Подстрока 'aaa' не встречается в s.
Подстрока 'bbb' не встречается в s.
Пример:
Input: a = 4, b = 1 Output: "aabaa"👨💻 Алгоритм: 1⃣Инициализация переменных: Завести пустую строку s и переменные a_count и b_count для отслеживания оставшихся 'a' и 'b' соответственно. 2⃣Создание строки: Добавляйте символы в строку s, попеременно добавляя 'a' и 'b', чтобы избегать подстрок 'aaa' и 'bbb'. Если в строке подряд уже два символа 'a' и осталось ещё 'b', добавьте 'b' и наоборот. Если оба символа возможны для добавления, выбирайте тот, которого осталось больше. 3⃣Добавление оставшихся символов: После основной логики добавления символов, добавьте оставшиеся 'a' или 'b' в конец строки, если они остались. 😎 Решение:
func strWithout3a3b(_ a: Int, _ b: Int) -> String {
var result = [Character]()
var a = a, b = b
while a > 0 || b > 0 {
if result.count >= 2 && result[result.count - 1] == result[result.count - 2] {
if result.last! == "a" {
result.append("b")
b -= 1
} else {
result.append("a")
a -= 1
}
} else {
if a >= b {
result.append("a")
a -= 1
} else {
result.append("b")
b -= 1
}
}
}
return String(result)
}1 348
Задача: 1004. Max Consecutive Ones III
Сложность: medium
Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.
Пример:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6👨💻 Алгоритм: 1⃣Инициализация оконного подхода: Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне. 2⃣Перемещение правого указателя и обновление окна: Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k). 3⃣Подсчет максимального количества последовательных единиц: На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом. 😎 Решение:
class Solution {
func longestOnes(_ nums: [Int], _ k: Int) -> Int {
var left = 0
var maxOnes = 0
var zeroCount = 0
for right in 0..<nums.count {
if nums[right] == 0 {
zeroCount += 1
}
while zeroCount > k {
if nums[left] == 0 {
zeroCount -= 1
}
left += 1
}
maxOnes = max(maxOnes, right - left + 1)
}
return maxOnes
}
}1 348
Задача: 942. DI String Match
Сложность: easy
Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.
Пример:
Input: s = "IDID" Output: [0,4,1,3,2]👨💻 Алгоритм: 1⃣Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке. 2⃣Создать массив perm длиной n + 1. Пройти по строке s: Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low. Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high. Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm. 3⃣Вернуть массив perm. 😎 Решение:
class Solution {
func diStringMatch(_ s: String) -> [Int] {
let n = s.count
var low = 0, high = n
var perm = [Int](repeating: 0, count: n + 1)
for (i, char) in s.enumerated() {
if char == "I" {
perm[i] = low
low += 1
} else {
perm[i] = high
high -= 1
}
}
perm[n] = low
return perm
}
}1 348
Задача: 153. Find Minimum in Rotated Sorted Array
Сложность: Medium
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:
[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.
Вы должны написать алгоритм, который работает за время O(log n).
Пример:
Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.👨💻 Алгоритм: 1⃣Нахождение середины массива: Определите элемент, находящийся посередине массива. 2⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины. 3⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом. 😎 Решение:
class Solution {
func findMin(_ nums: [Int]) -> Int {
if nums.count == 1 {
return nums[0]
}
var left = 0
var right = nums.count - 1
if nums[right] > nums[0] {
return nums[0]
}
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] > nums[mid + 1] {
return nums[mid + 1]
}
if mid > 0 && nums[mid - 1] > nums[mid] {
return nums[mid]
}
if nums[mid] > nums[0] {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
}1 348
Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium
Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.
Пример:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5👨💻 Алгоритм: 1⃣Представить каждую строку и столбец как узлы в графе. 2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце. Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности. 3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности. 😎 Решение:
class Solution {
func removeStones(_ stones: [[Int]]) -> Int {
var parent = [Int: Int]()
func find(_ x: Int) -> Int {
if parent[x] == nil {
parent[x] = x
}
if parent[x]! != x {
parent[x] = find(parent[x]!)
}
return parent[x]!
}
func union(_ x: Int, _ y: Int) {
parent[find(x)] = find(y)
}
for stone in stones {
union(stone[0], ~stone[1])
}
var uniqueRoots = Set<Int>()
for key in parent.keys {
uniqueRoots.insert(find(key))
}
return stones.count - uniqueRoots.count
}
}1 348
Задача: 1054. Distant Barcodes
Сложность: medium
На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует.
Пример:
Input: barcodes = [1,1,1,2,2,2] Output: [2,1,2,1,2,1]👨💻 Алгоритм: 1⃣Подсчитай частоту каждого штрих-кода. Помести все штрих-коды в максимальную кучу на основе их частоты. 2⃣Извлекай штрих-коды из кучи, чередуя их, чтобы два соседних штрих-кода не были одинаковыми. 3⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу. 😎 Решение:
func rearrangeBarcodes(_ barcodes: [Int]) -> [Int] {
let count = Dictionary(barcodes.map { ($0, 1) }, uniquingKeysWith: +)
var maxHeap = count.map { (-$0.value, $0.key) }
maxHeap.sort(by: <)
var prevFreq = 0
var prevBarcode = 0
var result = [Int]()
while !maxHeap.isEmpty {
let (freq, barcode) = maxHeap.removeLast()
result.append(barcode)
if prevFreq < 0 {
maxHeap.append((prevFreq, prevBarcode))
maxHeap.sort(by: <)
}
prevFreq = freq + 1
prevBarcode = barcode
}
return result
}1 348
Задача: 847. Shortest Path Visiting All Nodes
Сложность: hard
У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром.
Верните длину кратчайшего пути, который посещает каждый узел. Вы можете начать и закончить в любом узле, вы можете несколько раз посещать узлы и использовать ребра повторно.
Пример:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] Output: 4 Explanation: One possible path is [0,1,4,2,3]👨💻 Алгоритм: 1⃣Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов. 2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps. 3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов. 😎 Решение:
class Solution {
func shortestPathLength(_ graph: [[Int]]) -> Int {
let n = graph.count
if n == 1 {
return 0
}
let endingMask = (1 << n) - 1
var seen = Array(repeating: Array(repeating: false, count: endingMask), count: n)
var queue = [(node: Int, mask: Int)]()
for i in 0..<n {
queue.append((i, 1 << i))
seen[i][1 << i] = true
}
var steps = 0
while !queue.isEmpty {
var nextQueue = [(node: Int, mask: Int)]()
for (node, mask) in queue {
for neighbor in graph[node] {
let nextMask = mask | (1 << neighbor)
if nextMask == endingMask {
return 1 + steps
}
if !seen[neighbor][nextMask] {
seen[neighbor][nextMask] = true
nextQueue.append((neighbor, nextMask))
}
}
}
steps += 1
queue = nextQueue
}
return -1
}
}1 348
Задача: 689. Maximum Sum of 3 Non-Overlapping Subarrays
Сложность: hard
Дан целочисленный массив nums и целое число k. Найдите три непересекающихся подмассива длины k с максимальной суммой и верните их.
Верните результат в виде списка индексов, представляющих начальную позицию каждого интервала (нумерация с 0). Если существует несколько ответов, верните лексикографически наименьший.
Пример:
Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.class Solution {
func maxSumOfThreeSubarrays(_ nums: [Int], _ k: Int) -> [Int] {
var W = [Int](repeating: 0, count: nums.count - k + 1)
var currSum = 0
for i in 0..<nums.count {
currSum += nums[i]
if i >= k {
currSum -= nums[i - k]
}
if i >= k - 1 {
W[i - k + 1] = currSum
}
}
var left = [Int](repeating: 0, count: W.count)
var best = 0
for i in 0..<W.count {
if W[i] > W[best] {
best = i
}
left[i] = best
}
var right = [Int](repeating: 0, count: W.count)
best = W.count - 1
for i in (0..<W.count).reversed() {
if W[i] >= W[best] {
best = i
}
right[i] = best
}
var ans = [-1, -1, -1]
for j in k..<(W.count - k) {
let i = left[j - k]
let l = right[j + k]
if ans[0] == -1 || W[i] + W[j] + W[l] > W[ans[0]] + W[ans[1]] + W[ans[2]] {
ans[0] = i
ans[1] = j
ans[2] = l
}
}
return ans
}
}1 348
Задача: 899. Orderly Queue
Сложность: hard
Вам дана строка s и целое число k. Вы можете выбрать одну из первых k букв s и добавить ее в конец строки. Верните лексикографически наименьшую строку, которая может получиться после применения указанного шага за любое количество ходов.
Пример:
Input: s = "cba", k = 1 Output: "acb"👨💻 Алгоритм: 1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта. 2⃣Если k больше 1, отсортировать строку, так как любое количество перемещений позволит упорядочить все символы в строке. 3⃣Вернуть результат. 😎 Решение:
func orderlyQueue(_ s: String, _ k: Int) -> String {
if k == 1 {
let sArr = Array(s)
var minString = s
for i in 1..<sArr.count {
let rotated = String(sArr[i...] + sArr[..<i])
if rotated < minString {
minString = rotated
}
}
return minString
} else {
return String(s.sorted())
}
}1 348
Задача: 216. Combination Sum III
Сложность: medium
Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:
Используются только числа от 1 до 9.
Каждое число используется не более одного раза.
Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке.
Пример:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.👨💻 Алгоритм: 1⃣Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2⃣Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3⃣Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:
class Solution {
func backtrack(_ remain: Int, _ k: Int, _ comb: inout [Int], _ nextStart: Int, _ results: inout [[Int]]) {
if remain == 0 && comb.count == k {
results.append(comb)
return
} else if remain < 0 || comb.count == k {
return
}
for i in nextStart..<9 {
comb.append(i + 1)
backtrack(remain - i - 1, k, &comb, i + 1, &results)
comb.removeLast()
}
}
func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
var results = [[Int]]()
var comb = [Int]()
backtrack(n, k, &comb, 0, &results)
return results
}
}1 348
Задача: 839. Similar String Groups
Сложность: hard
Две строки, X и Y, считаются похожими, если либо они идентичны, либо мы можем сделать их эквивалентными, поменяв местами не более двух букв (в разных позициях) в строке X.
Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts".
Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе.
Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует?
Пример:
Input: strs = ["tars","rats","arts","star"] Output: 2👨💻 Алгоритм: 1⃣Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n. 2⃣Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи. 3⃣Верните количество оставшихся групп. 😎 Решение:
class UnionFind {
var parent: [Int]
var rank: [Int]
init(size: Int) {
parent = Array(0..<size)
rank = [Int](repeating: 0, count: size)
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
func union(_ x: Int, _ y: Int) {
let xset = find(x)
let yset = find(y)
if xset != yset {
if rank[xset] < rank[yset] {
parent[xset] = yset
} else if rank[xset] > rank[yset] {
parent[yset] = xset
} else {
parent[yset] = xset
rank[xset] += 1
}
}
}
}
class Solution {
func isSimilar(_ a: String, _ b: String) -> Bool {
let aArray = Array(a)
let bArray = Array(b)
var diff = 0
for i in 0..<a.count {
if aArray[i] != bArray[i] {
diff += 1
}
}
return diff == 0 || diff == 2
}
func numSimilarGroups(_ strs: [String]) -> Int {
let n = strs.count
let dsu = UnionFind(size: n)
var count = n
for i in 0..<n {
for j in i+1..<n {
if isSimilar(strs[i], strs[j]) && dsu.find(i) != dsu.find(j) {
count -= 1
dsu.union(i, j)
}
}
}
return count
}
}1 348
Задача: 253. Meeting Rooms II
Сложность: medium
Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.
Пример:
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2👨💻 Алгоритм: 1⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи. 2⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче): Если свободна, обновите время окончания этой комнаты. Если не свободна, добавьте новое время окончания в кучу. 3⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат. 😎 Решение:
import Foundation
class Solution {
func minMeetingRooms(_ intervals: [[Int]]) -> Int {
let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
var heap: [Int] = [sortedIntervals[0][1]]
for i in 1..<sortedIntervals.count {
if sortedIntervals[i][0] >= heap.first! {
heap[0] = sortedIntervals[i][1]
heap.sort()
} else {
heap.append(sortedIntervals[i][1])
heap.sort()
}
}
return heap.count
}
}1 348
Задача: 919. Complete Binary Tree Inserter
Сложность: medium
Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше влево. Разработайте алгоритм вставки нового узла в полное двоичное дерево, сохраняя его полным после вставки.
Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.
Пример:
Input ["CBTInserter", "insert", "insert", "get_root"] [[[1, 2]], [3], [4], []] Output [null, 1, 2, [1, 2, 3, 4]]👨💻 Алгоритм: 1⃣Инициализация: Проход по дереву и добавление всех узлов в очередь, чтобы отслеживать узлы, у которых есть хотя бы одно пустое место для нового дочернего узла. 2⃣Вставка: Добавление нового узла в первое доступное место слева направо. 3⃣Возвращение корня: Просто возвращает корневой узел. 😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}
class CBTInserter {
private var root: TreeNode
private var deque = [TreeNode]()
init(_ root: TreeNode) {
self.root = root
var queue = [TreeNode]()
queue.append(root)
while !queue.isEmpty {
let node = queue.removeFirst()
if node.left == nil || node.right == nil {
deque.append(node)
}
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
}
func insert(_ v: Int) -> Int {
let node = deque[0]
let newNode = TreeNode(v)
if node.left == nil {
node.left = newNode
} else {
node.right = newNode
deque.removeFirst()
}
deque.append(newNode)
return node.val
}
func get_root() -> TreeNode {
return root
}
}