Swift | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
显示更多
网络:1 339
订阅者
-124 小时
-87 天
-2530 天
帖子存档
1 339
#easy
Задача: 58. Length of Last Word
Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке.
Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами.
Пример:
Input: s = "Hello World" Output: 5 Explanation: The last word is "World" with length 5.👨💻 Алгоритм: 1️⃣Поиск последнего слова: Сначала мы пытаемся найти последнее слово, начиная с конца строки. Итерируем строку в обратном порядке, пропуская пробелы. Когда мы встречаем первый непробельный символ, мы знаем, что нашли последний символ последнего слова. 2️⃣Определение длины последнего слова: После того как последнее слово найдено, мы подсчитываем его длину, начиная с его последнего символа. Здесь также можно использовать цикл. 3️⃣Итог: Используя обратную итерацию и пропуск пробелов, определяется начало и конец последнего слова в строке для вычисления его длины. 😎 Решение:
class Solution {
func lengthOfLastWord(_ s: String) -> Int {
var p = s.count - 1
// Trim the trailing spaces
while p >= 0 && s[s.index(s.startIndex, offsetBy: p)] == ' ' {
p -= 1
}
// Compute the length of the last word
var length = 0
while p >= 0 && s[s.index(s.startIndex, offsetBy: p)] != ' ' {
p -= 1
length += 1
}
return length
}
}1 339
Задача: 35. Search Insert Position #easy
Условие:
Учитывая отсортированный массив различных целых чисел и целевое значение, верните индекс, если цель найдена. Если нет, верните индекс там, где он был бы, если бы он был вставлен по порядку. Вы должны написать алгоритм со сложностью выполнения O(log n).Решение:
class Solution {
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
var left = 0, right = nums.count - 1
while left <= right {
var pivot = left + (right - left) / 2
if nums[pivot] == target {
return pivot
} else if nums[pivot] > target {
right = pivot - 1
} else {
left = pivot + 1
}
}
return left
}
}1 339
#medium
Задача: 57. Insert Interval
Вам дан массив непересекающихся интервалов
intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.
Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).
Верните массив intervals после вставки.
Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его.
Пример:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]👨💻 Алгоритм: 1️⃣ Инициализация переменных: Инициализируются переменные n и i для хранения размера массива интервалов и текущего индекса соответственно, а также пустой массив res для хранения результата. 2️⃣Обработка случаев без перекрытия и с перекрытием: В случае отсутствия перекрытия до вставки, проходим через массив интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в массив res и переходим к следующему. В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один. 3️⃣Обработка интервалов после вставки: Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним. Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом. 😎 Решение:
class Solution {
func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
var intervals = intervals
var newInterval = newInterval
var res = [[Int]]()
var i = 0
// Process intervals with no overlap before the new interval
while i < intervals.count && intervals[i][1] < newInterval[0] {
res.append(intervals[i])
i += 1
}
// Merge overlapping intervals with newInterval
while i < intervals.count && newInterval[1] >= intervals[i][0] {
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
}
res.append(newInterval)
// Append remaining intervals after merging
while i < intervals.count {
res.append(intervals[i])
i += 1
}
return res
}
}1 339
#medium
Задача: 56. Merge Intervals
Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.
Пример:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].👨💻 Алгоритм: 1️⃣ Представление графа: Имея представленную интуицию, мы можем изобразить граф в виде списка смежности, вставляя направленные ребра в обоих направлениях, чтобы симулировать неориентированные ребра. 2️⃣Определение компонент связности: Для определения, в какой компоненте связности находится каждый узел, мы выполняем обходы графа от произвольных непосещенных узлов до тех пор, пока все узлы не будут посещены. Для эффективности мы храним посещенные узлы в множестве (Set), что позволяет проводить проверки на принадлежность и вставку за константное время. 3️⃣Объединение интервалов внутри компонент: Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу. Решение:
import Foundation
class Solution {
var graph = [Array<Int>: [[Int]]]()
var nodesInComp = [Int: [[Int]]]()
var visited = Set<Array<Int>>()
func overlap(_ a: [Int], _ b: [Int]) -> Bool {
return a[0] <= b[1] && b[0] <= a[1]
}
func buildGraph(_ intervals: [[Int]]) {
for interval1 in intervals {
for interval2 in intervals {
if overlap(interval1, interval2) {
graph[interval1, default: []].append(interval2)
graph[interval2, default: []].append(interval1)
}
}
}
}
func mergeNodes(_ nodes: [[Int]]) -> [Int] {
var minStart = nodes[0][0]
for node in nodes {
minStart = min(minStart, node[0])
}
var maxEnd = nodes[0][1]
for node in nodes {
maxEnd = max(maxEnd, node[1])
}
return [minStart, maxEnd]
}
func markComponentDFS(_ start: [Int], _ compNumber: Int) {
var stack = [[Int]]()
stack.append(start)
while !stack.isEmpty {
let node = stack.removeLast()
if !visited.contains(node) {
visited.insert(node)
nodesInComp[compNumber, default: []].append(node)
for child in graph[node, default: []] {
stack.append(child)
}
}
}
}
func buildComponents(_ intervals: [[Int]]) {
var compNumber = 0
for interval in intervals {
if !visited.contains(interval) {
markComponentDFS(interval, compNumber)
compNumber += 1
}
}
}
func merge(_ intervals: [[Int]]) -> [[Int]] {
buildGraph(intervals)
buildComponents(intervals)
var merged = [[Int]]()
for comp in 0..<nodesInComp.count {
if let nodes = nodesInComp[comp] {
merged.append(mergeNodes(nodes))
}
}
return merged
}
}1 339
😮 Добавлена новая база слитых курсов на 800ГБ:
Программирование:
https://t.me/+tHab1ttNTE85Yjgy
Python:
https://t.me/+zpUxu2ScikwwZGJi
Графика и дизайн:
https://t.me/+GwFBZ4HOcOs2ZDcy
Frontend и Web:
https://t.me/+8op47ibl8thhYTIy
1 339
Задача: 34. Find First and Last Position of Element in Sorted Array #medium
Условие:
Учитывая массив целых чисел, отсортированных в порядке неубывания, найдите начальную и конечную позицию заданного целевого значения. Если цель не найдена в массиве, верните [-1, -1]. Вы должны написать алгоритм со сложностью выполнения O(log n).Решение:
func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
let lo = searchRange(nums, target, .lo)
let hi = searchRange(nums, target, .hi)
return [lo, hi]
}
func searchRange(_ nums: [Int], _ target: Int, _ direction: Direction = .lo) -> Int {
var start = 0
var end = nums.count - 1
var result = -1
while start <= end {
let mid = (start+end) / 2
if nums[mid] == target {
result = mid
if direction == .lo {
end = mid - 1
} else {
start = mid + 1
}
} else if nums[mid] < target {
start = mid + 1
} else if nums[mid] > target {
end = mid - 1
}
}
return result
} 1 339
#medium
Задача: 55. Jump Game
Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции.
Верните true, если вы можете достичь последнего индекса, или false в противном случае.
Пример:
Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.👨💻Алгоритм: 1️⃣ Инициализация таблицы памяти: Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя). 2️⃣Модификация алгоритма обратного трассирования: Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD). Если индекс известен, тогда возвращается True/False. 3️⃣Выполнение и сохранение результатов: Если индекс не известен, выполняйте шаги обратного трассирования, как ранее. После определения значения текущего индекса, сохраните его в таблице памяти. 😎 Решение:
enum Index {
case good, bad, unknown
}
class Solution {
var memo: [Index]
init(_ nums: [Int]) {
self.memo = Array(repeating: .unknown, count: nums.count)
self.memo[nums.count - 1] = .good
}
func canJumpFromPosition(_ position: Int, _ nums: [Int]) -> Bool {
if memo[position] != .unknown {
return memo[position] == .good
}
let furthestJump = min(position + nums[position], nums.count - 1)
for nextPosition in (position + 1)...furthestJump {
if canJumpFromPosition(nextPosition, nums) {
memo[position] = .good
return true
}
}
memo[position] = .bad
return false
}
func canJump(_ nums: [Int]) -> Bool {
return canJumpFromPosition(0, nums)
}
}1 339
#hard
Задача: 43. Multiply Strings
Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.
Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.
Пример:
Input: num1 = "2", num2 = "3" Output: "6"👨💻 Алгоритм: 1️⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber: Инициализируйте переменную carry, первоначально равную 0. Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber. 2️⃣Для каждой цифры в firstNumber: Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению. Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру в массив currentResult. Разделите умножение на 10, чтобы получить новое значение для carry. 3️⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult. Добавьте currentResult к ans. Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль. Переверните ans и верните его. 😎 Решение:
func addStrings(_ num1: [Int], _ num2: [Int]) -> [Int] {
var ans = [Int]()
var carry = 0
let maxLength = max(num1.count, num2.count)
for i in 0..<maxLength {
let digit1 = i < num1.count ? num1[i] : 0
let digit2 = i < num2.count ? num2[i] : 0
let sum = digit1 + digit2 + carry
carry = sum / 10
ans.append(sum % 10)
}
if carry > 0 {
ans.append(carry)
}
return ans
}
func multiplyOneDigit(_ firstNumber: [Int], _ secondNumberDigit: Int, _ numZeros: Int) -> [Int] {
var currentResult = Array(repeating: 0, count: numZeros)
var carry = 0
for digit in firstNumber {
let multiplication = secondNumberDigit * digit + carry
carry = multiplication / 10
currentResult.append(multiplication % 10)
}
if carry > 0 {
currentResult.append(carry)
}
return currentResult
}
func multiply(_ num1: String, _ num2: String) -> String {
if num1 == "0" || num2 == "0" {
return "0"
}
let firstNumber = Array(num1).reversed().map { Int(String($0))! }
let secondNumber = Array(num2).reversed().map { Int(String($0))! }
var ans = Array(repeating: 0, count: firstNumber.count + secondNumber.count)
for (i, digit) in secondNumber.enumerated() {
let partialResult = multiplyOneDigit(firstNumber, digit, i)
ans = addStrings(ans, partialResult)
}
// Remove leading zeros
while ans.last == 0 && ans.count > 1 {
ans.removeLast()
}
return ans.reversed().map { String($0) }.joined()
}1 339
Задача: 33. Search in Rotated Sorted Array #medium
Условие:
Существует целочисленный массив nums, отсортированный по возрастанию (с разными значениями). Перед передачей в вашу функцию nums, возможно, поворачивается с неизвестным индексом поворота k (1 <= k < nums.length), так что результирующий массив имеет вид [nums[k], nums[k+1],... , nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексом 0). Например, [0,1,2,4,5,6,7] можно повернуть с опорным индексом 3 и превратить в [4,5,6,7,0,1,2]. Учитывая массив nums после возможного поворота и целочисленную цель, верните индекс цели, если он находится в nums, или -1, если он не в nums. Вы должны написать алгоритм со сложностью выполнения O(log n).Решение:
class Solution {
func search(_ nums: [Int], _ target: Int) -> Int {
if nums.isEmpty { return -1 }
var lo = 0
var hi = nums.count - 1
while lo <= hi {
var mid = lo + (hi-lo)/2
if nums[mid] == target { return mid }
else if nums[mid] <= nums[hi] {
//right half is sorted
if target > nums[mid] && target <= nums[hi] {
lo = mid+1
} else {
hi = mid-1
}
} else if nums[lo] <= nums[mid] {
//left half is sorted
if target >= nums[lo] && target < nums[mid] {
hi = mid-1
} else {
lo = mid+1
}
}
}
return -1
}
}1 339
#hard
Задача: 42. Trapping Rain Water
Дано n неотрицательных целых чисел, представляющих карту высот, где ширина каждого столбца равна 1. Вычислите, сколько воды он может удержать после дождя.
Пример:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6👨💻 Алгоритм: 1️⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max. 2️⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max. 3️⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans. 😎 Решение:
func trap(_ height: [Int]) -> Int {
if height.isEmpty {
return 0
}
let size = height.count
var ans = 0
var leftMax = Array(repeating: 0, count: size)
var rightMax = Array(repeating: 0, count: size)
leftMax[0] = height[0]
for i in 1..<size {
leftMax[i] = max(height[i], leftMax[i - 1])
}
rightMax[size - 1] = height[size - 1]
for i in stride(from: size - 2, through: 0, by: -1) {
rightMax[i] = max(height[i], rightMax[i + 1])
}
for i in 1..<size - 1 {
ans += min(leftMax[i], rightMax[i]) - height[i]
}
return ans
}1 339
#hard
Задача: 41. First Missing Positive
Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums.
Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти.
Пример:
Input: nums = [3,4,-1,1] Output: 2 Explanation: 1 is in the array but 2 is missing.👨💻 Алгоритм: 1️⃣Инициализировать переменную n длиной массива nums. Создать массив seen размером n + 1. Отметить элементы в массиве nums как просмотренные в массиве seen. Для каждого числа num в массиве nums, если num больше 0 и меньше или равно n, установить seen[num] в значение true. 2️⃣Найти наименьшее недостающее положительное число: Проитерировать от 1 до n, и если seen[i] не равно true, вернуть i как наименьшее недостающее положительное число. 3️⃣Если массив seen содержит все элементы от 1 до n, вернуть n + 1 как наименьшее недостающее положительное число. 😎 Решение:
func firstMissingPositive(_ nums: [Int]) -> Int {
let n = nums.count
var seen = Array(repeating: false, count: n + 1)
for num in nums {
if num > 0 && num <= n {
seen[num] = true
}
}
for i in 1...n {
if !seen[i] {
return i
}
}
return n + 1
}1 339
Задача: 32. Longest Valid Parentheses #hard
Условие:
Учитывая строку, содержащую только символы «(» и «)», верните длину самых длинных допустимых (правильно сформированных) круглых скобок. подстрокаРешение:
func longestValidParentheses(_ s: String) -> Int {
if s.count == 0{
return 0
}
var stack = [Int]()
stack.append(-1)
var arr = Array(s)
var res = 0
for i in 0..<arr.count{
if arr[i] == ")"{
if stack.count > 1 && arr[stack.last!] == "("{
stack.removeLast()
res = max(res, i - stack.last!)
}else{
stack.append(i)
}
}else{
stack.append(i)
}
}
return res
}
1 339
#medium
Задача: 40. Combination Sum II
Дана коллекция кандидатов (candidates) и целевое число (target). Найдите все уникальные комбинации в candidates, где числа кандидатов в сумме дают target.
Каждое число в candidates может быть использовано только один раз в комбинации.
Примечание: Набор решений не должен содержать повторяющихся комбинаций.
Пример:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]👨💻 Алгоритм: 1️⃣Во-первых, мы создаём таблицу счётчиков из предоставленного списка чисел. Затем мы используем эту таблицу счётчиков в процессе обратного поиска, который мы определяем как функцию
backtrack(comb, remain, curr, candidate_groups, results). Для сохранения состояния на каждом этапе обратного поиска мы используем несколько параметров в функции:
comb: комбинация, которую мы построили на данный момент.
remain: оставшаяся сумма, которую нам нужно заполнить, чтобы достичь целевой суммы.
curr: курсор, который указывает на текущую группу чисел, используемую из таблицы счётчиков.
counter: текущая таблица счётчиков.
results: окончательные комбинации, которые достигают целевой суммы.
2️⃣При каждом вызове функции обратного поиска мы сначала проверяем, достигли ли мы целевой суммы (то есть sum(comb) = target), и нужно ли прекратить исследование, потому что сумма текущей комбинации превышает желаемую целевую сумму.
3️⃣Если осталась сумма для заполнения, мы затем перебираем текущую таблицу счётчиков, чтобы выбрать следующего кандидата. После выбора кандидата мы продолжаем исследование, вызывая функцию backtrack() с обновлёнными состояниями. Более важно, что в конце каждого исследования нам нужно вернуть состояние, которое мы обновили ранее, чтобы начать с чистого листа для следующего исследования. Именно из-за этой операции обратного поиска алгоритм получил своё название.
😎 Решение:
class Solution {
func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
let candidates = candidates.sorted()
var res = [[Int]]()
findCombinationSum2(candidates, target, 0, [], &res)
return res
}
private func findCombinationSum2(_ candidates: [Int], _ target: Int, _ start: Int, _ current: [Int], _ res: inout [[Int]]) {
if target == 0 {
res.append(current)
return
}
var current = current
for i in start..<candidates.count {
if i > start && candidates[i] == candidates[i - 1] {
continue
}
if candidates[i] > target {
break
}
current.append(candidates[i])
findCombinationSum2(candidates, target - candidates[i], i + 1, current, &res)
current.removeLast()
}
}
}1 339
Ну все! Теперь не нужно тратить деньги на топовые курсы и книги по программированию — их выложили в Telegram бесплатно
Все найденные курсы собирают тут — @portalToIT
По этим курсам выучить любой язык за 7 дней вообще не проблема, находка для начинающих программистов.
1 339
#medium
Задача: 39. Combination Sum
Дан массив уникальных целых чисел 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
}
}1 339
Задача: 31. Next Permutation #medium
Условие:
Перестановка массива целых чисел — это расположение его членов в последовательность или линейный порядок. Например, для arr = [1,2,3] следующие перестановки arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его целого числа. Более формально, если все перестановки массива отсортированы в одном контейнере в соответствии с их лексикографическим порядком, то следующей перестановкой этого массива будет перестановка, следующая за ней в отсортированном контейнере. Если такое расположение невозможно, массив необходимо переупорядочить в наименьшем возможном порядке (т. е. отсортировать по возрастанию). Например, следующая перестановка arr = [1,2,3] — это [1,3,2]. Аналогично, следующая перестановка arr = [2,3,1] — это [3,1,2]. А следующая перестановка arr = [3,2,1] — это [1,2,3], потому что [3,2,1] не имеет более крупной лексикографической перестановки. Учитывая массив целых чисел nums, найдите следующую перестановку чисел. Замена должна быть на месте и использовать только постоянную дополнительную память.Решение:
class Solution {
func nextPermutation(_ nums: inout [Int]) {
if(nums.count == 1) {
return
}
var i = nums.count - 2
while(i >= 0 && nums[i + 1] <= nums[i]) {
i -= 1
}
//if input is in decreaing order
if(i < 0) {
nums.sort()
return
}
if(i >= 0) {
var j = nums.count - 1
while(j >= 0 && nums[j] <= nums[i]) {
j -= 1
}
(nums[i],nums[j]) = (nums[j], nums[i])
reverse(&nums, i + 1)
}
}
func reverse(_ nums:inout [Int], _ start:Int) {
var low = start
var high = nums.count - 1
while (low < high) {
(nums[low],nums[high]) = (nums[high],nums[low])
low += 1
high -= 1
}
}
}1 339
#medium
Задача: 38. Count and Say
Последовательность "считай и скажи" — это последовательность строк цифр, определяемая с помощью рекурсивной формулы:
countAndSay(1) = "1"
countAndSay(n) — это кодирование длин серий из countAndSay(n - 1).
Кодирование длин серий (RLE) — это метод сжатия строк, который работает путём замены последовательных идентичных символов (повторяющихся 2 или более раз) на конкатенацию символа и числа, обозначающего количество символов (длину серии). Например, чтобы сжать строку "3322251", мы заменяем "33" на "23", "222" на "32", "5" на "15" и "1" на "11". Таким образом, сжатая строка становится "23321511".
Для заданного положительного целого числа n верните n-й элемент последовательности "считай и скажи".
Пример:
Input: n = 4 Output: "1211" Explanation: countAndSay(1) = "1" countAndSay(2) = RLE of "1" = "11" countAndSay(3) = RLE of "11" = "21" countAndSay(4) = RLE of "21" = "1211"👨💻 Алгоритм: 1️⃣Мы хотим использовать шаблон, который соответствует строкам из одинаковых символов, таких как "4", "7777", "2222222". Если у вас есть опыт работы с регулярными выражениями, вы можете обнаружить, что шаблон (.)\1* работает. 2️⃣Мы можем разбить это регулярное выражение на три части: (.): оно определяет группу, содержащую один символ, который может быть чем угодно. 3️⃣*: этот квалификатор, следующий за ссылкой на группу \1, указывает, что мы хотели бы видеть повторение группы ноль или более раз. Таким образом, шаблон соответствует строкам, которые состоят из некоторого символа, а затем ноль или более повторений этого символа после его первого появления. Это то, что нам нужно. Мы находим все совпадения с регулярным выражением, а затем конкатенируем результаты. 😎 Решение:
func countAndSay(_ n: Int) -> String {
var s = "1"
for _ in 2...n {
var t = ""
var matches = Array(s.matchingStrings(regex: "(.)\\1*"))
for match in matches {
t += "\(match[0].count)\(match[1])"
}
s = t
}
return s
}
extension String {
func matchingStrings(regex: String) -> [[String]] {
do {
let regex = try NSRegularExpression(pattern: regex)
let results = regex.matches(in: self, range: NSRange(self.startIndex..., in: self))
return results.map { result in
(0..<result.numberOfRanges).map {
String(self[Range(result.range(at: $0), in: self)!])
}
}
} catch let error {
print("invalid regex: \(error.localizedDescription)")
return []
}
}
}1 339
#hard
Задача: 37. Sudoku Solver
Напишите программу для решения головоломки Судоку, заполнив пустые ячейки.
Решение Судоку должно удовлетворять всем следующим правилам:
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждой строке.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом столбце.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом из 9 подблоков 3x3 сетки.
Символ '.' обозначает пустые ячейки.
Пример:
Input: board = [["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]👨💻 Алгоритм: 1️⃣Теперь все готово для написания функции обратного поиска backtrack(row = 0, col = 0). Начните с верхней левой ячейки row = 0, col = 0. Продолжайте, пока не дойдете до первой свободной ячейки. 2️⃣Итерируйте по числам от 1 до 9 и попробуйте поставить каждое число d в ячейку (row, col). Если число d еще не в текущей строке, столбце и блоке: Поместите d в ячейку (row, col). Запишите, что d теперь присутствует в текущей строке, столбце и блоке. 3️⃣Если вы на последней ячейке row == 8, col == 8: Это означает, что судоку решено. В противном случае продолжайте размещать дальнейшие числа. Откат, если решение еще не найдено: удалите последнее число из ячейки (row, col). 😎 Решение:
import Foundation
class Solution {
func solveSudoku(_ board: inout [[Character]]) {
let n = 3
let N = n * n
var tracking = Array(repeating: [Character: Int](), count: N * 3)
func index(_ type: Int, _ i: Int) -> Int { type * N + i }
func boxIndex(_ r: Int, _ c: Int) -> Int { (r / n) * n + c / n }
func canPlace(_ num: Character, _ r: Int, _ c: Int) -> Bool {
let bIdx = boxIndex(r, c)
return tracking[index(0, r)][num] == nil &&
tracking[index(1, c)][num] == nil &&
tracking[index(2, bIdx)][num] == nil
}
func placeOrRemove(_ num: Character, _ r: Int, _ c: Int, place: Bool) {
let bIdx = boxIndex(r, c)
let adjustment = place ? 1 : -1
tracking[index(0, r)][num, default: 0] += adjustment
tracking[index(1, c)][num, default: 0] += adjustment
tracking[index(2, bIdx)][num, default: 0] += adjustment
board[r][c] = place ? num : "."
}
func backtrack(_ r: Int = 0, _ c: Int = 0) {
if c == N && r == N - 1 { return }
let nextR = c == N - 1 ? r + 1 : r
let nextC = c == N - 1 ? 0 : c + 1
if board[r][c] == "." {
for num in "123456789" {
if canPlace(num, r, c) {
placeOrRemove(num, r, c, place: true)
backtrack(nextR, nextC)
placeOrRemove(num, r, c, place: false)
}
}
} else {
backtrack(nextR, nextC)
}
}
for r in 0..<N {
for c in 0..<N where board[r][c] != "." {
placeOrRemove(board[r][c], r, c, place: true)
}
}
backtrack()
}
}1 339
Задача: 30. Substring with Concatenation of All Words #hard
Условие:
Вам дана строка s и массив строк-слов. Все строки слов имеют одинаковую длину. Объединенная строка — это строка, которая в точности содержит все строки любой перестановки объединенных слов. Например, если слова = ["ab", "cd", "ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются объединенными строками. «acdbef» не является объединенной строкой, поскольку не является объединением какой-либо перестановки слов. Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.Решение:
vector<int> findSubstring(string str, vector<string>& words) {
int len = words[0].length();
unordered_map<string, int> contain;
for(string s: words) contain[s]++;
vector<int> res;
for(int j = 0; j < len; j++) {
unordered_map<string, int> found;
int st = j;
for(int i = 0 + j; i < str.size() - len + 1; i += len) {
string curr = str.substr(i, len);
if(contain.find(curr) != contain.end()) {
found[curr]++;
while(found[curr] > contain[curr]) {
found[str.substr(st, len)]--;
st += len;
}
int size = (i - st + len) / len;
if(size == words.size()) {
cout << j << " " << st << " " << i << endl;
res.push_back(st);
}
} else {
found.clear();
st = i + len;
}
}
}
return res;
}1 339
#medium
Задача: 36. Valid Sudoku
Определите, является ли доска Судоку размером 9 на 9 валидной. Необходимо проверить только заполненные ячейки согласно следующим правилам:
Каждая строка должна содержать цифры от 1 до 9 без повторений.
Каждый столбец должен содержать цифры от 1 до 9 без повторений.
Каждая из девяти подзон размером 3 на 3 в сетке должна содержать цифры от 1 до 9 без повторений.
Пример:
Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] Output: true👨💻 Алгоритм: 1️⃣Инициализируйте список из 9 хеш-множеств, где хеш-множество с индексом r будет использоваться для хранения ранее увиденных чисел в строке r судоку. Аналогично инициализируйте списки из 9 хеш-множеств для отслеживания столбцов и блоков. 2️⃣Итерируйтесь по каждой позиции (r, c) в судоку. На каждой итерации, если на текущей позиции есть число: Проверьте, существует ли это число в хеш-множестве для текущей строки, столбца или блока. Если да, верните false, потому что это второе появление числа в текущей строке, столбце или блоке. 3️⃣В противном случае обновите множество, отвечающее за отслеживание ранее увиденных чисел в текущей строке, столбце и блоке. Индекс текущего блока рассчитывается как (r / 3) * 3 + (c / 3), где / означает деление нацело. Если дубликаты не были найдены после посещения каждой позиции на доске судоку, то судоку валидно, поэтому верните true. 😎 Решение:
func isValidSudoku(_ board: [[Character]]) -> Bool {
let N = 9
var rows = Array(repeating: [Character: Bool](), count: N)
var cols = Array(repeating: [Character: Bool](), count: N)
var boxes = Array(repeating: [Character: Bool](), count: N)
for r in 0..<N {
for c in 0..<N {
let val = board[r][c]
if val == "." {
continue
}
if rows[r][val] != nil {
return false
}
rows[r][val] = true
if cols[c][val] != nil {
return false
}
cols[c][val] = true
let idx = (r / 3) * 3 + (c / 3)
if boxes[idx][val] != nil {
return false
}
boxes[idx][val] = true
}
}
return true
}