现已上线！2025 年 Telegram 研究 — 年度关键洞察 
Swift | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
显示更多1 348
订阅者
-124 小时
-57 天
-1730 天
帖子存档
1 348
Задача: 561. Array Partition
Сложность: easy
Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.
Пример:
Input: nums = [1,4,3,2] Output: 4 Explanation: All possible pairings (ignoring the ordering of elements) are: 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 So the maximum possible sum is 4.👨💻 Алгоритм: 1⃣Отсортируйте массив nums в неубывающем порядке. 2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого). 3⃣Суммируйте выбранные элементы и верните эту сумму. 😎 Решение:
class Solution {
func arrayPairSum(_ nums: [Int]) -> Int {
let sortedNums = nums.sorted()
var sum = 0
for i in stride(from: 0, to: sortedNums.count, by: 2) {
sum += sortedNums[i]
}
return sum
}
}1 348
Задача: 743. Network Delay Time
Сложность: medium
Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.
Пример:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2👨💻 Алгоритм: 1⃣Представьте граф в виде списка смежности. 2⃣Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов. 3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1. 😎 Решение:
import Foundation
func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
var graph = [Int: [(Int, Int)]]()
for i in 1...n {
graph[i] = []
}
for time in times {
graph[time[0]]?.append((time[1], time[2]))
}
var minHeap = [(0, k)]
var minTime = [Int: Int]()
for i in 1...n {
minTime[i] = Int.max
}
minTime[k] = 0
while !minHeap.isEmpty {
minHeap.sort { $0.0 < $1.0 }
let (time, node) = minHeap.removeFirst()
if let neighbors = graph[node] {
for (neighbor, t) in neighbors {
let newTime = time + t
if newTime < minTime[neighbor]! {
minTime[neighbor] = newTime
minHeap.append((newTime, neighbor))
}
}
}
}
let maxTime = minTime.values.max()!
return maxTime == Int.max ? -1 : maxTime
}1 348
Задача: 515. Largest Value in Each Tree Row
Сложность: medium
Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).
Пример:
Input: root = [1,3,2,5,3,null,9] Output: [1,3,9]👨💻 Алгоритм: 1⃣Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS). 2⃣Выполните BFS, пока очередь не пуста: инициализируйте currMax минимальным значением и сохраните длину очереди в currentLength. Повторите currentLength раз: удалите узел из очереди, обновите currMax, если значение узла больше. Для каждого дочернего узла, если он не равен null, добавьте его в очередь. 3⃣Добавьте currMax в ans. Верните ans. 😎 Решение:
class Solution {
func largestValues(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
var ans = [Int]()
var queue = [root]
while !queue.isEmpty {
var currentLength = queue.count
var currMax = Int.min
for _ in 0..<currentLength {
let node = queue.removeFirst()
currMax = max(currMax, node.val)
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
ans.append(currMax)
}
return ans
}
}1 348
Задача: 69. Sqrt(x)
Сложность: easy
Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным.
Вы не должны использовать встроенные функции или операторы для возведения в степень.
Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python.
Пример:
Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2.👨💻 Алгоритм: 1⃣Если x < 2, верните x. Установите левую границу left = 2 и правую границу right = x / 2. 2⃣Пока left ≤ right: Возьмите num = (left + right) / 2 в качестве предположения. Вычислите num × num и сравните его с x: Если num × num > x, переместите правую границу right = pivot − 1. В противном случае, если num × num < x, переместите левую границу left = pivot + 1. В противном случае num × num == x, целочисленный квадратный корень найден, давайте вернем его. 3⃣Верните right. 😎 Решение:
func mySqrt(_ x: Int) -> Int {
if x < 2 { return x }
var left = 2
var right = x / 2
while left <= right {
let pivot = left + (right - left) / 2
let num = pivot * pivot
if num > x {
right = pivot - 1
} else if num < x {
left = pivot + 1
} else {
return pivot
}
}
return right
}1 348
Задача: 416. Partition Equal Subset Sum
Сложность: medium
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: nums = [1,5,11,5] Output: true👨💻 Алгоритм: 1⃣Проверьте, является ли сумма всех элементов массива четной. Если нет, верните false. 2⃣Используйте динамическое программирование для определения, можно ли найти подмножество с суммой, равной половине от общей суммы элементов. 3⃣Инициализируйте массив для хранения возможных сумм и обновляйте его, проверяя каждое число в массиве. 😎 Решение:
func canPartition(_ nums: [Int]) -> Bool {
let sum = nums.reduce(0, +)
if sum % 2 != 0 { return false }
let target = sum / 2
var dp = [Bool](repeating: false, count: target + 1)
dp[0] = true
for num in nums {
for j in stride(from: target, through: num, by: -1) {
dp[j] = dp[j] || dp[j - num]
}
}
return dp[target]
}1 348
Задача: 121. Best Time to Buy and Sell Stock
Сложность: easy
Вам дан массив цен, где prices[i] является ценой данной акции в i-й день.
Нужно выбрать день для покупки и день в будущем для продажи, чтобы получить максимальную прибыль. Если прибыли нет — вернуть 0.
Пример:
Input: prices = [7,1,5,3,6,4] Output: 5
👨💻 Алгоритм:
1⃣Поддерживаем переменную minPrice, обновляем её при каждом снижении цены
2⃣Вычисляем потенциальную прибыль на каждом шаге и обновляем maxProfit
3⃣Возвращаем максимальную прибыль после прохода по массиву
😎 Решение:
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
var minPrice = Int.max
var maxProfit = 0
for price in prices {
if price < minPrice {
minPrice = price
} else if price - minPrice > maxProfit {
maxProfit = price - minPrice
}
}
return maxProfit
}
}1 348
Задача: 344. Reverse String
Сложность: easy
Напишите функцию, которая переворачивает строку. Входная строка представлена в виде массива символов s.
Вы должны сделать это, изменяя входной массив на месте с использованием O(1) дополнительной памяти.
Пример:
Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]👨💻 Алгоритм: 1⃣Инициализация указателей: Установите два указателя: один на начало массива (left), другой на конец массива (right). 2⃣Перестановка символов: Пока левый указатель меньше правого, обменяйте символы, на которые указывают левый и правый указатели. Сдвиньте левый указатель вправо, а правый указатель влево. 3⃣Завершение работы: Повторяйте шаг 2 до тех пор, пока левый указатель не станет больше или равен правому. 😎 Решение:
class Solution {
func reverseString(_ s: inout [Character]) {
var left = 0
var right = s.count - 1
while left < right {
s.swapAt(left, right)
left += 1
right -= 1
}
}
}1 348
Задача: 1425. Constrained Subsequence Sum
Сложность: hard
Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.
Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке.
Пример:
Input: nums = [10,2,-10,5,20], k = 2 Output: 37 Explanation: The subsequence is [10, 2, 5, 20].👨💻 Алгоритм: 1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums. 2⃣Итерируйте i по индексам nums: Если i минус первый элемент queue больше k, удалите элемент из начала queue. Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()]. Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue. Если dp[i] > 0, добавьте i в конец queue. 3⃣Верните максимальное значение в массиве dp. 😎 Решение:
class Solution {
func constrainedSubsetSum(_ nums: [Int], _ k: Int) -> Int {
var queue = [Int]()
var dp = [Int](repeating: 0, count: nums.count)
var maxSum = Int.min
for i in 0..<nums.count {
if !queue.isEmpty && i - queue.first! > k {
queue.removeFirst()
}
dp[i] = (!queue.isEmpty ? dp[queue.first!] : 0) + nums[i]
while !queue.isEmpty && dp[queue.last!] < dp[i] {
queue.removeLast()
}
if dp[i] > 0 {
queue.append(i)
}
maxSum = max(maxSum, dp[i])
}
return maxSum
}
}1 348
Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium
Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.
Пример:
Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15👨💻 Алгоритм: 1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов. 2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. 3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц. 😎 Решение:
class Solution {
func countSquares(_ matrix: [[Int]]) -> Int {
let m = matrix.count, n = matrix[0].count
var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
var count = 0
for i in 0..<m {
for j in 0..<n {
if matrix[i][j] == 1 {
if i == 0 || j == 0 {
dp[i][j] = 1
} else {
dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
}
count += dp[i][j]
}
}
}
return count
}
}1 348
Задача: 80. Remove Duplicates from Sorted Array II
Сложность: medium
Дан массив целых чисел nums, отсортированный в неубывающем порядке. Удалите из него некоторые дубликаты на месте так, чтобы каждый уникальный элемент встречался не более двух раз. Относительный порядок элементов должен быть сохранён.
Поскольку в некоторых языках программирования невозможно изменить длину массива, результат следует разместить в первой части массива nums. Более формально, если после удаления дубликатов остаётся k элементов, то первые k элементов массива nums должны содержать итоговый результат. Не важно, что остаётся за пределами первых k элементов.
Верните k после размещения итогового результата в первые k слотов массива nums.
Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменяя исходный массив на месте с использованием дополнительной памяти O(1).
Пример:
Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3,_] Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).👨💻 Алгоритм: 1⃣Инициализация переменных: Используйте две переменные: i, которая указывает на текущий индекс в массиве, и count, которая отслеживает количество каждого элемента. Начните обработку массива с первого элемента (индекс 1), предполагая, что первый элемент всегда имеет count равный 1. 2⃣Обработка элементов массива: Для каждого элемента в массиве: 3⃣Если текущий элемент такой же, как предыдущий (nums[i] == nums[i - 1]), увеличьте count. Если count больше 2, это означает, что текущий элемент встречается более двух раз. В этом случае удалите этот элемент из массива с помощью операции удаления, поддерживаемой вашим языком программирования (например, del, pop, remove), и уменьшите индекс i на 1, чтобы корректно обработать следующий элемент. Если текущий элемент отличается от предыдущего (nums[i] != nums[i - 1]), это означает начало новой последовательности, поэтому сбросьте count к 1. Возвращение результата: После обработки всех элементов в массиве, все ненужные дубликаты удалены, и в массиве остаются только допустимые элементы. Верните длину обработанного массива, так как это количество элементов, которые теперь соответствуют условиям задачи. 😎 Решение:
func removeDuplicates(_ nums: inout [Int]) -> Int {
var j = 0
for i in 0..<nums.count {
if j < 2 || nums[i] > nums[j - 2] {
nums[j] = nums[i]
j += 1
}
}
return j
}1 348
Задача: 165. Compare Version Numbers
Сложность: medium
Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей.
Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0.
Верните следующее:
- Если version1 < version2, верните -1.
- Если version1 > version2, верните 1.
- В противном случае верните 0.
Пример:
Input: version1 = "1.2", version2 = "1.10" Output: -1 Explanation: version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.👨💻 Алгоритм: 1⃣Разделение строк: Разделите обе строки по символу точки на два массива. 2⃣Итерация и сравнение: Итерируйте по самому длинному массиву и сравнивайте элементы по одному. Если один из массивов закончился, предполагайте, что все оставшиеся элементы в другом массиве равны нулю, чтобы продолжить сравнение с более длинной строкой. 3⃣Определение результатов сравнения: Если два сегмента не равны, верните 1 или -1 в зависимости от того, какой сегмент больше. Если все сегменты равны после завершения цикла, версии считаются равными. Верните 0 😎 Решение:
class Solution {
func compareVersion(_ version1: String, _ version2: String) -> Int {
let tokens1 = version1.split(separator: ".").map { Int($0)! }
let tokens2 = version2.split(separator: ".").map { Int($0)! }
for i in 0..<max(tokens1.count, tokens2.count) {
let i1 = i < tokens1.count ? tokens1[i] : 0
let i2 = i < tokens2.count ? tokens2[i] : 0
if i1 != i2 {
return i1 > i2 ? 1 : -1
}
}
return 0
}
}1 348
Задача: 1339. Maximum Product of Splitted Binary Tree
Сложность: medium
Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным.
Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после.
Пример:
Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)👨💻 Алгоритм: 1⃣Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке. 2⃣Перебрать все сохраненные суммы поддеревьев и для каждой вычислить произведение суммы поддерева и разности между общей суммой дерева и данной суммой поддерева. 3⃣Найти максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7. 😎 Решение:
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 {
private var allSums: [Int] = []
func maxProduct(_ root: TreeNode?) -> Int {
let totalSum = treeSum(root)
var best: Int64 = 0
for sum in allSums {
best = max(best, Int64(sum) * (totalSum - Int64(sum)))
}
return Int(best % 1000000007)
}
private func treeSum(_ subroot: TreeNode?) -> Int64 {
guard let subroot = subroot else { return 0 }
let leftSum = treeSum(subroot.left)
let rightSum = treeSum(subroot.right)
let totalSum = leftSum + rightSum + Int64(subroot.val)
allSums.append(Int(totalSum))
return totalSum
}
}1 348
Задача: 439. Ternary Expression Parser
Сложность: medium
Дана строка expression, представляющая произвольно вложенные тернарные выражения, вычислите это выражение и верните его результат.
Можно всегда считать, что данное выражение является корректным и содержит только цифры, '?', ':', 'T' и 'F', где 'T' означает истину, а 'F' - ложь. Все числа в выражении являются однозначными числами (т.е. в диапазоне от 0 до 9).
Условные выражения группируются справа налево (как обычно в большинстве языков), и результат выражения всегда будет либо цифрой, либо 'T', либо 'F'.
Пример:
Input: expression = "T?2:3" Output: "2" Explanation: If true, then result is 2; otherwise result is 3.👨💻 Алгоритм: 1⃣Определите вспомогательную функцию isValidAtomic(s), которая принимает строку s и возвращает True, если s является допустимым атомарным выражением. В противном случае функция возвращает False. Функция будет вызываться только с пятисимвольными строками. Если все следующие условия выполнены, функция возвращает True, иначе - False: s[0] является T или F. s[1] является ?. s[2] является T, F или цифрой от 0 до 9. s[3] является :. s[4] является T, F или цифрой от 0 до 9. 2⃣Определите вспомогательную функцию solveAtomic(s), которая принимает строку s и возвращает значение атомарного выражения. Значение атомарного выражения равно E1, если B - это T, иначе значение равно E2. Функция будет вызываться только с пятисимвольными строками и возвращать один символ:. 3⃣Если s[0] является T, функция возвращает s[2], иначе возвращает s[4]. В функции parseTernary(expression) уменьшайте выражение до тех пор, пока не останется односимвольная строка. Инициализируйте j как expression.size() - 1 (это будет самый правый индекс окна). Пока самое правое окно длиной 5 не является допустимым атомарным выражением, уменьшайте j на 1. Когда будет найдено самое правое допустимое атомарное выражение, решите его и уменьшите до одного символа. Замените самое правое допустимое атомарное выражение одним символом, после чего длина выражения уменьшится на 4. В итоге останется односимвольная строка, которую и верните. 😎 Решение:
class Solution {
func parseTernary(_ expression: String) -> String {
func isValidAtomic(_ s: String) -> Bool {
let chars = Array(s)
return chars[0] == "T" || chars[0] == "F" &&
chars[1] == "?" &&
("TF0123456789".contains(chars[2])) &&
chars[3] == ":" &&
("TF0123456789".contains(chars[4]))
}
func solveAtomic(_ s: String) -> Character {
let chars = Array(s)
return chars[0] == "T" ? chars[2] : chars[4]
}
var expression = Array(expression)
while expression.count != 1 {
var j = expression.count - 1
while !isValidAtomic(String(expression[(j-4)...j])) {
j -= 1
}
let result = solveAtomic(String(expression[(j-4)...j]))
expression = Array(expression[0..<(j-4)]) + [result] + Array(expression[(j+1)...])
}
return String(expression)
}
}1 348
Задача: 629. K Inverse Pairs Array
Сложность: hard
Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.
Пример:
Input: n = 3, k = 0 Output: 1👨💻 Алгоритм: 1⃣Инициализация Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0. 2⃣Заполнение DP-таблицы Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1. 3⃣Возвращение результата Результатом будет значение dp[n][k]. 😎 Решение:
func kInversePairs(_ n: Int, _ k: Int) -> Int {
let MOD = 1_000_000_007
var dp = Array(repeating: Array(repeating: 0, count: k + 1), count: n + 1)
dp[0][0] = 1
for i in 1...n {
dp[i][0] = 1
for j in 1...k {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD
if j >= i {
dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + MOD) % MOD
}
}
}
return dp[n][k]
}1 348
Задача: 171. Excel Sheet Column Number
Сложность: easy
Дана строка
columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца.
Пример:
Input: columnTitle = "A" Output: 1👨💻 Алгоритм: 1⃣Создайте отображение букв алфавита и их соответствующих значений (начиная с 1). 2⃣Инициализируйте переменную-аккумулятор result. 3⃣Начиная справа налево, вычислите значение символа в зависимости от его позиции и добавьте его к result. 😎 Решение:
func titleToNumber(_ s: String) -> Int {
var result = 0
let alpha_map: [Character: Int] = {
var map = [Character: Int]()
for i in 0..<26 {
map[Character(UnicodeScalar(i + 65)!)] = i + 1
}
return map
}()
let n = s.count
for (i, char) in s.reversed().enumerated() {
result += alpha_map[char]! * Int(pow(26.0, Double(i)))
}
return result
}1 348
Задача: 154. Find Minimum in Rotated Sorted Array II
Сложность: Hard
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать:
[4,5,6,7,0,1,4], если он был повернут 4 раза.
[0,1,4,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, который может содержать дубликаты, верните минимальный элемент этого массива.
Необходимо максимально уменьшить количество операций.
Пример:
Input: nums = [1,3,5] Output: 1👨💻 Алгоритм: 1⃣Сравнение с правой границей: В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]). 2⃣Обновление указателей: Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid. Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid. Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента. 3⃣Итерация до сужения диапазона поиска: Продолжаем процесс, пока левый указатель не встретится с правым. В конечном итоге правый указатель укажет на минимальный элемент массива после всех поворотов. 😎 Решение:
class Solution {
func findMin(_ nums: [Int]) -> Int {
var low = 0
var high = nums.count - 1
while low < high {
let pivot = low + (high - low) / 2
if nums[pivot] < nums[high] {
high = pivot
} else if nums[pivot] > nums[high] {
low = pivot + 1
} else {
high -= 1
}
}
return nums[low]
}
}1 348
Задача: 282. Expression Add Operators
Сложность: hard
Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.
Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей.
Пример:
Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"] Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.👨💻 Алгоритм: 1⃣Инициализация и рекурсивный вызов: Создайте класс Solution с полями для хранения результирующих выражений, строки цифр и целевого значения. Инициализируйте эти поля в методе addOperators и запустите рекурсивный метод для генерации всех возможных выражений. 2⃣Рекурсивная генерация выражений: В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения. Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение. 3⃣Проверка и запись валидных выражений: Когда вся строка цифр обработана, проверяйте, соответствует ли итоговое значение целевому значению и нет ли остатков операндов. Если выражение валидное, записывайте его в список результатов. 😎 Решение:
class Solution {
var answer = [String]()
var digits = ""
var target: Int64 = 0
func recurse(_ index: Int, _ previousOperand: Int64, _ currentOperand: Int64, _ value: Int64, _ ops: inout [String]) {
if index == digits.count {
if value == target && currentOperand == 0 {
answer.append(ops.joined())
}
return
}
let nums = Array(digits)
let currentDigit = Int64(String(nums[index]))!
let currentOperand = currentOperand * 10 + currentDigit
let currentValRep = String(currentOperand)
if currentOperand > 0 {
recurse(index + 1, previousOperand, currentOperand, value, &ops)
}
ops.append("+")
ops.append(currentValRep)
recurse(index + 1, currentOperand, 0, value + currentOperand, &ops)
ops.removeLast(2)
if !ops.isEmpty {
ops.append("-")
ops.append(currentValRep)
recurse(index + 1, -currentOperand, 0, value - currentOperand, &ops)
ops.removeLast(2)
ops.append("*")
ops.append(currentValRep)
recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), &ops)
ops.removeLast(2)
}
}
func addOperators(_ num: String, _ target: Int) -> [String] {
if num.isEmpty {
return []
}
self.target = Int64(target)
self.digits = num
self.answer = []
var ops = [String]()
recurse(0, 0, 0, 0, &ops)
return answer
}
}1 348
Задача: 1140. Stone Game II
Сложность: medium
Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.
Пример:
Input: piles = [2,7,9,4,4] Output: 10 Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.👨💻 Алгоритм: 1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи), и m (максимальное количество куч, которые можно взять за ход). Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его. 2⃣Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния. Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат. Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат. 3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res. 😎 Решение:
class Solution {
func stoneGameII(_ piles: [Int]) -> Int {
var dp = Array(repeating: Array(repeating: Array(repeating: -1, count: piles.count + 1), count: piles.count + 1), count: 2)
func f(_ p: Int, _ i: Int, _ m: Int) -> Int {
if i == piles.count {
return 0
}
if dp[p][i][m] != -1 {
return dp[p][i][m]
}
var res = p == 1 ? Int.max : -1
var s = 0
for x in 1...min(2 * m, piles.count - i) {
s += piles[i + x - 1]
if p == 0 {
res = max(res, s + f(1, i + x, max(m, x)))
} else {
res = min(res, f(0, i + x, max(m, x)))
}
}
dp[p][i][m] = res
return res
}
return f(0, 0, 1)
}
}1 348
Задача: 30. Substring with Concatenation of All Words
Сложность: hard
Вам дана строка
s и массив строк words. Все строки в words имеют одинаковую длину.
Объединенная строка — это строка, которая в точности содержит все строки любой перестановки words.
Возвращает массив начальных индексов всех объединенных подстрок в s.
Пример:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]👨💻Алгоритм: 1⃣Определяем длину слова
len и количество слов cnt.
2⃣Создаем словарь wf с частотами слов в words.
3⃣Проходим по строке s, проверяя подстроки длиной cnt * len.
😎Решение:
class Solution {
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
let len = words.first!.count
let cnt = words.count
guard s.count >= cnt * len else { return [] }
let s = Array(s)
let words = words.map(Array.init)
let wf = words.reduce(into: [[Character]: Int]()) { $0[$1, default: 0] += 1 }
let ws = Set(words)
var res = [Int]()
for i in 0...(s.count - cnt * len) {
var sf = [[Character]: Int]()
var j = i
for _ in 0..<cnt {
let w = Array(s[j..<j + len])
guard ws.contains(w) else { break }
let old = sf[w, default: 0]
guard old + 1 <= wf[w]! else { break }
sf[w] = old + 1
j += len
}
guard j == i + cnt * len, sf == wf else { continue }
res.append(i)
}
return res
}
}1 348
Задача: 527. Word Abbreviation
Сложность: hard
Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.
Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.
Пример:
Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"] Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]👨💻 Алгоритм: 1⃣ Инициализация и создание начальных сокращений: Создайте массив для хранения сокращений и массив для отслеживания длины префикса каждого слова. Для каждого слова создайте начальное сокращение с использованием первого символа, количества символов между первым и последним символом и последнего символа. 2⃣ Обработка коллизий: Для каждого слова проверьте, не совпадает ли его сокращение с уже существующими сокращениями. Если сокращение не уникально, увеличьте длину префикса и повторите проверку. 3⃣ Возврат результата: Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны. 😎 Решение:
class Solution {
func wordsAbbreviation(_ words: [String]) -> [String] {
let n = words.count
var ans = Array(repeating: "", count: n)
var prefix = Array(repeating: 0, count: n)
for i in 0..<n {
ans[i] = abbrev(words[i], 0)
}
for i in 0..<n {
while true {
var dupes = Set<Int>()
for j in (i+1)..<n {
if ans[i] == ans[j] {
dupes.insert(j)
}
}
if dupes.isEmpty { break }
dupes.insert(i)
for k in dupes {
ans[k] = abbrev(words[k], prefix[k] + 1)
prefix[k] += 1
}
}
}
return ans
}
private func abbrev(_ word: String, _ i: Int) -> String {
let n = word.count
if n - i <= 3 { return word }
let start = word.prefix(i + 1)
let end = word.suffix(1)
return "\(start)\(n - i - 2)\(end)"
}
}