Вже доступно! Дослідження Telegram за 2025 — головні інсайти року 
Swift | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Показати більше
Сітка:1 340
Підписники
-124 години
-107 днів
-2330 день
Архів дописів
1 340
👩💻 Программирование теперь в Telegram!
Вот 10 обучающих каналов по самым востребованным направлениям в IT.
Выбирай своё направление:
👩💻 Python: @python_ready
👩💻 Java: @java_ready
📖 Общее IT: @roadmap_ready
👩💻 Frontend: @code_ready
👩💻 Backend: @backend_ready
🖥 Базы Данных & SQL: @sql_ready
👩💻 C#: @csharp_ready
👩💻 C/C++: @cpp_ready
📋 IT Архив: @archive_ready
🖥 Design: @time_design
📌 Ресурсы, гайды, шпаргалки, книги и задачи для каждого языка программирования.
1 340
#medium
Задача: 221. Maximal Square
Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.
Пример:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4👨💻 Алгоритм: 1️⃣ Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения. 2️⃣ Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением. 3️⃣ По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата. 😎 Решение:
class Solution {
func maximalSquare(_ matrix: [[Character]]) -> Int {
let rows = matrix.count
let cols = rows > 0 ? matrix[0].count : 0
var dp = [Int](repeating: 0, count: cols + 1)
var maxsqlen = 0
var prev = 0
for i in 1...rows {
for j in 1...cols {
let temp = dp[j]
if matrix[i - 1][j - 1] == "1" {
dp[j] = min(dp[j - 1], min(prev, dp[j])) + 1
maxsqlen = max(maxsqlen, dp[j])
} else {
dp[j] = 0
}
prev = temp
}
}
return maxsqlen * maxsqlen
}
}1 340
#hard
Задача: 220. Contains Duplicate III
Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.
Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.
Верните true, если такая пара существует, или false в противном случае.
Пример:
Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0 Output: true Explanation: We can choose (i, j) = (0, 3). We satisfy the three conditions: i != j --> 0 != 3 abs(i - j) <= indexDiff --> abs(0 - 3) <= 3 abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0👨💻 Алгоритм: 1️⃣ Инициализация и вычисление корзин: Рассчитать ширину корзины w = t + 1. Инициализировать пустой хэш-таблицей buckets. Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w. 2️⃣ Итерация и проверка корзин: Перебрать все элементы массива nums. Для каждого элемента nums[i]: Определить его корзину с помощью getID. Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true. Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true. Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину. Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна. 3️⃣ Завершение: Если ни одна пара "почти дубликатов" не найдена, вернуть false. 😎 Решение:
class Solution {
func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
if t < 0 { return false }
var buckets = [Int: Int]()
let w = t + 1
for i in 0..<nums.count {
let bucket = nums[i] < 0 ? (nums[i] + 1) / w - 1 : nums[i] / w
if buckets[bucket] != nil { return true }
if let val = buckets[bucket - 1], abs(nums[i] - val) < w { return true }
if let val = buckets[bucket + 1], abs(nums[i] - val) < w { return true }
buckets[bucket] = nums[i]
if i >= k {
buckets.removeValue(forKey: nums[i - k] < 0 ? (nums[i - k] + 1) / w - 1 : nums[i - k] / w)
}
}
return false
}
}1 340
#hard
Задача: 315. Count of Smaller Numbers After Self
Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].
Пример:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.👨💻 Алгоритм: 1️⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2️⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3️⃣Верните результат. 😎 Решение:
class Solution {
func countSmaller(_ nums: [Int]) -> [Int] {
let offset = 10000
let size = 2 * 10000 + 1
var tree = [Int](repeating: 0, count: size * 2)
var result = [Int]()
for num in nums.reversed() {
let smallerCount = query(0, num + offset, tree, size)
result.append(smallerCount)
update(num + offset, 1, tree, size)
}
return result.reversed()
}
private func update(_ index: Int, _ value: Int, _ tree: inout [Int], _ size: Int) {
var idx = index + size
tree[idx] += value
while idx > 1 {
idx /= 2
tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]
}
}
private func query(_ left: Int, _ right: Int, _ tree: [Int], _ size: Int) -> Int {
var result = 0
var l = left + size
var r = right + size
while l < r {
if l % 2 == 1 {
result += tree[l]
l += 1
}
l /= 2
if r % 2 == 1 {
r -= 1
result += tree[r]
}
r /= 2
}
return result
}
}1 340
#medium
Задача: 314. Binary Tree Vertical Order Traversal
Дан корень бинарного дерева, верните вертикальный порядок обхода значений его узлов (т.е. сверху вниз, столбец за столбцом).
Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.
Пример:
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]]👨💻 Алгоритм: 1️⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов. 2️⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь. 3️⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам. 😎 Решение:
class Solution {
func verticalOrder(_ root: TreeNode?) -> [[Int]] {
var output = [[Int]]()
guard let root = root else {
return output
}
var columnTable = [Int: [Int]]()
var queue: [(TreeNode, Int)] = [(root, 0)]
while !queue.isEmpty {
let (node, column) = queue.removeFirst()
if columnTable[column] == nil {
columnTable[column] = [Int]()
}
columnTable[column]?.append(node.val)
if let left = node.left {
queue.append((left, column - 1))
}
if let right = node.right {
queue.append((right, column + 1))
}
}
let sortedKeys = columnTable.keys.sorted()
for key in sortedKeys {
if let values = columnTable[key] {
output.append(values)
}
}
return output
}
}1 340
#easy
Задача: 219. Contains Duplicate II
Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k.
Пример:
Input: nums = [1,2,3,1,2,3], k = 2 Output: false👨💻 Алгоритм: 1️⃣ Создайте пустое множество set. 2️⃣ Пройдитесь по массиву nums: Если текущий элемент уже есть в множестве, верните true. Добавьте текущий элемент в множество. Если размер множества больше k, удалите элемент, который был добавлен k шагов назад. 3️⃣ Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false. 😎 Решение:
class Solution {
func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
var set = Set<Int>()
for i in 0..<nums.count {
if set.contains(nums[i]) {
return true
}
set.insert(nums[i])
if set.count > k {
set.remove(nums[i - k])
}
}
return false
}
}1 340
#hard
Задача: 218. The Skyline Problem
Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности.
Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:
lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.
Пример:
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] Explanation: Figure A shows the buildings of the input. Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.👨💻 Алгоритм: 1️⃣ Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights. 2️⃣ Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex). 3️⃣ Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат. 😎 Решение:
class Solution {
func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
var edgeSet = Set<Int>()
for building in buildings {
edgeSet.insert(building[0])
edgeSet.insert(building[1])
}
let edges = Array(edgeSet).sorted()
var edgeIndexMap = [Int: Int]()
for i in 0..<edges.count {
edgeIndexMap[edges[i]] = i
}
var heights = [Int](repeating: 0, count: edges.count)
for building in buildings {
let left = building[0], right = building[1], height = building[2]
let leftIndex = edgeIndexMap[left]!, rightIndex = edgeIndexMap[right]!
for idx in leftIndex..<rightIndex {
heights[idx] = max(heights[idx], height)
}
}
var answer = [[Int]]()
for i in 0..<heights.count {
let currHeight = heights[i], currPos = edges[i]
if answer.isEmpty || answer.last![1] != currHeight {
answer.append([currPos, currHeight])
}
}
return answer
}
}1 340
#medium
Задача: 276. Paint Fence
Вы красите забор из n столбцов, используя k различных цветов. Вы должны красить столбы, следуя этим правилам:
Каждый столб должен быть окрашен в один цвет.
Не может быть трех или более подряд идущих столбцов одного цвета.
Учитывая два целых числа n и k, верните количество способов покрасить забор.
Пример:
Input: n = 3, k = 2 Output: 6 Explanation: All the possibilities are shown. Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.👨💻 Алгоритм: 1️⃣Инициализация и определение вспомогательной функции: Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов. Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов. 2️⃣Реализация базы и проверка кэша: В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2. Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i]. 3️⃣Расчет с использованием рекуррентного соотношения: В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его. Вызвать и вернуть totalWays(n). 😎 Решение:
class Solution {
func numWays(_ n: Int, _ k: Int) -> Int {
if n == 1 {
return k
}
var twoPostsBack = k
var onePostBack = k * k
for _ in 3...n {
let curr = (k - 1) * (onePostBack + twoPostsBack)
twoPostsBack = onePostBack
onePostBack = curr
}
return onePostBack
}
}1 340
#easy
Задача: 217. Contains Duplicate
Дан массив целых чисел nums. Верните true, если любое значение появляется в массиве хотя бы дважды, и верните false, если каждый элемент уникален.
Пример:
Input: nums = [1,2,3,4] Output: false👨💻 Алгоритм: 1️⃣ Отсортируйте массив nums по возрастанию. 2️⃣ Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим. 3️⃣ Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false. 😎 Решение:
func containsDuplicate(_ nums: [Int]) -> Bool {
let sortedNums = nums.sorted()
for i in 0..<sortedNums.count - 1 {
if sortedNums[i] == sortedNums[i + 1] {
return true
}
}
return false
}1 340
#medium
Задача: 275. H-Index II
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.
Пример:
Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Найти середину массива: Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n]. 2️⃣Сравнить количество статей с цитированиями больше или равными citations[mid]: Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть. Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n]. Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1]. 3️⃣Возвращение результата: Продолжать процесс, пока не будет найден h-индекс. Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid]. 😎 Решение:
class Solution {
func hIndex(_ citations: [Int]) -> Int {
let n = citations.count
var left = 0
var right = n - 1
while left <= right {
let mid = left + (right - left) / 2
if citations[mid] == n - mid {
return n - mid
} else if citations[mid] < n - mid {
left = mid + 1
} else {
right = mid - 1
}
}
return n - left
}
}1 340
#medium
Задача: 274. H-Index
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Пример:
Input: citations = [3,0,6,1,5] Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Отсортировать массив цитирований по убыванию: Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива. 2️⃣Найти наибольшее значение i, для которого citations[i] > i: Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i. Это значение будет индексом, при котором количество цитирований статьи больше индекса. 3️⃣Рассчитать h-индекс: h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге. 😎 Решение:
class Solution {
func hIndex(_ citations: [Int]) -> Int {
let n = citations.count
var papers = [Int](repeating: 0, count: n + 1)
for c in citations {
papers[min(n, c)] += 1
}
var k = n
var s = papers[n]
while k > s {
k -= 1
s += papers[k]
}
return k
}
}1 340
#medium
Задача: 216. Combination Sum III
Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:
Используются только числа от 1 до 9.
Каждое число используется не более одного раза.
Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке.
Пример:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.👨💻 Алгоритм: 1️⃣ Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2️⃣ Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3️⃣ Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:
class Solution {
func backtrack(_ remain: Int, _ k: Int, _ comb: inout [Int], _ nextStart: Int, _ results: inout [[Int]]) {
if remain == 0 && comb.count == k {
results.append(comb)
return
} else if remain < 0 || comb.count == k {
return
}
for i in nextStart..<9 {
comb.append(i + 1)
backtrack(remain - i - 1, k, &comb, i + 1, &results)
comb.removeLast()
}
}
func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
var results = [[Int]]()
var comb = [Int]()
backtrack(n, k, &comb, 0, &results)
return results
}
}1 340
#medium
Задача: 215. Kth Largest Element in an Array
Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.
Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.
Пример:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4👨💻 Алгоритм: 1️⃣ Отсортируйте массив в порядке убывания: Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее. 2️⃣ Найдите k-й по величине элемент: После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0). 3️⃣ Верните результат: Возвратите найденное значение как результат. 😎 Решение:
class Solution {
func shortestPalindrome(_ s: String) -> String {
let n = s.count
let rev = String(s.reversed())
for i in 0..<n {
let endIdx = s.index(s.startIndex, offsetBy: n - i)
let startIdx = rev.index(rev.startIndex, offsetBy: i)
if s[s.startIndex..<endIdx] == rev[startIdx...] {
return String(rev[rev.startIndex..<startIdx]) + s
}
}
return ""
}
}1 340
#hard
Задача: 273. Integer to English Words
Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.
Пример:
Input: num = 123 Output: "One Hundred Twenty Three"👨💻 Алгоритм: 1️⃣Обработка чисел до 20 и кратных 10 до 90: Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90. Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление. 2️⃣Обработка сотен, тысяч, миллионов и миллиардов: Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды). Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999. 3️⃣Формирование окончательного результата: Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды). Соединить все части в одну строку, удалив лишние пробелы. 😎 Решение:
class Solution {
private let belowTwenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
private let tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
private let thousands = ["", "Thousand", "Million", "Billion"]
func numberToWords(_ num: Int) -> String {
if num == 0 { return "Zero" }
var num = num
var result = ""
var i = 0
while num > 0 {
if num % 1000 != 0 {
result = helper(num % 1000) + thousands[i] + " " + result
}
num /= 1000
i += 1
}
return result.trimmingCharacters(in: .whitespaces)
}
private func helper(_ num: Int) -> String {
if num == 0 { return "" }
else if num < 20 { return belowTwenty[num] + " " }
else if num < 100 { return tens[num / 10] + " " + helper(num % 10) }
else { return belowTwenty[num / 100] + " Hundred " + helper(num % 100) }
}
}1 340
#hard
Задача: 214. Shortest Palindrome
Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.
Верните самый короткий палиндром, который можно получить, выполняя это преобразование.
Пример:
Input: s = "aacecaaa" Output: "aaacecaaa"👨💻 Алгоритм: 1️⃣ Создание обратной строки: Создаем обратную строку rev от исходной строки s. 2️⃣ Итерация для поиска наибольшего палиндрома: Перемещаемся по индексу i от 0 до n - 1. Проверяем, является ли подстрока s от 0 до n - i равной подстроке rev от i до конца строки. Если находим такое совпадение, возвращаем обратную подстроку от начала rev до i + исходная строка s. 3️⃣ Возврат результата: Возвращаем наименьший палиндром, полученный путем добавления символов в начало строки s. 😎 Решение:
class Solution {
func shortestPalindrome(_ s: String) -> String {
let n = s.count
let rev = String(s.reversed())
for i in 0..<n {
let startIndex = s.index(s.startIndex, offsetBy: 0)
let endIndex = s.index(s.startIndex, offsetBy: n - i)
let revStartIndex = rev.index(rev.startIndex, offsetBy: i)
let revEndIndex = rev.endIndex
if s[startIndex..<endIndex] == rev[revStartIndex..<revEndIndex] {
let prefix = rev[rev.startIndex..<revStartIndex]
return prefix + s
}
}
return ""
}
}
1 340
#hard
Задача: 272. Closest Binary Search Tree Value II
Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке.
Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]👨💻 Алгоритм: 1️⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив: Пройти по дереву в глубину, добавляя каждое значение узла в массив. 2️⃣Отсортировать массив по расстоянию от целевого значения: Использовать пользовательский компаратор, чтобы отсортировать массив по абсолютному значению разности между элементом массива и целевым значением. 3️⃣Вернуть первые k значений из отсортированного массива: Извлечь первые k элементов из отсортированного массива и вернуть их. 😎 Решение:
class Solution {
func closestKValues(_ root: TreeNode?, _ target: Double, _ k: Int) -> [Int] {
var arr = [Int]()
dfs(root, &arr)
arr.sort { abs(Double($0) - target) < abs(Double($1) - target) }
return Array(arr.prefix(k))
}
private func dfs(_ node: TreeNode?, _ arr: inout [Int]) {
guard let node = node else { return }
arr.append(node.val)
dfs(node.left, &arr)
dfs(node.right, &arr)
}
}1 340
#easy
Задача: 270. Closest Binary Search Tree Value
Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286 Output: 4👨💻 Алгоритм: 1️⃣Построить массив с помощью inorder обхода: Выполнить inorder обход дерева и собрать элементы в отсортированный массив. 2️⃣Найти ближайший элемент: Пройти по массиву и определить элемент, наиболее близкий к целевому значению. 3️⃣Выбрать наименьший из ближайших элементов: Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них. 😎 Решение:
class Solution {
func closestValue(_ root: TreeNode?, _ target: Double) -> Int {
var closest = root!.val
var node = root
while node != nil {
if abs(Double(node!.val) - target) < abs(Double(closest) - target) {
closest = node!.val
} else if abs(Double(node!.val) - target) == abs(Double(closest) - target) {
closest = min(node!.val, closest)
}
node = target < Double(node!.val) ? node!.left : node!.right
}
return closest
}
}1 340
#hard
Задача: 269. Alien Dictionary
Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.
Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.
Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".
В противном случае верните строку из уникальных букв нового инопланетного языка, отсортированных в лексикографическом порядке по правилам нового языка. Если существует несколько решений, верните любое из них.
Пример:
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"👨💻 Алгоритм: 1️⃣Извлечение отношений порядка и создание списков смежности: Извлечь отношения порядка между буквами из слов. Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого. 2️⃣Подсчет числа входящих ребер: Подсчитать количество входящих ребер (in-degree) для каждой буквы. Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы. 3️⃣Обход в ширину (BFS): Инициализировать очередь буквами с нулевым in-degree. Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым. Продолжать до тех пор, пока очередь не станет пустой. Проверить наличие циклов и вернуть результат. 😎 Решение:
import Foundation
class Solution {
func alienOrder(_ words: [String]) -> String {
var adjList = [Character: Set<Character>]()
var inDegree = [Character: Int]()
for word in words {
for char in word {
inDegree[char] = 0
}
}
for (firstWord, secondWord) in zip(words, words.dropFirst()) {
for (c, d) in zip(firstWord, secondWord) {
if c != d {
if !adjList[c, default: []].contains(d) {
adjList[c, default: []].insert(d)
inDegree[d, default: 0] += 1
}
break
}
}
if secondWord.count < firstWord.count && firstWord.hasPrefix(secondWord) {
return ""
}
}
var output = [Character]()
var queue = [Character]()
for (char, degree) in inDegree where degree == 0 {
queue.append(char)
}
while !queue.isEmpty {
let c = queue.removeFirst()
output.append(c)
for d in adjList[c] ?? [] {
inDegree[d]! -= 1
if inDegree[d] == 0 {
queue.append(d)
}
}
}
if output.count < inDegree.count {
return ""
}
return String(output)
}
}1 340
#easy
Задача: 268. Missing Number
Дан массив 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
}
}