Swift | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:1 325
مشترکین
-124 ساعت
+17 روز
-930 روز
آرشیو پست ها
1 325
Задача: 409. Longest Palindrome
Сложность: easy
Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.
Пример:
Input: s = "abccccdd" Output: 7👨💻 Алгоритм: 1⃣Создайте словарь для подсчета количества каждого символа в строке. 2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома. 3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа. 😎 Решение:
func longestPalindrome(_ s: String) -> Int {
var charCount = [Character: Int]()
for char in s {
charCount[char, default: 0] += 1
}
var length = 0
var oddFound = false
for count in charCount.values {
if count % 2 == 0 {
length += count
} else {
length += count - 1
oddFound = true
}
}
return oddFound ? length + 1 : length
}1 325
Задача: 1243. Array Transformation
Сложность: easy
Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.
Пример:
Input: arr = [6,2,3,4] Output: [6,3,3,4]👨💻 Алгоритм: 1⃣Инициализация нового массива с такими же значениями, как у исходного массива. Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться. 2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей. Если элемент меньше своего левого и правого соседей, увеличиваем его. Если элемент больше своего левого и правого соседей, уменьшаем его. 3⃣Первый и последний элементы массива остаются неизменными. 😎 Решение:
class Solution {
func transformArray(_ arr: [Int]) -> [Int] {
var arr = arr
var changed = false
repeat {
changed = false
var newArr = arr
for i in 1..<arr.count - 1 {
if arr[i] < arr[i - 1] && arr[i] < arr[i + 1] {
newArr[i] += 1
changed = true
} else if arr[i] > arr[i - 1] && arr[i] > arr[i + 1] {
newArr[i] -= 1
changed = true
}
}
arr = newArr
} while changed
return arr
}
}1 325
Задача: 926. Flip String to Monotone Increasing
Сложность: medium
Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.
Пример:
Input: s = "00110" Output: 1👨💻 Алгоритм: 1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0). 2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1). Пройти по строке и заполнить массивы left и right. 3⃣Пройти по строке и найти минимальное количество операций, чтобы сделать всю строку монотонной. 😎 Решение:
class Solution {
func minFlipsMonoIncr(_ s: String) -> Int {
let n = s.count
var left = [Int](repeating: 0, count: n + 1)
var right = [Int](repeating: 0, count: n + 1)
let sArray = Array(s)
for i in 0..<n {
left[i + 1] = left[i] + (sArray[i] == "1" ? 1 : 0)
}
for i in (0..<n).reversed() {
right[i] = right[i + 1] + (sArray[i] == "0" ? 1 : 0)
}
var result = Int.max
for i in 0...n {
result = min(result, left[i] + right[i])
}
return result
}
}1 325
Задача: 268. Missing Number
Сложность: easy
Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.
Пример:
Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.👨💻 Алгоритм: 1⃣Сначала отсортируйте массив nums. 2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце. 3⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число. 😎 Решение:
class Solution {
func missingNumber(_ nums: [Int]) -> Int {
let sortedNums = nums.sorted()
if sortedNums.last != sortedNums.count {
return sortedNums.count
} else if sortedNums.first != 0 {
return 0
}
for i in 1..<sortedNums.count {
let expectedNum = sortedNums[i - 1] + 1
if sortedNums[i] != expectedNum {
return expectedNum
}
}
return -1
}
}1 325
Задача: 1273. Delete Tree Nodes
Сложность: medium
Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.
Пример:
Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1] Output: 2👨💻 Алгоритм: 1⃣Постройте дерево из заданных узлов, значений и родителей. 2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю. 3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов. 😎 Решение:
class Solution {
func deleteTreeNodes(_ nodes: Int, _ parent: [Int], _ value: [Int]) -> Int {
var tree = [Int: [Int]]()
for i in 0..<nodes {
tree[parent[i], default: []].append(i)
}
func dfs(_ node: Int) -> (Int, Int) {
var totalSum = value[node]
var totalCount = 1
if let children = tree[node] {
for child in children {
let (childSum, childCount) = dfs(child)
totalSum += childSum
totalCount += childCount
}
}
return totalSum == 0 ? (0, 0) : (totalSum, totalCount)
}
return dfs(0).1
}
}1 325
Задача: 640. Solve the Equation
Сложность: medium
Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.
Пример:
Input: s = "*" Output: 9👨💻 Алгоритм: 1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='. 2⃣Парсинг и упрощение: Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений. 3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'. 😎 Решение:
class Solution {
func solveEquation(_ equation: String) -> String {
func parse(_ s: String) -> (Int, Int) {
var coeff = 0
var constPart = 0
var sign = 1
var num = 0
var i = s.startIndex
while i < s.endIndex {
if s[i] == "+" {
sign = 1
i = s.index(after: i)
} else if s[i] == "-" {
sign = -1
i = s.index(after: i)
} else if s[i].isNumber {
num = 0
while i < s.endIndex && s[i].isNumber {
num = num * 10 + s[i].wholeNumberValue!
i = s.index(after: i)
}
if i < s.endIndex && s[i] == "x" {
coeff += sign * num
i = s.index(after: i)
} else {
constPart += sign * num
}
} else if s[i] == "x" {
coeff += sign
i = s.index(after: i)
}
}
return (coeff, constPart)
}
let parts = equation.split(separator: "=")
let (leftCoeff, leftConst) = parse(String(parts[0]))
let (rightCoeff, rightConst) = parse(String(parts[1]))
let coeff = leftCoeff - rightCoeff
let constPart = rightConst - leftConst
if coeff == 0 {
return constPart == 0 ? "Infinite solutions" : "No solution"
}
return "x=\(constPart / coeff)"
}
}1 325
Задача: 1265. Print Immutable Linked List in Reverse
Сложность: medium
Вам дан неизменяемый связный список, распечатайте все значения каждого узла в обратном порядке с помощью следующего интерфейса: ImmutableListNode:Интерфейс неизменяемого связанного списка, вам дана голова списка. Для доступа к связанному списку необходимо использовать следующие функции (напрямую к ImmutableListNode обращаться нельзя): ImmutableListNode.printValue(): Выводит значение текущего узла. ImmutableListNode.getNext(): Возвращает следующий узел. Входные данные даются только для внутренней инициализации связанного списка.Вы должны решить эту задачу, не изменяя связанный список. Другими словами, вы должны работать со связанным списком, используя только упомянутые API.
Пример:
Input: head = [1,2,3,4] Output: [4,3,2,1]👨💻 Алгоритм: 1⃣Используйте рекурсию для достижения конца связного списка. 2⃣На обратном пути рекурсии распечатайте значение каждого узла. 3⃣Обратный порядок достигается благодаря природе рекурсии (стек вызовов). 😎 Решение:
protocol ImmutableListNode {
func printValue()
func getNext() -> ImmutableListNode?
}
class Solution {
func printLinkedListInReverse(_ head: ImmutableListNode?) {
if let next = head?.getNext() {
printLinkedListInReverse(next)
}
head?.printValue()
}
}1 325
Задача: 1114. Print in Order
Сложность: easy
Предположим, у нас есть класс:
public class Foo {
public void first() { print("first"); }
public void second() { print("second"); }
public void third() { print("third"); }
}Input: nums = [1,2,3] Output: "firstsecondthird" Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.👨💻 Алгоритм: 1⃣Инициализация переменных: Инициализируйте координационные переменные firstJobDone и secondJobDone, чтобы указать, что задания еще не выполнены. 2⃣Функция first(): В этой функции нет зависимости, поэтому можно сразу приступить к выполнению задания. В конце функции обновите переменную firstJobDone, чтобы указать, что первое задание выполнено. 3⃣Функции second() и third(): В функции second() проверьте статус firstJobDone. Если она не обновлена, подождите, иначе переходите к выполнению второго задания. В конце функции обновите переменную secondJobDone, чтобы отметить завершение второго задания. В функции third() проверьте статус secondJobDone. Аналогично функции second(), подождите сигнала secondJobDone перед тем, как приступить к выполнению третьего задания. 😎 Решение:
import Foundation
class Foo {
private let firstJobDone = DispatchSemaphore(value: 0)
private let secondJobDone = DispatchSemaphore(value: 0)
func first(_ printFirst: () -> Void) {
printFirst()
firstJobDone.signal()
}
func second(_ printSecond: () -> Void) {
firstJobDone.wait()
printSecond()
secondJobDone.signal()
}
func third(_ printThird: () -> Void) {
secondJobDone.wait()
printThird()
}
}1 325
Задача: 63. Unique Paths II
Сложность: medium
Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.
Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями.
Верните количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла.
Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.
Пример:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right👨💻 Алгоритм: 1⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем. 2⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца. 3⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях. 😎 Решение:
func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
let R = obstacleGrid.count
let C = obstacleGrid[0].count
if obstacleGrid[0][0] == 1 {
return 0
}
var grid = obstacleGrid
grid[0][0] = 1
for i in 1..<R {
grid[i][0] = grid[i][0] == 0 && grid[i - 1][0] == 1 ? 1 : 0
}
for i in 1..<C {
grid[0][i] = grid[0][i] == 0 && grid[0][i - 1] == 1 ? 1 : 0
}
for i in 1..<R {
for j in 1..<C {
if grid[i][j] == 0 {
grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
} else {
grid[i][j] = 0
}
}
}
return grid[R - 1][C - 1]
}1 325
Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium
Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).
Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.
Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.
Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.
Пример:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).class Solution {
func dfs(_ node: Int, _ parent: Int, _ adj: [Int: [Int]], _ labels: [Character], _ ans: inout [Int]) -> [Int] {
var nodeCounts = [Int](repeating: 0, count: 26)
nodeCounts[Int(labels[node].asciiValue! - Character("a").asciiValue!)] = 1
guard let children = adj[node] else {
return nodeCounts
}
for child in children {
if child == parent {
continue
}
let childCounts = dfs(child, node, adj, labels, &ans)
for i in 0..<26 {
nodeCounts[i] += childCounts[i]
}
}
ans[node] = nodeCounts[Int(labels[node].asciiValue! - Character("a").asciiValue!)]
return nodeCounts
}
func countSubTrees(_ n: Int, _ edges: [[Int]], _ labels: String) -> [Int] {
var adj = [Int: [Int]]()
for edge in edges {
adj[edge[0], default: []].append(edge[1])
adj[edge[1], default: []].append(edge[0])
}
var ans = [Int](repeating: 0, count: n)
let labelsArray = Array(labels)
_ = dfs(0, -1, adj, labelsArray, &ans)
return ans
}
}1 325
Задача: 1326. Minimum Number of Taps to Open to Water a Garden
Сложность: hard
Есть одномерный сад на оси x. Сад начинается в точке 0 и заканчивается в точке n. (т.е. длина сада равна n).
В саду есть n + 1 кранов, расположенных в точках [0, 1, ..., n].
Даны целое число n и целочисленный массив ranges длиной n + 1, где ranges[i] (индексация начинается с 0) означает, что i-й кран может поливать область [i - ranges[i], i + ranges[i]], если он открыт.
Верните минимальное количество кранов, которые должны быть открыты для полива всего сада. Если сад невозможно полить, верните -1.
Пример:
Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]class Solution {
func minTaps(_ n: Int, _ ranges: [Int]) -> Int {
let INF = Int.max
var dp = [Int](repeating: INF, count: n + 1)
dp[0] = 0
for i in 0...n {
let tapStart = max(0, i - ranges[i])
let tapEnd = min(n, i + ranges[i])
for j in tapStart...tapEnd {
dp[tapEnd] = min(dp[tapEnd], dp[j] + 1)
}
}
return dp[n] == INF ? -1 : dp[n]
}
}1 325
Задача: 1019. Next Greater Node In Linked List
Сложность: medium
Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.
Пример:
Input: head = [2,1,5] Output: [5,5,0]👨💻 Алгоритм: 1⃣Инициализация переменных: Пройдитесь по всему списку и сохраните значения узлов в массив. Инициализируйте стек для хранения индексов узлов, которые нужно обработать. 2⃣Поиск следующего большего элемента: Итерируйте по массиву значений узлов. Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека. Добавьте текущий индекс в стек. 3⃣Заполнение оставшихся значений: Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента. 😎 Решение:
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 nextLargerNodes(_ head: ListNode?) -> [Int] {
var values = [Int]()
var current = head
while current != nil {
values.append(current!.val)
current = current?.next
}
var answer = [Int](repeating: 0, count: values.count)
var stack = [Int]()
for i in 0..<values.count {
while !stack.isEmpty && values[stack.last!] < values[i] {
answer[stack.removeLast()] = values[i]
}
stack.append(i)
}
return answer
}
}1 325
Задача: 372. Super Pow
Сложность: medium
Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.
Пример:
Input: a = 2, b = [3] Output: 8👨💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:
class Solution {
func getSum(_ a: Int, _ b: Int) -> Int {
var x = abs(a), y = abs(b)
if x < y {
return getSum(b, a)
}
let sign = a > 0 ? 1 : -1
if a * b >= 0 {
while y != 0 {
let carry = (x & y) << 1
x ^= y
y = carry
}
} else {
while y != 0 {
let borrow = ((~x) & y) << 1
x ^= y
y = borrow
}
}
return x * sign
}
}1 325
Задача: 1245. Tree Diameter
Сложность: medium
Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.
Пример:
Input: edges = [[0,1],[0,2]] Output: 2👨💻 Алгоритм: 1⃣Построение графа: Используем представление графа в виде списка смежности. 2⃣Поиск самой удаленной вершины (DFS1): Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее. 3⃣Поиск диаметра (DFS2): Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:
class Solution {
func treeDiameter(_ edges: [[Int]]) -> Int {
if edges.isEmpty { return 0 }
var graph = [Int: [Int]]()
for edge in edges {
graph[edge[0], default: []].append(edge[1])
graph[edge[1], default: []].append(edge[0])
}
var farthestNode = 0
func dfs(_ node: Int, _ parent: Int) -> Int {
var maxDepth = 0
for neighbor in graph[node]! {
if neighbor != parent {
let depth = dfs(neighbor, node)
if depth + 1 > maxDepth {
maxDepth = depth + 1
farthestNode = neighbor
}
}
}
return maxDepth
}
_ = dfs(0, -1)
let startNode = farthestNode
_ = dfs(startNode, -1)
return dfs(farthestNode, -1)
}
}1 325
Задача: 560. Subarray Sum Equals K
Сложность: medium
Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.
Подмассив - это непрерывная непустая последовательность элементов внутри массива.
Пример:
Input: nums = [1,1,1], k = 2 Output: 2👨💻 Алгоритм: 1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums. 2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k. 3⃣Всякий раз, когда сумма равна k, увеличить счетчик, используемый для хранения необходимого результата. 😎 Решение:
class Solution {
func subarraySum(_ nums: [Int], _ k: Int) -> Int {
var count = 0
for start in 0..<nums.count {
for end in (start + 1)...nums.count {
var sum = 0
for i in start..<end {
sum += nums[i]
}
if sum == k {
count += 1
}
}
}
return count
}
}1 325
Задача: №18. 4Sum
Сложность: medium
Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 <= a, b, c, d < n
- a, b, c и d различны.
- nums[a] + nums[b] + nums[c] + nums[d] == target
Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]👨💻 Алгоритм: 1⃣Отсортировать массив для удобного пропуска дубликатов и эффективного поиска. 2⃣Использовать два вложенных цикла для выбора первых двух чисел и два указателя для поиска оставшихся двух чисел. 3⃣Обрабатывать дубликаты, чтобы избежать повторяющихся четверок. 😎 Решение:
class Solution {
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let len = nums.count
guard len >= 4 else { return [] }
var result = [[Int]]()
let sort = nums.sorted()
for a in 0..<(len - 3) {
if a > 0, sort[a] == sort[a - 1] { continue }
for b in (a + 1)..<(len - 2) {
if b > a + 1, sort[b] == sort[b - 1] { continue }
var c = b + 1, d = len - 1
while c < d {
let sum = sort[a] + sort[b] + sort[c] + sort[d]
if sum == target {
result.append([sort[a], sort[b], sort[c], sort[d]])
repeat { c += 1 } while c < d && sort[c] == sort[c - 1]
repeat { d -= 1 } while c < d && sort[d] == sort[d + 1]
} else if sum < target {
c += 1
} else {
d -= 1
}
}
}
}
return result
}
}1 325
Задача: 717. 1-bit and 2-bit Characters
Сложность: easy
У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.
Пример:
Input: bits = [1,0,0] Output: true👨💻 Алгоритм: 1⃣Инициализируйте индекс для итерации по массиву. 2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1. 3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат. 😎 Решение:
func isOneBitCharacter(_ bits: [Int]) -> Bool {
var i = 0
while i < bits.count - 1 {
i += bits[i] + 1
}
return i == bits.count - 1
}1 325
Задача: 225. Implement Stack using Queues
Сложность: easy
Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).
Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.
Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.
Пример:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return Falseclass MyStack {
private var q1 = [Int]()
private var q2 = [Int]()
private var topElement: Int = 0
func push(_ x: Int) {
q2.append(x)
topElement = x
while !q1.isEmpty {
q2.append(q1.removeFirst())
}
(q1, q2) = (q2, q1)
}
func pop() {
q1.removeFirst()
if !q1.isEmpty {
topElement = q1.first!
}
}
func empty() -> Bool {
return q1.isEmpty
}
func top() -> Int {
return topElement
}
}1 325
Задача: 908. Smallest Range I
Сложность: easy
Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем.
Пример:
Input: nums = [1], k = 0 Output: 0👨💻 Алгоритм: 1⃣Найти минимальное и максимальное значения массива nums. 2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции. 3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями. 😎 Решение:
class Solution {
func smallestRangeI(_ nums: [Int], _ k: Int) -> Int {
let minVal = nums.min()!
let maxVal = nums.max()!
return max(0, (maxVal - k) - (minVal + k))
}
}1 325
Задача: 339. Nested List Weight Sum
Сложность: medium
Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.
Верните сумму каждого целого числа в nestedList, умноженного на его глубину.
Пример:
Input: nestedList = [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.👨💻 Алгоритм: 1⃣ Инициализация и вызов рекурсивной функции: Создайте основную функцию, которая принимает вложенный список и вызывает вспомогательную рекурсивную функцию с начальной глубиной 1. 2⃣ Рекурсивное исследование списка: В вспомогательной функции пройдите по каждому элементу списка. Если элемент является целым числом, добавьте его значение, умноженное на текущую глубину, к общей сумме. Если элемент является списком, вызовите вспомогательную функцию рекурсивно с увеличенной глубиной. 3⃣ Возврат результата: Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму. 😎 Решение:
class Solution {
func depthSum(_ nestedList: [NestedInteger]) -> Int {
return dfs(nestedList, 1)
}
private func dfs(_ list: [NestedInteger], _ depth: Int) -> Int {
var total = 0
for nested in list {
if nested.isInteger() {
total += nested.getInteger() * depth
} else {
total += dfs(nested.getList(), depth + 1)
}
}
return total
}
}