Swift | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
显示更多
网络:1 339
订阅者
-124 小时
-87 天
-2530 天
帖子存档
1 339
#easy
Задача: 35. Search Insert Position
Дан отсортированный массив уникальных целых чисел и целевое значение. Верните индекс, если цель найдена. Если нет, верните индекс, где она должна быть вставлена в соответствии с порядком.
Вы должны написать алгоритм со временной сложностью O(log n).
Пример:
Input: nums = [1,3,5,6], target = 5 Output: 2👨💻 Алгоритм: 1️⃣Инициализируйте указатели left и right: left = 0, right = n - 1. 2️⃣Пока left <= right: Сравните средний элемент массива nums[pivot] с целевым значением target. Если средний элемент является целевым, то есть target == nums[pivot]: верните pivot. Если цель не найдена: Если target < nums[pivot], продолжайте поиск в левом подмассиве. right = pivot - 1. Иначе продолжайте поиск в правом подмассиве. left = pivot + 1. 3️⃣Верните left. 😎 Решение:
class Solution {
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let pivot = left + (right - left) / 2
if nums[pivot] == target {
return pivot
}
if target < nums[pivot] {
right = pivot - 1
} else {
left = pivot + 1
}
}
return left
}
}1 339
#medium
Задача: 34. Find First and Last Position of Element in Sorted Array
Дан массив целых чисел nums, отсортированный в неубывающем порядке, найдите начальную и конечную позицию заданного целевого значения.
Если целевое значение не найдено в массиве, верните [-1, -1].
Вы должны написать алгоритм со временной сложностью O(log n).
Пример:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]👨💻 Алгоритм: 1️⃣Определите функцию под названием findBound, которая принимает три аргумента: массив, целевое значение для поиска и булевое значение isFirst, указывающее, ищем ли мы первое или последнее вхождение цели. Мы используем 2 переменные для отслеживания подмассива, который мы сканируем. Назовем их begin и end. Изначально begin устанавливается в 0, а end — в последний индекс массива. 2️⃣Мы итерируем, пока begin не станет больше, чем end. На каждом шаге мы вычисляем средний элемент mid = (begin + end) / 2. Мы используем значение среднего элемента, чтобы решить, какую половину массива нам нужно искать. Если nums[mid] == target: Если isFirst true — это означает, что мы пытаемся найти первое вхождение элемента. Если mid == begin или nums[mid - 1] != target, тогда мы возвращаем mid как первое вхождение цели. В противном случае мы обновляем end = mid - 1. Если isFirst false — это означает, что мы пытаемся найти последнее вхождение элемента. Если mid == end или nums[mid + 1] != target, тогда мы возвращаем mid как последнее вхождение цели. В противном случае мы обновляем begin = mid + 1. 3️⃣Если nums[mid] > target — мы обновляем end = mid - 1, так как мы должны отбросить правую сторону массива, поскольку средний элемент больше цели. Если nums[mid] < target — мы обновляем begin = mid + 1, так как мы должны отбросить левую сторону массива, поскольку средний элемент меньше цели. В конце нашей функции мы возвращаем значение -1, что указывает на то, что цель не найдена в массиве. В основной функции searchRange мы сначала вызываем findBound с isFirst, установленным в true. Если это значение равно -1, мы можем просто вернуть [-1, -1]. В противном случае мы вызываем findBound с isFirst, установленным в false, чтобы получить последнее вхождение, а затем возвращаем результат. 😎 Решение:
func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
let firstOccurrence = findBound(nums, target, true)
if firstOccurrence == -1 {
return [-1, -1]
}
let lastOccurrence = findBound(nums, target, false)
return [firstOccurrence, lastOccurrence]
}
func findBound(_ nums: [Int], _ target: Int, _ isFirst: Bool) -> Int {
let N = nums.count
var begin = 0
var end = N - 1
while begin <= end {
let mid = (begin + end) / 2
if nums[mid] == target {
if isFirst {
if mid == begin || nums[mid - 1] != target {
return mid
}
end = mid - 1
} else {
if mid == end || nums[mid + 1] != target {
return mid
}
begin = mid + 1
}
} else if nums[mid] > target {
end = mid - 1
} else {
begin = mid + 1
}
}
return -1
}1 339
Задача: 29. Divide Two Integers #medium
Условие:
Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора. Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2. Возвращает частное после деления делимого на делитель. Примечание. Предположим, мы имеем дело со средой, которая может хранить целые числа только в пределах 32-битного целого диапазона со знаком: [−2^31, 2^31 − 1]. В этой задаче, если частное строго больше 2^31 - 1, верните 2^31 - 1, а если частное строго меньше -2^31, верните -2^31.Решение:
func divide(_ dividend: Int, _ divisor: Int) -> Int {
// Особые случаи: деление на ноль или делитель равен нулю
if divisor == 0 || (dividend == Int.min && divisor == -1) {
return Int.max
}
// Определение знака результата
let isNegative = (dividend < 0) != (divisor < 0)
// Приведение чисел к абсолютным значениям и приведение их к типу Int64,
// чтобы избежать переполнения при работе с Int32.
var absDividend = abs(Int64(dividend))
let absDivisor = abs(Int64(divisor))
// Инициализация результата
var result: Int64 = 0
// Выполнение деления путем вычитания
while absDividend >= absDivisor {
var tempDivisor = absDivisor
var multiple: Int64 = 1
// Увеличиваем делитель в два раза, пока он не станет больше чем делимое
while absDividend >= (tempDivisor << 1) {
tempDivisor <<= 1
multiple <<= 1
}
// Вычитаем делитель из делимого и обновляем результат
absDividend -= tempDivisor
result += multiple
}
// Применяем знак к результату и проверяем на переполнение
if isNegative {
result = -result
}
if result > Int64(Int32.max) {
return Int(Int32.max)
} else if result < Int64(Int32.min) {
return Int(Int32.min)
} else {
return Int(result)
}
}
// Пример использования
let dividend = 10
let divisor = 3
let quotient = divide(dividend, divisor)
print("Частное деления \(dividend) на \(divisor) равно \(quotient)") 1. Особые случаи: - Проверяем случаи деления на ноль или когда делимое равно Int.min, а делитель равен -1, что приведет к переполнению. В таких случаях возвращаем максимальное значение Int. 2. Определение знака результата: - Определяем знак результата деления на основе знаков делимого и делителя. 3. Приведение к абсолютным значениям: - Приводим числа к абсолютным значениям для удобства работы и чтобы избежать проблем с переполнением. 4. Цикл деления путем вычитания: - Используем цикл, в котором делимое вычитается наибольшими возможными кратными значениями делителя, умноженными на степень двойки (tempDivisor <<= 1). 5. Применение знака и проверка на переполнение: - Применяем знак к результату, затем проверяем, не превышает ли результат допустимый диапазон Int32. Если превышает, возвращаем максимальное или минимальное значение Int32. Этот подход эффективно решает задачу деления целых чисел без использования операторов умножения, деления и модуля, с учетом всех особых случаев и ограничений задачи.
1 339
#medium
Задача: 33. Search in Rotated Sorted Array
Есть массив целых чисел nums, отсортированный в порядке возрастания (с уникальными значениями).
Перед передачей в вашу функцию массив nums может быть повёрнут в неизвестном индексе поворота k (1 <= k < nums.length), так что результирующий массив будет иметь вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексацией с нуля). Например, [0,1,2,4,5,6,7] может быть повёрнут в индексе поворота 3 и стать [4,5,6,7,0,1,2].
Для данного массива nums после возможного поворота и целого числа target, верните индекс target, если он есть в массиве, или -1, если его нет в массиве.
Вы должны написать алгоритм с временной сложностью O(log n).
Пример:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4👨💻 Алгоритм: 1️⃣Выполните двоичный поиск для определения индекса поворота, инициализируя границы области поиска значениями left = 0 и right = n - 1. Пока left < right: Пусть mid = left + (right - left) // 2. Если nums[mid] > nums[n - 1], это предполагает, что точка поворота находится справа от mid, следовательно, мы устанавливаем left = mid + 1. В противном случае, поворот может находиться на позиции mid или левее от mid, в этом случае мы должны установить right = mid. 2️⃣По завершении двоичного поиска мы имеем индекс поворота, обозначенный как pivot = left. nums состоит из двух отсортированных подмассивов, nums[0 ~ left - 1] и nums[left ~ n - 1]. 3️⃣Выполните двоичный поиск по подмассиву nums[0 ~ left - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс. В противном случае выполните двоичный поиск по подмассиву nums[left ~ n - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс. В противном случае верните -1. 😎 Решение:
func search(_ nums: [Int], _ target: Int) -> Int {
let n = nums.count
var left = 0
var right = n - 1
// Find the index of the pivot element (the smallest element)
while left <= right {
let mid = (left + right) / 2
if nums[mid] > nums[n - 1] {
left = mid + 1
} else {
right = mid - 1
}
}
func binarySearch(_ leftBoundary: Int, _ rightBoundary: Int, _ target: Int) -> Int {
var left = leftBoundary
var right = rightBoundary
while left <= right {
let mid = (left + right) / 2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
return -1
}
// Binary search over elements on the pivot element's left
let answer = binarySearch(0, left - 1, target)
if answer != -1 {
return answer
}
// Binary search over elements on the pivot element's right
return binarySearch(left, n - 1, target)
}1 339
#hard
Задача: 32. Longest Valid Parentheses
Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.
Пример:
Input: s = "(()" Output: 2👨💻 Алгоритм: 1️⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека. 2️⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной. 3️⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки. 😎 Решение:
func isValid(_ s: String) -> Bool {
var stack = [Character]()
for char in s {
if char == "(" {
stack.append("(")
} else if !stack.isEmpty && stack.last == "(" {
stack.removeLast()
} else {
return false
}
}
return stack.isEmpty
}
func longestValidParentheses(_ s: String) -> Int {
var maxlen = 0
for i in 0..<s.count {
for j in stride(from: i + 2, through: s.count, by: 2) {
let start = s.index(s.startIndex, offsetBy: i)
let end = s.index(s.startIndex, offsetBy: j)
let substring = String(s[start..<end])
if isValid(substring) {
maxlen = max(maxlen, j - i)
}
}
}
return maxlen
}1 339
Задача: 28. Find the Index of the First Occurrence in a String #easy
Условие:
Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена.Решение:
func findNeedleInHaystack(_ haystack: String, _ needle: String) -> Int {
if let range = haystack.range(of: needle) {
return haystack.distance(from: haystack.startIndex, to: range.lowerBound)
} else {
return -1
}
}
// Пример использования
let haystack = "стог сена"
let needle = "игла"
let index = findNeedleInHaystack(haystack, needle)
print("Индекс первого вхождения иглы в стог сена:", index)1. Функция findNeedleInHaystack: - Принимает две строки: haystack (стог сена) и needle (игла). - Использует метод range(of:) для поиска первого вхождения подстроки needle в строке haystack. - Если подстрока найдена (range не равен nil), вычисляется индекс первого символа подстроки needle в строке haystack с помощью метода distance(from:to:). - Возвращается найденный индекс. - Если подстрока не найдена, возвращается -1. Пример использованияия: - Создается строка haystack с текстом "стог сена". - Создается строка needle с текстом "игла". - Функция вызывается с этими строками, и результат (индекс или -1) выводится на экран. Этот код эффективно находит первое вхождение подстроки в строке, сохраняя относительный порядок символов и возвращая соответствующий индекс или -1, если подстрока не найдена.
1 339
#medium
Задача: 31. Next Permutation
Перестановка массива целых чисел — это упорядочивание его элементов в последовательность или линейный порядок.
Например, для 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 найдите следующую перестановку nums.
Замена должна быть выполнена на месте и использовать только постоянную дополнительную память.
Пример:
Input: nums = [1,2,3] Output: [1,3,2]👨💻 Алгоритм: 1️⃣Мы меняем местами числа a[i−1] и a[j]. Теперь у нас есть правильное число на индексе i−1. Однако текущая перестановка ещё не является той перестановкой, которую мы ищем. Нам нужна наименьшая перестановка, которая может быть сформирована с использованием чисел только справа от a[i−1]. Следовательно, нам нужно расположить эти числа в порядке возрастания, чтобы получить их наименьшую перестановку. 2️⃣Однако, вспомните, что, сканируя числа справа налево, мы просто уменьшали индекс, пока не нашли пару a[i] и a[i−1], где a[i] > a[i−1]. Таким образом, все числа справа от a[i−1] уже были отсортированы в порядке убывания. Более того, обмен местами a[i−1] и a[j] не изменил этот порядок. 3️⃣Поэтому нам просто нужно перевернуть числа, следующие за a[i−1], чтобы получить следующую наименьшую лексикографическую перестановку. 😎 Решение:
func nextPermutation(_ nums: inout [Int]) {
var i = nums.count - 2
while i >= 0 && nums[i + 1] <= nums[i] {
i -= 1
}
if i >= 0 {
var j = nums.count - 1
while nums[j] <= nums[i] {
j -= 1
}
nums.swapAt(i, j)
}
reverse(nums: &nums, start: i + 1)
}
func reverse(nums: inout [Int], start: Int) {
var i = start
var j = nums.count - 1
while i < j {
nums.swapAt(i, j)
i += 1
j -= 1
}
}1 339
Задача: 30. Substring with Concatenation of All Words #hard
Условие:
Вам дана строка s и массив строк-слов. Все строки слов имеют одинаковую длину. Объединенная строка — это строка, которая в точности содержит все строки любой перестановки объединенных слов. Например, если слова = ["ab", "cd", "ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются объединенными строками. «acdbef» не является объединенной строкой, поскольку не является объединением какой-либо перестановки слов. Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.Решение:
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 339
Задача: 27. Remove Element #easy
Условие:
Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val. Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее: Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums. Вернуть К.Решение:
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
var k = 0 // Индекс для элементов, не равных val
for i in 0..<nums.count {
if nums[i] != val {
nums[k] = nums[i]
k += 1
}
}
return k
}
// Пример использования
var nums = [3, 2, 2, 3]
let val = 3
let k = removeElement(&nums, val)
print("Количество элементов, не равных \(val):", k) // Вывод: Количество элементов, не равных 3: 2
print("Массив с элементами, не равными \(val):", nums.prefix(k)) // Вывод: Массив с элементами, не равными 3: [2, 2]Пояснение:
1. Функция removeElement: - Принимает массив nums и значение val, которое нужно удалить. - Инициализирует переменную k для отслеживания индекса элементов, которые не равны val. - Проходит по массиву nums и для каждого элемента, который не равен val, помещает его на позицию k и увеличивает k. - Возвращает k, который представляет количество элементов, не равных val. 2. Пример использования: - Создается массив nums с элементами [3, 2, 2, 3] и значение val = 3. - Функция вызывается с этими параметрами, и результат (количество элементов, не равных val и измененный массив nums) выводится на экран. Этот код эффективно решает задачу удаления всех вхождений значения val из массива nums на месте и возвращает количество элементов, которые не равны val, что соответствует требованиям задачи.
1 339
Задача: 29. Divide Two Integers #medium
Условие:
Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора. Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2. Возвращает частное после деления делимого на делитель. Примечание. Предположим, мы имеем дело со средой, которая может хранить целые числа только в пределах 32-битного целого диапазона со знаком: [−2^31, 2^31 − 1]. В этой задаче, если частное строго больше 2^31 - 1, верните 2^31 - 1, а если частное строго меньше -2^31, верните -2^31.Решение:
func divide(_ dividend: Int, _ divisor: Int) -> Int {
// Особые случаи: деление на ноль или делитель равен нулю
if divisor == 0 || (dividend == Int.min && divisor == -1) {
return Int.max
}
// Определение знака результата
let isNegative = (dividend < 0) != (divisor < 0)
// Приведение чисел к абсолютным значениям и приведение их к типу Int64,
// чтобы избежать переполнения при работе с Int32.
var absDividend = abs(Int64(dividend))
let absDivisor = abs(Int64(divisor))
// Инициализация результата
var result: Int64 = 0
// Выполнение деления путем вычитания
while absDividend >= absDivisor {
var tempDivisor = absDivisor
var multiple: Int64 = 1
// Увеличиваем делитель в два раза, пока он не станет больше чем делимое
while absDividend >= (tempDivisor << 1) {
tempDivisor <<= 1
multiple <<= 1
}
// Вычитаем делитель из делимого и обновляем результат
absDividend -= tempDivisor
result += multiple
}
// Применяем знак к результату и проверяем на переполнение
if isNegative {
result = -result
}
if result > Int64(Int32.max) {
return Int(Int32.max)
} else if result < Int64(Int32.min) {
return Int(Int32.min)
} else {
return Int(result)
}
}
// Пример использования
let dividend = 10
let divisor = 3
let quotient = divide(dividend, divisor)
print("Частное деления \(dividend) на \(divisor) равно \(quotient)") 1 339
Задача: 28. Find the Index of the First Occurrence in a String #easy
Условие:
Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена.Решение:
func findNeedleInHaystack(_ haystack: String, _ needle: String) -> Int {
if let range = haystack.range(of: needle) {
return haystack.distance(from: haystack.startIndex, to: range.lowerBound)
} else {
return -1
}
}
// Пример использования
let haystack = "стог сена"
let needle = "игла"
let index = findNeedleInHaystack(haystack, needle)
print("Индекс первого вхождения иглы в стог сена:", index)1 339
Задача: 26. Remove Duplicates from Sorted Array #easy
Условие:
Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов в числах. Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее: Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums. Вернуть К.Решение:
func removeDuplicates(_ nums: inout [Int]) -> Int {
if nums.isEmpty { return 0 }
var k = 1 // Индекс для уникальных элементов
for i in 1..<nums.count {
if nums[i] != nums[k - 1] {
nums[k] = nums[i]
k += 1
}
}
return k
}
// Пример использования
var nums = [1, 1, 2, 2, 2, 3, 4, 4, 5]
let k = removeDuplicates(&nums)
print("Количество уникальных элементов:", k) // Вывод: Количество уникальных элементов: 5
print("Массив с уникальными элементами:", nums.prefix(k)) // Вывод: Массив с уникальными элементами: [1, 2, 3, 4, 5]- В функции removeDuplicates используется переменная k для отслеживания текущей позиции для уникальных элементов. - Мы проходим по массиву, начиная с индекса 1, и сравниваем текущий элемент с предыдущим (на позиции k-1). - Если текущий элемент отличается от предыдущего, мы помещаем его на позицию k и увеличиваем k. - В конце функции возвращаем k, который содержит количество уникальных элементов. - Пример использования показывает, как после удаления дубликатов в массиве nums получается массив с уникальными элементами и выводится их количество.
1 339
Задача: 27. Remove Element #easy
Условие:
Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val. Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее: Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums. Вернуть К.Решение:
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
var k = 0 // Индекс для элементов, не равных val
for i in 0..<nums.count {
if nums[i] != val {
nums[k] = nums[i]
k += 1
}
}
return k
}
// Пример использования
var nums = [3, 2, 2, 3]
let val = 3
let k = removeElement(&nums, val)
print("Количество элементов, не равных \(val):", k) // Вывод: Количество элементов, не равных 3: 2
print("Массив с элементами, не равными \(val):", nums.prefix(k)) // Вывод: Массив с элементами, не равными 3: [2, 2]Пояснение:
1. Функция removeElement:
- Принимает массив nums и значение val, которое нужно удалить.
- Инициализирует переменную k для отслеживания индекса элементов, которые не равны val.
- Проходит по массиву nums и для каждого элемента, который не равен val, помещает его на позицию k и увеличивает k.
- Возвращает k, который представляет количество элементов, не равных val.
2. Пример использования:
- Создается массив nums с элементами [3, 2, 2, 3] и значение val = 3.
- Функция вызывается с этими параметрами, и результат (количество элементов, не равных val и измененный массив nums) выводится на экран.
Этот код эффективно решает задачу удаления всех вхождений значения val из массива nums на месте и возвращает количество элементов, которые не равны val, что соответствует требованиям задачи.1 339
Задача: 26. Remove Duplicates from Sorted Array #easy
Условие:
Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов в числах. Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее: Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums. Вернуть К.Решение:
func removeDuplicates(_ nums: inout [Int]) -> Int {
if nums.isEmpty { return 0 }
var k = 1 // Индекс для уникальных элементов
for i in 1..<nums.count {
if nums[i] != nums[k - 1] {
nums[k] = nums[i]
k += 1
}
}
return k
}
// Пример использования
var nums = [1, 1, 2, 2, 2, 3, 4, 4, 5]
let k = removeDuplicates(&nums)
print("Количество уникальных элементов:", k) // Вывод: Количество уникальных элементов: 5
print("Массив с уникальными элементами:", nums.prefix(k)) // Вывод: Массив с уникальными элементами: [1, 2, 3, 4, 5]1 339
Задача: 25. Reverse Nodes in k-Group #hard
Условие:
Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список. k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть. Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
if head == nil || k == 1 {
return head
}
let dummy = ListNode(0)
dummy.next = head
var current: ListNode? = dummy
var next: ListNode?
var prev: ListNode? = dummy
// Определяем длину списка
var count = 0
while current?.next != nil {
current = current?.next
count += 1
}
while count >= k {
current = prev?.next
next = current?.next
for _ in 1..<k {
current?.next = next?.next
next?.next = prev?.next
prev?.next = next
next = current?.next
}
prev = current
count -= k
}
return dummy.next
}
// Пример использования
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
let node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
if let reversedList = reverseKGroup(node1, 3) {
var current: ListNode? = reversedList
while current != nil {
print(current!.val, terminator: " ")
current = current?.next
}
}1. Определение структурыListNode: - КлассListNodeпредставляет узел связанного списка с полями для значения (val) и указателя на следующий узел (next). 2. Инициализация фиктивного узла (dummy): - Создаем фиктивный узел для упрощения обработки головы списка и устанавливаем егоnextна текущую голову спис Определение длины спискасписка: - Сначала определяем длину списка, чтобы знать, сколько полных групп поkузлов можно переставить. 4. Перестановка узлов поkза раз: - Пока оставшихся узлов хватает для полной группы поkузлов: - Устанавливаемcurrentна первый узел текущей группы, аnextна второй узел. - Перемещаем узлы в группе, изменяя указатели так, чтобы узлы были переставлены в обратном порядке. - После перестановки обновляемprevдля перехода к следующей группе. - Уменьшаемcountнаk, так как мы уже обработали одну Возвращение головы нового спискаого списка: - Возвращаемdummy.next, который теперь указывает на новую голову списка после всех перестановок. Пример использования В примере создается связанный список 1 -> 2 -> 3 -> 4 -> 5. После вызова функцииreverseKGroupсk = 3, узлы будут переставлены группами по три: 3 -> 2 -> 1 -> 4 -> 5. Результат выводится в консоль..
1 339
Задача: 25. Reverse Nodes in k-Group #hard
Условие:
Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список. k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть. Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
if head == nil || k == 1 {
return head
}
let dummy = ListNode(0)
dummy.next = head
var current: ListNode? = dummy
var next: ListNode?
var prev: ListNode? = dummy
// Определяем длину списка
var count = 0
while current?.next != nil {
current = current?.next
count += 1
}
while count >= k {
current = prev?.next
next = current?.next
for _ in 1..<k {
current?.next = next?.next
next?.next = prev?.next
prev?.next = next
next = current?.next
}
prev = current
count -= k
}
return dummy.next
}
// Пример использования
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
let node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
if let reversedList = reverseKGroup(node1, 3) {
var current: ListNode? = reversedList
while current != nil {
print(current!.val, terminator: " ")
current = current?.next
}
}1 339
Задача: 24. Swap Nodes in Pairs #medium
Условие:
Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы).Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
func swapPairs(_ head: ListNode?) -> ListNode? {
let dummy = ListNode(0)
dummy.next = head
var current: ListNode? = dummy
while current?.next != nil && current?.next?.next != nil {
let first = current?.next
let second = current?.next?.next
first?.next = second?.next
second?.next = first
current?.next = second
current = first
}
return dummy.next
}
// Пример использования
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
if let swappedList = swapPairs(node1) {
var current: ListNode? = swappedList
while current != nil {
print(current!.val, terminator: " ")
current = current?.next
}
}
1 339
Задача: 23. Merge k Sorted Lists #medium
Условие:
Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.Объедините все связанные списки в один отсортированный связанный список и верните его.Решение:
/**
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
var heap = [ListNode]()
// Инициализируем кучу начальными значениями из всех списков
for list in lists {
if let node = list {
heap.append(node)
}
}
// Определяем компаратор для кучи
heap.sort { $0.val < $1.val }
let dummy = ListNode(0)
var current: ListNode? = dummy
while !heap.isEmpty {
let smallest = heap.removeFirst()
current?.next = smallest
current = smallest
if let next = smallest.next {
var index = heap.firstIndex { $0.val > next.val } ?? heap.count
heap.insert(next, at: index)
}
}
return dummy.next
}
// Пример использования
let node1 = ListNode(1)
let node2 = ListNode(4)
let node3 = ListNode(5)
node1.next = node2
node2.next = node3
let node4 = ListNode(1)
let node5 = ListNode(3)
let node6 = ListNode(4)
node4.next = node5
node5.next = node6
let node7 = ListNode(2)
let node8 = ListNode(6)
node7.next = node8
let lists: [ListNode?] = [node1, node4, node7]
if let mergedList = mergeKLists(lists) {
var current: ListNode? = mergedList
while current != nil {
print(current!.val, terminator: " ")
current = current?.next
}
}
Основная идея
Задача состоит в объединении нескольких отсортированных связанных списков в один отсортированный связанный список. Для этого используется приоритетная очередь (min-heap) для эффективного извлечения минимального элемента среди всех текущих головных узлов списков.
Шаги решения
1. **Определение структуры
ListNode**:
- Это стандартная структура узла связанного списка, содержащая значение (val) и указатель на следующий узел (next).
Инициализация кучичи**:
- Создаем массив heap, который будет использоваться как куча для хранения текущих головных узлов всех списков.
- Заполняем кучу начальными узлами каждого списка из входного массива lists.
Сортировка кучичи**:
- Изначально сортируем кучу по значениям узлов. Это упрощает дальнейшую вставку новых элементов в отсортированном порядке.
4. Создание фиктивного узла (dummy):
- Создаем фиктивный узел, чтобы облегчить обработку головы результирующего списка.
- Используем указатель current, который будет перемещаться по новому связанному списОбработка кучиа кучи**:
- Пока куча не пуста, извлекаем минимальный элемент (первый элемент массива).
- Присоединяем этот элемент к результирующему списку.
- Если у извлеченного узла есть следующий узел, вставляем его в кучу в правильное место, чтобы сохранить сортировку.
- Для вставки нового элемента используем бинарный поиск для нахождения правильного места вставВозвращение результирующего спискасписка**:
- Возвращаем следующий элемент от фиктивного узла (dummy.next), который является головой нового отсортированного связанного списка.
Пример использования
В примере создаются три отсортированных связанных списка:
- Первый список: 1 -> 4 -> 5
- Второй список: 1 -> 3 -> 4
- Третий список: 2 -> 6
Функция mergeKLists объединяет эти списки в один отсортированный список: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6. Затем результаты выводятся в консоль.
Заключение
Этот алгоритм использует приоритетную очередь для эффективного объединения нескольких отсортированных связанных списков в один отсортированный список. Время выполнения оптимизировано за счет использования кучи для извлечения минимальных элементов и вставки новых элементов в правильном порядке.1 339
Задача:22. Generate Parentheses #Medium
Условие:
Учитывая n пар круглых скобок, напишите функцию для генерации всех комбинаций правильно сформированных круглых скобок.Решение:
import Foundation
func generateParenthesis(_ n: Int) -> [String] {
var result = [String]()
generate(current: "", open: 0, close: 0, max: n, result: &result)
return result
}
private func generate(current: String, open: Int, close: Int, max: Int, result: inout [String]) {
if current.count == max * 2 {
result.append(current)
return
}
if open < max {
generate(current: current + "(", open: open + 1, close: close, max: max, result: &result)
}
if close < open {
generate(current: current + ")", open: open, close: close + 1, max: max, result: &result)
}
}
// Пример использования:
let n = 3
let combinations = generateParenthesis(n)
print(combinations)
ПОсновная идея Задача заключается в том, чтобы сгенерировать все возможные комбинации правильно сформированных круглых скобок для заданного числа пар скобок. Решение основывается на рекурсивном подходе. Шаги решения 1. Инициализация и запуск рекурсии: - Функция, принимающая число пар скобок (n), создает пустой массив для хранения результатов и запускает рекурсивную функцию с начальными параметрами. 2. Рекурсивная функция: - В этой функции проверяется текущая длина строки скобок. Если длина достигла 2 * n (две скобки на каждую пару), текущая строка добавляется в массив результатов, и рекурсия завершается для этой ветви. 3. Добавление открывающей скобки: - Если количество открытых скобок меньше максимального (n), добавляется открывающая скобка, и рекурсивная функция вызывается снова с обновленным состоянием. 4. Добавление закрывающей скобки: - Если количество закрытых скобок меньше количества открытых, добавляется закрывающая скобка, и рекурсивная функция вызывается снова с обновленным состоянием. Логика работы - Рекурсивная функция строит строку скобок шаг за шагом, добавляя либо открывающую, либо закрывающую скобку, если это возможно. - Функция следит за тем, чтобы в любой момент времени количество закрывающих скобок не превышало количество открывающих, что гарантирует правильность формирования скобок. - Когда строка достигает длины 2 * n, она добавляется в массив результатов. Вывод В результате работы функции получается массив всех возможных комбинаций правильно сформированных скобок для заданного числа пар. Это достигается путем полного перебора всех возможных вариантов и отбора только тех, которые соответствуют условиям правильного формирования скобок.
1 339
Задача: №21. Merge Two Sorted Lists #easy
Условие:
Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.Решение:
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
// Base case
guard let list1 = list1 else { return list2 }
guard let list2 = list2 else { return list1 }
// Initialize the merged list's head and tail
var mergedHead: ListNode?
var mergedTail: ListNode?
// Compare the values of the current nodes of l1 and l2
if list1.val < list2.val {
mergedHead = list1
mergedTail = mergeTwoLists(list1.next, list2)
} else {
mergedHead = list2
mergedTail = mergeTwoLists(list1, list2.next)
}
// Set the mergedHead's next pointer to the mergedTail
mergedHead?.next = mergedTail
// Return the mergedHead
return mergedHead
}
}