Available now! Telegram Research 2025 — the year's key insights 
Swift | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more1 348
Subscribers
-224 hours
-47 days
-1630 days
Posts Archive
1 348
Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing
Сложность: hard
Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим.
В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j].
Если нет способа сделать arr1 строго возрастающим, верните -1.
Пример:
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].class Solution {
func makeArrayIncreasing(_ arr1: [Int], _ arr2: [Int]) -> Int {
let sortedArr2 = arr2.sorted()
var dp = [String: Int]()
func dfs(_ i: Int, _ prev: Int) -> Int {
if i == arr1.count { return 0 }
let key = "\(i)-\(prev)"
if let val = dp[key] { return val }
var cost = 2001
if arr1[i] > prev {
cost = dfs(i + 1, arr1[i])
}
if let idx = sortedArr2.firstIndex(where: { $0 > prev }) {
cost = min(cost, 1 + dfs(i + 1, sortedArr2[idx]))
}
dp[key] = cost
return cost
}
let result = dfs(0, -1)
return result < 2001 ? result : -1
}
}1 348
Задача: 1136. Parallel Courses
Сложность: medium
Вам дано целое число n, которое указывает, что есть n курсов, обозначенных от 1 до n. Вам также дан массив relations, где relations[i] = [prevCoursei, nextCoursei], представляющий собой зависимость между курсами: курс prevCoursei должен быть пройден до курса nextCoursei.
За один семестр вы можете взять любое количество курсов, при условии, что вы прошли все необходимые предварительные курсы в предыдущем семестре для тех курсов, которые вы собираетесь взять.
Верните минимальное количество семестров, необходимых для прохождения всех курсов. Если нет способа пройти все курсы, верните -1.
Пример:
Input: n = 3, relations = [[1,3],[2,3]] Output: 2 Explanation: The figure above represents the given graph. In the first semester, you can take courses 1 and 2. In the second semester, you can take course 3.👨💻 Алгоритм: 1⃣Постройте направленный граф из зависимостей (relations). 2⃣Реализуйте функцию dfsCheckCycle для проверки наличия цикла в графе. 3⃣Реализуйте функцию dfsMaxPath для вычисления длины самого длинного пути в графе. Если цикл найден, верните -1. Иначе верните длину самого длинного пути. 😎 Решение:
class Solution {
func minimumSemesters(_ N: Int, _ relations: [[Int]]) -> Int {
var graph = [[Int]](repeating: [], count: N + 1)
for relation in relations {
graph[relation[0]].append(relation[1])
}
var visited = [Int](repeating: 0, count: N + 1)
for node in 1...N {
if dfsCheckCycle(node, graph, &visited) == -1 {
return -1
}
}
var visitedLength = [Int](repeating: 0, count: N + 1)
var maxLength = 1
for node in 1...N {
let length = dfsMaxPath(node, graph, &visitedLength)
maxLength = max(length, maxLength)
}
return maxLength
}
private func dfsCheckCycle(_ node: Int, _ graph: [[Int]], _ visited: inout [Int]) -> Int {
if visited[node] != 0 {
return visited[node]
} else {
visited[node] = -1
}
for endNode in graph[node] {
if dfsCheckCycle(endNode, graph, &visited) == -1 {
return -1
}
}
visited[node] = 1
return 1
}
private func dfsMaxPath(_ node: Int, _ graph: [[Int]], _ visitedLength: inout [Int]) -> Int {
if visitedLength[node] != 0 {
return visitedLength[node]
}
var maxLength = 1
for endNode in graph[node] {
let length = dfsMaxPath(endNode, graph, &visitedLength)
maxLength = max(length + 1, maxLength)
}
visitedLength[node] = maxLength
return maxLength
}
}1 348
Задача: 1268. Search Suggestions System
Сложность: medium
Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord.
Пример:
Input: products = ["havana"], searchWord = "havana" Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]👨💻 Алгоритм: 1⃣Отсортируйте массив продуктов. 2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу. 3⃣Сохраняйте не более трех лексикографически минимальных продуктов для каждого префикса. 😎 Решение:
class Solution {
func suggestedProducts(_ products: [String], _ searchWord: String) -> [[String]] {
let sortedProducts = products.sorted()
var result = [[String]]()
var prefix = ""
for char in searchWord {
prefix.append(char)
var suggestions = [String]()
for product in sortedProducts {
if product.hasPrefix(prefix) {
suggestions.append(product)
if suggestions.count == 3 { break }
}
}
result.append(suggestions)
}
return result
}
}1 348
Задача: 664. Strange Printer
Сложность: hard
Существует странный принтер с двумя особыми свойствами:
Принтер может печатать последовательность одного и того же символа за раз.
На каждом шагу принтер может печатать новые символы, начиная и заканчивая в любом месте, при этом покрывая уже существующие символы.
Дана строка s. Верните минимальное количество ходов, необходимых для её печати.
Пример:
Input: s = "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb".👨💻 Алгоритм: 1⃣Инициализация и подсчет: Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1]. 2⃣Динамическое программирование: Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим. В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов. 3⃣Возврат результата: Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки. 😎 Решение:
class Solution {
func strangePrinter(_ s: String) -> Int {
let n = s.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
let chars = Array(s)
for length in 1...n {
for i in 0...(n - length) {
let j = i + length - 1
dp[i][j] = (i == j) ? 1 : dp[i][j - 1] + 1
for k in i..<j {
if chars[k] == chars[j] {
dp[i][j] = min(dp[i][j], dp[i][k] + (dp[k + 1][j - 1] if k + 1 <= j - 1 else 0))
}
}
}
}
return dp[0][n - 1]
}
}1 348
Задача: 1036. Escape a Large Maze
Сложность: hard
Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false👨💻 Алгоритм: 1⃣Обработка входных данных: Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked. 2⃣Проверка простого случая: Если список blocked пуст, верните true, так как путь не будет заблокирован. Проверка начальной или целевой клетки: Если исходная или целевая клетка заблокированы, верните false. 3⃣Поиск пути с использованием BFS или DFS: Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток. Если обнаружен путь, верните true, в противном случае верните false. 😎 Решение:
class Solution {
func isEscapePossible(_ blocked: [[Int]], _ source: [Int], _ target: [Int]) -> Bool {
let blockedSet = Set(blocked.map { ($0[0], $0[1]) })
let source = (source[0], source[1])
let target = (target[0], target[1])
if blockedSet.contains(source) || blockedSet.contains(target) {
return false
}
func bfs(_ start: (Int, Int), _ end: (Int, Int)) -> Bool {
var queue = [(start.0, start.1)]
var visited = Set([(start.0, start.1)])
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
let maxArea = blocked.count * (blocked.count - 1) / 2
while !queue.isEmpty {
if visited.count > maxArea {
return true
}
let (x, y) = queue.removeFirst()
for (dx, dy) in directions {
let nx = x + dx, ny = y + dy
if nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.contains((nx, ny)) && !blockedSet.contains((nx, ny)) {
if (nx, ny) == end {
return true
}
queue.append((nx, ny))
visited.insert((nx, ny))
}
}
}
return false
}
return bfs(source, target) && bfs(target, source)
}
}1 348
Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy
Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.
Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.
Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.
Пример:
Input: candies = [2,3,5,1,3], extraCandies = 3 Output: [true,true,true,false,true] Explanation: If you give all extraCandies to: - Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids. - Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids. - Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids. - Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids. - Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.👨💻 Алгоритм: 1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies. 2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false. 3⃣Верните список answer. 😎 Решение:
class Solution {
func kidsWithCandies(_ candies: [Int], _ extraCandies: Int) -> [Bool] {
var maxCandies = 0
for candy in candies {
maxCandies = max(candy, maxCandies)
}
var result = [Bool]()
for candy in candies {
result.append(candy + extraCandies >= maxCandies)
}
return result
}
}1 348
Задача: 346. Moving Average from Data Stream
Сложность: easy
Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне.
Реализуйте класс MovingAverage:
MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.
Пример:
Input ["MovingAverage", "next", "next", "next", "next"] [[3], [1], [10], [3], [5]] Output [null, 1.0, 5.5, 4.66667, 6.0]👨💻 Алгоритм: 1⃣Инициализация: Инициализируйте объект с фиксированным размером окна size. Используйте очередь или список для хранения значений в текущем окне. Храните текущую сумму значений в окне. 2⃣Добавление нового значения: Добавьте новое значение в очередь. Обновите текущую сумму, добавив новое значение. Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение. 3⃣Вычисление скользящего среднего: Возвращайте текущее скользящее среднее как сумму значений в окне, деленную на количество значений в окне. 😎 Решение:
class MovingAverage {
private var size: Int
private var queue: [Int]
private var sum: Int
init(_ size: Int) {
self.size = size
self.queue = []
self.sum = 0
}
func next(_ val: Int) -> Double {
queue.append(val)
sum += val
if queue.count > size {
sum -= queue.removeFirst()
}
return Double(sum) / Double(queue.count)
}
}1 348
Задача: 246. Strobogrammatic Number
Сложность: easy
Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).
Пример:
Input: num = "69" Output: true👨💻 Алгоритм: 1⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false. 2⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку. 3⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false. 😎 Решение:
class Solution {
func isStrobogrammatic(_ num: String) -> Bool {
var rotatedString = ""
for c in num.reversed() {
if c == "0" || c == "1" || c == "8" {
rotatedString.append(c)
} else if c == "6" {
rotatedString.append("9")
} else if c == "9" {
rotatedString.append("6")
} else {
return false
}
}
return num == rotatedString
}
}1 348
Задача: 387. First Unique Character in a String
Сложность: easy
Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1.
Пример:
Input: s = "leetcode" Output: 0👨💻 Алгоритм: 1⃣Постройте хеш-таблицу, где ключами являются символы строки, а значениями — количество их появлений. Для этого пройдите по строке и для каждого символа увеличивайте его счетчик в хеш-таблице. 2⃣Пройдите по строке снова и проверьте для каждого символа, является ли его количество появлений в хеш-таблице равным 1. 3⃣Если найдется символ с количеством появлений, равным 1, верните его индекс. Если такой символ не найден, верните -1. 😎 Решение:
class Solution {
private var original: [Int]
private var array: [Int]
init(_ nums: [Int]) {
self.original = nums
self.array = nums
}
func reset() -> [Int] {
self.array = self.original
return self.original
}
func shuffle() -> [Int] {
let n = array.count
for i in 0..<n {
let randIndex = Int.random(in: i..<n)
array.swapAt(i, randIndex)
}
return array
}
}1 348
Задача: 459. Repeated Substring Pattern
Сложность: easy
Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом.
Пример:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.👨💻 Алгоритм: 1⃣Создайте целочисленную переменную n, равную длине строки s. 2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2: Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s. Если pattern равен s, вернуть true. 3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false. 😎 Решение:
class Solution {
func repeatedSubstringPattern(_ s: String) -> Bool {
let n = s.count
for i in 1...n / 2 {
if n % i == 0 {
var pattern = ""
let substr = String(s.prefix(i))
for _ in 0..<n / i {
pattern += substr
}
if s == pattern {
return true
}
}
}
return false
}
}1 348
Задача: 996. Number of Squareful Arrays
Сложность: hard
Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].
Пример:
Input: nums = [1,17,8] Output: 2👨💻 Алгоритм: 1⃣Генерация перестановок: Сгенерируйте все возможные перестановки массива nums. Для каждой перестановки проверьте, является ли она квадратной. 2⃣Проверка квадратности: Для каждой перестановки проверьте, является ли сумма каждой пары соседних элементов совершенным квадратом. Для этого используйте функцию для проверки, является ли число совершенным квадратом. 3⃣Подсчет квадратных перестановок: Подсчитайте количество перестановок, которые являются квадратными, и верните это значение. 😎 Решение:
class Solution {
func numSquarefulPerms(_ nums: [Int]) -> Int {
var nums = nums.sorted()
var used = Array(repeating: false, count: nums.count)
var result = Set<[Int]>()
var path = [Int]()
backtrack(nums, &used, &path, &result)
return result.count
}
private func backtrack(_ nums: [Int], _ used: inout [Bool], _ path: inout [Int], _ result: inout Set<[Int]>) {
if path.count == nums.count {
if isSquareful(path) {
result.insert(path)
}
return
}
for i in 0..<nums.count {
if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue }
path.append(nums[i])
used[i] = true
backtrack(nums, &used, &path, &result)
path.removeLast()
used[i] = false
}
}
private func isSquareful(_ perm: [Int]) -> Bool {
for i in 0..<perm.count - 1 {
let sum = perm[i] + perm[i + 1]
let root = Int(sqrt(Double(sum)))
if root * root != sum { return false }
}
return true
}
}1 348
Задача: 954. Array of Doubled Pairs
Сложность: medium
Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.
Пример:
Input: arr = [3,1,3,6] Output: false👨💻 Алгоритм: 1⃣Подсчитать частоту каждого элемента в массиве. Отсортировать массив по абсолютным значениям элементов. 2⃣Для каждого элемента в отсортированном массиве: Проверить, можно ли сопоставить его с элементом, равным его удвоенному значению. Уменьшить счетчик обоих элементов в словаре частот. 3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false. 😎 Решение:
class Solution {
func canReorderDoubled(_ arr: [Int]) -> Bool {
var count = [Int: Int]()
for num in arr {
count[num, default: 0] += 1
}
for num in arr.sorted(by: { abs($0) < abs($1) }) {
if count[num]! == 0 {
continue
}
if count[2 * num, default: 0] == 0 {
return false
}
count[num]! -= 1
count[2 * num]! -= 1
}
return true
}
}1 348
Задача: 656. Coin Path
Сложность: hard
Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.
Пример:
Input: coins = [1,2,4,-1,2], maxJump = 2 Output: [1,3,5]👨💻 Алгоритм: 1⃣Используйте динамическое программирование для нахождения минимальной стоимости до каждого индекса, начиная с первого. 2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути. 3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса. 😎 Решение:
import Foundation
func minCostPath(_ coins: [Int], _ maxJump: Int) -> [Int] {
let n = coins.count
if coins[0] == -1 { return [] }
var dp = [Int](repeating: Int.max, count: n)
dp[0] = coins[0]
var path = Array(repeating: [Int](), count: n)
path[0] = [1]
var heap = [(cost: Int, index: Int)]()
heap.append((coins[0], 0))
while !heap.isEmpty {
heap.sort(by: { $0.cost < $1.cost })
let (current_cost, i) = heap.removeFirst()
if current_cost > dp[i] { continue }
for k in 1...maxJump {
if i + k < n && coins[i + k] != -1 {
let new_cost = current_cost + coins[i + k]
if new_cost < dp[i + k] || (new_cost == dp[i + k] && path[i] + [i + k + 1] < path[i + k]) {
dp[i + k] = new_cost
path[i + k] = path[i] + [i + k + 1]
heap.append((new_cost, i + k))
}
}
}
}
return dp[n - 1] == Int.max ? [] : path[n - 1]
}1 348
Задача: 757. Set Intersection Size At Least Two
Сложность: hard
Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.
Пример:
Input: intervals = [[1,3],[3,7],[8,9]] Output: 5👨💻 Алгоритм: 1⃣Отсортируйте интервалы по их конечным точкам. 2⃣Инициализируйте пустое множество для хранения чисел. 3⃣Пройдите по каждому интервалу, добавляя необходимые числа в множество так, чтобы каждый интервал содержал не менее двух чисел из этого множества. 😎 Решение:
func minSetSize(_ intervals: [[Int]]) -> Int {
let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
var nums = [Int]()
for interval in sortedIntervals {
let start = interval[0]
let end = interval[1]
if nums.isEmpty || nums.last! < start {
nums.append(end - 1)
nums.append(end)
} else if nums.last! == end - 1 {
nums.append(end)
}
}
return nums.count
}1 348
Задача: 985. Sum of Even Numbers After Queries
Сложность: medium
Дан целочисленный массив nums и массив queries, где queries[i] = [vali, indexi].
Для каждого запроса i, сначала примените nums[indexi] = nums[indexi] + vali, затем выведите сумму четных значений nums.
Верните целочисленный массив answer, где answer[i] - это ответ на i-й запрос.
Пример:
Input: nums = [1], queries = [[4,0]] Output: [0]👨💻 Алгоритм: 1⃣Инициализация переменных: Завести переменную evenSum для хранения суммы всех четных чисел в массиве nums. Пройти по массиву nums и вычислить начальное значение evenSum, сложив все четные числа в nums. 2⃣Обработка запросов: Создать пустой массив result для хранения ответов на каждый запрос. Для каждого запроса [val, index] из массива queries выполнить следующие действия: Если значение nums[index] четное, вычесть его из evenSum. Обновить nums[index] добавлением val. Если новое значение nums[index] четное, добавить его к evenSum. Добавить текущее значение evenSum в массив result. 3⃣Возврат результата: Вернуть массив result, содержащий ответы на все запросы. 😎 Решение:
func sumEvenAfterQueries(_ nums: [Int], _ queries: [[Int]]) -> [Int] {
var nums = nums
var evenSum = nums.filter { $0 % 2 == 0 }.reduce(0, +)
var result = [Int]()
for query in queries {
let val = query[0], index = query[1]
if nums[index] % 2 == 0 {
evenSum -= nums[index]
}
nums[index] += val
if nums[index] % 2 == 0 {
evenSum += nums[index]
}
result.append(evenSum)
}
return result
}1 348
Задача: 643. Maximum Average Subarray I
Сложность: easy
Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.
Пример:
Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000👨💻 Алгоритм: 1⃣Инициализация скользящего окна: Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы. 2⃣Перемещение окна: Перемещайте окно длиной k по массиву, добавляя следующий элемент и убирая предыдущий, чтобы поддерживать сумму текущего окна. 3⃣Обновление максимальной суммы: На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы. 😎 Решение:
class Solution {
func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
var currentSum = nums.prefix(k).reduce(0, +)
var maxSum = currentSum
for i in k..<nums.count {
currentSum += nums[i] - nums[i - k]
maxSum = max(maxSum, currentSum)
}
return Double(maxSum) / Double(k)
}
}1 348
📱 Стажировки и вакансии для SWIFT разработчиков.
- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram
👉 @jobs_swift
🤖 ML & DS 👩💻 DevOps
👨✈️ ИБ & OSINT 👣 Go
👩💻 Mobile 👩💻 C#
👩💻 Node.js 👩💻 Python
🔎 QA 👩💻 Java
👩💻 UX/UI 👩💻 Frontend
🖼️ PHP 📋 Analyst
💼 1C 🖥 SQL
👩💻 IT HR
Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.
1 348
Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard
Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.
Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию.
Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.
Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.
Пример:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000class Solution {
func minmaxGasDist(_ stations: [Int], _ K: Int) -> Double {
let N = stations.count
var deltas = [Double](repeating: 0, count: N-1)
for i in 0..<N-1 {
deltas[i] = Double(stations[i+1] - stations[i])
}
var dp = [[Double]](repeating: [Double](repeating: 0, count: K+1), count: N-1)
for i in 0...K {
dp[0][i] = deltas[0] / Double(i+1)
}
for p in 1..<N-1 {
for k in 0...K {
var bns = Double.greatestFiniteMagnitude
for x in 0...k {
bns = min(bns, max(deltas[p] / Double(x+1), dp[p-1][k-x]))
}
dp[p][k] = bns
}
}
return dp[N-2][K]
}
}1 348
Задача: 230. Kth Smallest Element in a BST
Сложность: medium
Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.
Пример:
Input: root = [3,1,4,null,2], k = 1 Output: 1👨💻 Алгоритм: 1⃣Инициализация стека и обход в глубину: Инициализируйте стек для хранения узлов дерева. Начните обход дерева в глубину, начиная с корня, и перемещайтесь влево, добавляя каждый узел в стек, пока не достигнете самого левого узла. 2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение. 3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение. 😎 Решение:
class Solution {
func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
var stack = [TreeNode]()
var root = root
var k = k
while true {
while root != nil {
stack.append(root!)
root = root?.left
}
root = stack.removeLast()
k -= 1
if k == 0 {
return root!.val
}
root = root?.right
}
}
}1 348
Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium
Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.
Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.
Гарантируется, что каждый город может добраться до города 0 после перенаправления.
Пример:
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).class Solution {
var count = 0
func dfs(_ node: Int, _ parent: Int, _ adj: [Int: [[Int]]]) {
guard let neighbors = adj[node] else { return }
for neighbor in neighbors {
let (nei, sign) = (neighbor[0], neighbor[1])
if nei != parent {
count += sign
dfs(nei, node, adj)
}
}
}
func minReorder(_ n: Int, _ connections: [[Int]]) -> Int {
var adj = [Int: [[Int]]]()
for connection in connections {
adj[connection[0], default: []].append([connection[1], 1])
adj[connection[1], default: []].append([connection[0], 0])
}
dfs(0, -1, adj)
return count
}
}