Swift | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Показати більше
Сітка:1 339
Підписники
Немає даних24 години
-17 днів
-2630 день
Архів дописів
1 339
Задача: 661. Image Smoother
Сложность: easy
Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.
Пример:
Input: img = [[1,1,1],[1,0,1],[1,1,1]] Output: [[0,0,0],[0,0,0],[0,0,0]] Explanation: For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) = floor(0.88888889) = 0👨💻 Алгоритм: 1⃣Инициализация: Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания. 2⃣Обработка каждой ячейки: Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку). Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы. 3⃣Возврат результата: Верните результирующую матрицу после применения сглаживания ко всем ячейкам. 😎 Решение:
class Solution {
func imageSmoother(_ img: [[Int]]) -> [[Int]] {
let m = img.count
let n = img[0].count
var result = Array(repeating: Array(repeating: 0, count: n), count: m)
for i in 0..<m {
for j in 0..<n {
var count = 0
var total = 0
for ni in max(0, i - 1)...min(m - 1, i + 1) {
for nj in max(0, j - 1)...min(n - 1, j + 1) {
total += img[ni][nj]
count += 1
}
}
result[i][j] = total / count
}
}
return result
}
}1 339
Задача: 851. Loud and Rich
Сложность: medium
Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.
Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).
Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.
Пример:
Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation:
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.class Solution {
var graph: [[Int]] = []
var answer: [Int] = []
var quiet: [Int] = []
func loudAndRich(_ richer: [[Int]], _ quiet: [Int]) -> [Int] {
let N = quiet.count
graph = Array(repeating: [], count: N)
answer = Array(repeating: -1, count: N)
self.quiet = quiet
for edge in richer {
graph[edge[1]].append(edge[0])
}
for node in 0..<N {
_ = dfs(node)
}
return answer
}
func dfs(_ node: Int) -> Int {
if answer[node] == -1 {
answer[node] = node
for child in graph[node] {
let cand = dfs(child)
if quiet[cand] < quiet[answer[node]] {
answer[node] = cand
}
}
}
return answer[node]
}
}1 339
Задача: 254. Factor Combinations
Сложность: medium
Числа можно рассматривать как произведение их множителей.
Например, 8 = 2 x 2 x 2 = 2 x 4.
Дано целое число n, верните все возможные комбинации его множителей. Вы можете вернуть ответ в любом порядке.
Обратите внимание, что множители должны быть в диапазоне [2, n - 1].
Пример:
Input: n = 1 Output: []👨💻 Алгоритм: 1⃣Определите вспомогательную функцию backtracking, которая принимает два параметра: factors (список множителей) и ans (список списков для сохранения всех комбинаций множителей). Начните вызов backtracking с factors, содержащим только n, и пустым списком ans. 2⃣Основная логика функции backtracking: Если размер factors больше 1, добавьте его копию в ans, так как это одно из желаемых решений. Получите последний элемент factors (lastFactor) и удалите его из factors. Если factors пуст, итерируйте i от 2. В противном случае, итерируйте i от последнего значения в factors. Итерируйте, пока i <= lastFactor / i. Для каждого i, если lastFactor % i == 0, добавьте i и lastFactor / i в factors и вызовите backtracking(factors, ans). Восстановите список (откат) factors, удалив последние два элемента из factors. Восстановите список (откат) factors, добавив обратно lastFactor. 3⃣В конце выполнения, ans будет содержать все возможные комбинации множителей числа n. 😎 Решение:
class Solution {
private func backtracking(_ factors: inout [Int], _ ans: inout [[Int]]) {
if factors.count > 1 {
ans.append(factors)
}
let lastFactor = factors.removeLast()
for i in (factors.isEmpty ? 2 : factors.last!)...lastFactor {
if i * i > lastFactor { break }
if lastFactor % i == 0 {
factors.append(i)
factors.append(lastFactor / i)
backtracking(&factors, &ans)
factors.removeLast()
factors.removeLast()
}
}
factors.append(lastFactor)
}
func getFactors(_ n: Int) -> [[Int]] {
var ans: [[Int]] = []
var factors: [Int] = [n]
backtracking(&factors, &ans)
return ans
}
}1 339
Задача: 443. String Compression
Сложность: medium
Дан массив символов chars, сжать его, используя следующий алгоритм:
Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:
Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.
После того как вы закончите модификацию входного массива, верните новую длину массива.
Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.
Пример:
Input: chars = ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".👨💻 Алгоритм: 1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0. 2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе. 3⃣Верните res. 😎 Решение:
class Solution {
func compress(_ chars: inout [Character]) -> Int {
var i = 0
var res = 0
while i < chars.count {
var groupLength = 1
while i + groupLength < chars.count && chars[i + groupLength] == chars[i] {
groupLength += 1
}
chars[res] = chars[i]
res += 1
if groupLength > 1 {
let strRepr = String(groupLength)
for ch in strRepr {
chars[res] = ch
res += 1
}
}
i += groupLength
}
return res
}
}1 339
Задача: 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 339
Задача: 1004. Max Consecutive Ones III
Сложность: medium
Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.
Пример:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6👨💻 Алгоритм: 1⃣Инициализация оконного подхода: Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне. 2⃣Перемещение правого указателя и обновление окна: Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k). 3⃣Подсчет максимального количества последовательных единиц: На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом. 😎 Решение:
class Solution {
func longestOnes(_ nums: [Int], _ k: Int) -> Int {
var left = 0
var maxOnes = 0
var zeroCount = 0
for right in 0..<nums.count {
if nums[right] == 0 {
zeroCount += 1
}
while zeroCount > k {
if nums[left] == 0 {
zeroCount -= 1
}
left += 1
}
maxOnes = max(maxOnes, right - left + 1)
}
return maxOnes
}
}1 339
Задача: 172. Factorial Trailing Zeroes
Сложность: medium
Дано целое число n, верните количество конечных нулей в n!.
Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
Пример:
Input: n = 3 Output: 0 Explanation: 3! = 6, no trailing zero.👨💻 Алгоритм: 1⃣Вычислите факториал n: Инициализируйте переменную nFactorial значением 1. Для каждого i от 2 до n включительно умножайте nFactorial на i. 2⃣Подсчитайте количество конечных нулей в nFactorial: Инициализируйте переменную zeroCount значением 0. Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1. 3⃣Верните значение zeroCount как количество конечных нулей в n!. 😎 Решение:
func trailingZeroes(_ n: Int) -> Int {
var nFactorial = 1
for i in 2...n {
nFactorial *= i
}
var zeroCount = 0
var nFactorialBigInt = nFactorial
while nFactorialBigInt % 10 == 0 {
nFactorialBigInt /= 10
zeroCount += 1
}
return zeroCount
}1 339
Задача: 712. Minimum ASCII Delete Sum for Two Strings
Сложность: medium
Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.
Пример:
Input: s1 = "sea", s2 = "eat" Output: 231👨💻 Алгоритм: 1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2. 2⃣Заполните первую строку и первый столбец массива dp суммами ASCII значений символов, которые необходимо удалить для достижения пустой строки. 3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])). 😎 Решение:
func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
let s1Array = Array(s1)
let s2Array = Array(s2)
var dp = Array(repeating: Array(repeating: 0, count: s2Array.count + 1), count: s1Array.count + 1)
for i in 1...s1Array.count {
dp[i][0] = dp[i - 1][0] + Int(s1Array[i - 1].asciiValue!)
}
for j in 1...s2Array.count {
dp[0][j] = dp[0][j - 1] + Int(s2Array[j - 1].asciiValue!)
}
for i in 1...s1Array.count {
for j in 1...s2Array.count {
if s1Array[i - 1] == s2Array[j - 1] {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = min(dp[i - 1][j] + Int(s1Array[i - 1].asciiValue!), dp[i][j - 1] + Int(s2Array[j - 1].asciiValue!))
}
}
}
return dp[s1Array.count][s2Array.count]
}1 339
Задача: 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 339
Задача: 26. Remove Duplicates from Sorted Array
Сложность: easy
Учитывая целочисленный массив
nums, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов.
Пример:
Input: nums = [1,1,2,2,2,3,4,4,5] Output: 5👨💻Алгоритм: 1⃣Используем указатель
k для отслеживания позиции, куда вставлять уникальные элементы.
2⃣Проходим по массиву, начиная со второго элемента, и сравниваем его с предыдущим.
3⃣Если текущий элемент отличается от предыдущего, записываем его на позицию k и увеличиваем k.
😎Решение:
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
}1 339
Задача: 168. Excel Sheet Column Title
Сложность: easy
Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.
Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28
Пример:
Input: columnNumber = 1 Output: "A"👨💻 Алгоритм: 1⃣Инициализация пустой строки ans: Создайте пустую строку ans, которая будет хранить заголовок столбца. 2⃣Циклическое преобразование числа в буквы: Пока columnNumber больше 0, выполняйте следующие действия: Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию). Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans. Присвойте columnNumber значение от деления columnNumber на 26 3⃣Переворот и возврат результата: Так как символы добавляются в начало строки, то по завершению цикла строка ans содержит заголовок столбца в обратном порядке. Переверните строку ans, чтобы представить её в правильном порядке. Верните полученный заголовок столбца. 😎 Решение:
class Solution {
func convertToTitle(_ columnNumber: Int) -> String {
var columnNumber = columnNumber
var ans = ""
while columnNumber > 0 {
columnNumber -= 1
ans = "\(Character(UnicodeScalar(columnNumber % 26 + Int("A".unicodeScalars.first!.value))!))" + ans
columnNumber /= 26
}
return ans
}
}1 339
Задача: 1086. High Five
Сложность: easy
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]class Solution {
func highFive(_ items: [[Int]]) -> [[Int]] {
let K = 5
let sortedItems = items.sorted {
if $0[0] != $1[0] {
return $0[0] < $1[0]
}
return $0[1] > $1[1]
}
var solution = [[Int]]()
var i = 0
while i < sortedItems.count {
let id = sortedItems[i][0]
var sum = 0
for k in i..<i+K {
sum += sortedItems[k][1]
}
while i < sortedItems.count && sortedItems[i][0] == id {
i += 1
}
solution.append([id, sum / K])
}
return solution
}
}1 339
Задача: 979. Distribute Coins in Binary Tree
Сложность: medium
Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.
За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.
Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету.
Пример:
Input: root = [3,0,0] Output: 2 Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.👨💻 Алгоритм: 1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0. 2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves. 3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves. 😎 Решение:
class Solution {
var moves = 0
func distributeCoins(_ root: TreeNode?) -> Int {
dfs(root)
return moves
}
private func dfs(_ current: TreeNode?) -> Int {
guard let current = current else { return 0 }
let leftCoins = dfs(current.left)
let rightCoins = dfs(current.right)
moves += abs(leftCoins) + abs(rightCoins)
return current.val - 1 + leftCoins + rightCoins
}
}1 339
АЙТИШНИКИ, ХВАТИТ сливать время на прилизанные новости и бесполезные курсы
Проект «ИИнтеллигенция» стал главным каналом для тех, кто использует нейросети на уровне разработки, автоматизации и опенсорса, а не просто балуется в чатах. Здесь собирают только то, что реально экономит человеко-часы и работает в проде.
🎓 Готовые ИИ-сервисы, промпты и ИИ-агенты для автоматизации рутины
📚 Разборы полезных ИИ-инструментов, локальных LLM и опенсорс-репозиториев
🛠 Практические кейсы, гайды по деплою моделей и интеграции ИИ в пайплайны
⚡️ Технические ИТ-новости без маркетинговой воды и душных отчетов
Обучение и прокачка в реальном времени: работа с API (Claude, GPT), локалки (Ollama, vLLM), автоматизация кода, опенсорс-утилиты, AI-агенты и др.
Ценишь время и работаешь с ИИ, подпишись: @clucai
1 339
Задача: 834. Sum of Distances in Tree
Сложность: hard
Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.
Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.
Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.
Пример:
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] Output: [8,12,6,10,10,10] Explanation: The tree is shown above. We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) equals 1 + 1 + 2 + 2 + 2 = 8. Hence, answer[0] = 8, and so on.👨💻 Алгоритм: 1⃣Постройте дерево и выполните обход в глубину (DFS) для расчета количества узлов в поддереве и суммы расстояний до всех узлов поддерева. 2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева. 3⃣Выполните второй обход в глубину (DFS) для корректировки суммы расстояний для каждого узла на основе суммы расстояний его родительского узла. 😎 Решение:
class Solution {
var ans: [Int] = []
var count: [Int] = []
var graph: [[Int]] = []
var N: Int = 0
func sumOfDistancesInTree(_ N: Int, _ edges: [[Int]]) -> [Int] {
self.N = N
graph = Array(repeating: [], count: N)
ans = Array(repeating: 0, count: N)
count = Array(repeating: 1, count: N)
for edge in edges {
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
}
dfs(0, -1)
dfs2(0, -1)
return ans
}
func dfs(_ node: Int, _ parent: Int) {
for child in graph[node] {
if child != parent {
dfs(child, node)
count[node] += count[child]
ans[node] += ans[child] + count[child]
}
}
}
func dfs2(_ node: Int, _ parent: Int) {
for child in graph[node] {
if child != parent {
ans[child] = ans[node] - count[child] + N - count[child]
dfs2(child, node)
}
}
}
}1 339
Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium
Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.
Пример:
Input ["FindElements","find","find"] [[[-1,null,-1]],[1],[2]] Output [null,false,true]👨💻 Алгоритм: 1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2. 2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов. 3⃣Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений. 😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
class FindElements {
private var root: TreeNode?
private var values: Set<Int>
init(_ root: TreeNode?) {
self.root = root
self.values = Set<Int>()
if let root = root {
root.val = 0
values.insert(0)
recover(root)
}
}
private func recover(_ node: TreeNode) {
if let left = node.left {
left.val = 2 * node.val + 1
values.insert(left.val)
recover(left)
}
if let right = node.right {
right.val = 2 * node.val + 2
values.insert(right.val)
recover(right)
}
}
func find(_ target: Int) -> Bool {
return values.contains(target)
}
}1 339
Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium
Вам дан корень бинарного дерева.
Зигзагообразный путь для бинарного дерева определяется следующим образом:
Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).
Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.
Пример:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.👨💻 Алгоритм: 1⃣Рекурсивная функция DFS: Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо). 2⃣Обновление максимальной длины пути: При каждом вызове рекурсивной функции обновляйте максимальную длину зигзагообразного пути, если текущая длина больше текущего максимума. 3⃣Рекурсивный вызов для левого и правого дочерних узлов: Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления. 😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}
class Solution {
var maxLength = 0
func longestZigZag(_ root: TreeNode?) -> Int {
dfs(root, true, 0)
dfs(root, false, 0)
return maxLength
}
func dfs(_ node: TreeNode?, _ isLeft: Bool, _ length: Int) {
guard let node = node else { return }
maxLength = max(maxLength, length)
if isLeft {
dfs(node.left, false, length + 1)
dfs(node.right, true, 1)
} else {
dfs(node.right, true, length + 1)
dfs(node.left, false, 1)
}
}
}1 339
Задача: 287. Find the Duplicate Number
Сложность: medium
Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.
Пример:
Input: nums = [1,3,4,2,2] Output: 2👨💻 Алгоритм: 1⃣Определение дубликата: Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс. Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла. Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу. 2⃣Восстановление массива: Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива. 3⃣Возврат результата: Верните найденный дубликат. 😎 Решение:
class Solution {
func findDuplicate(_ nums: [Int]) -> Int {
var nums = nums
var duplicate = -1
for i in 0..<nums.count {
let cur = abs(nums[i])
if nums[cur] < 0 {
duplicate = cur
break
}
nums[cur] *= -1
}
for i in 0..<nums.count {
nums[i] = abs(nums[i])
}
return duplicate
}
}1 339
Задача: 245. Shortest Word Distance II
Сложность: medium
Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.
Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.
Пример:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1👨💻 Алгоритм: 1⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX. 2⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают. 3⃣Верните значение переменной shortestDistance. 😎 Решение:
class Solution {
func shortestWordDistance(_ wordsDict: [String], _ word1: String, _ word2: String) -> Int {
var indices1 = [Int]()
var indices2 = [Int]()
for (i, word) in wordsDict.enumerated() {
if word == word1 {
indices1.append(i)
}
if word == word2 {
indices2.append(i)
}
}
var shortestDistance = Int.max
for index in indices1 {
let x = indices2.partitioningIndex(where: { $0 > index })
if x < indices2.count {
shortestDistance = min(shortestDistance, indices2[x] - index)
}
if x > 0 && indices2[x - 1] != index {
shortestDistance = min(shortestDistance, index - indices2[x - 1])
}
}
return shortestDistance
}
}1 339
Задача: 117. Populating Next Right Pointers in Each Node II
Сложность: medium
Вам дано бинарное дерево:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.
Изначально все указатели next установлены в NULL.
Пример:
Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.👨💻 Алгоритм: 1⃣Инициализируйте очередь Q, которая будет использоваться во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда дело доходит до определения уровня конкретного узла. Можно добавить в очередь пару (узел, уровень), и каждый раз, когда мы добавляем детей узла, мы добавляем (node.left, parent_level+1) и (node.right, parent_level+1). Этот подход может оказаться неэффективным для нашего алгоритма, так как нам нужны все узлы на одном уровне, и потребуется дополнительная структура данных. 2⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня - использовать разграничение между уровнями. Обычно мы вставляем в очередь элемент NULL, который обозначает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого объема памяти, пропорционального количеству уровней в дереве. 3⃣Подход, который мы будем использовать, предполагает структуру вложенных циклов, чтобы обойти необходимость NULL указателя. По сути, на каждом шаге мы фиксируем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и больше ничего. К тому времени, как мы закончим обработку заданного количества элементов, в очереди окажутся все узлы следующего уровня. Вот псевдокод для этого:
while (!Q.empty())
{
size = Q.size()
for i in range 0..size
{
node = Q.pop()
Q.push(node.left)
Q.push(node.right)
}
}
Мы начинаем с добавления корня дерева в очередь. Так как на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.
😎 Решение:
import Foundation
class Node {
var value: Int
var left: Node?
var right: Node?
var next: Node?
init(_ value: Int) {
self.value = value
}
}
class Solution {
func connect(_ root: Node?) -> Node? {
guard let root = root else { return nil }
var queue: [Node] = [root]
while !queue.isEmpty {
let size = queue.count
for i in 0..<size {
let node = queue.removeFirst()
if i < size - 1 {
node.next = queue.first
}
if let leftChild = node.left {
queue.append(leftChild)
}
if let rightChild = node.right {
queue.append(rightChild)
}
}
}
return root
}
}