اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Swift | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+bn3i_aLL0-A2ZGMy Вопросы собесов t.me/+wtkjBoN6OI5hNGEy Вакансии t.me/+3o9-Ytdiv_E5OGIy
نمایش بیشتر1 365
مشترکین
+124 ساعت
اطلاعاتی وجود ندارد7 روز
-730 روز
آرشیو پست ها
1 365
Задача: 438. Find All Anagrams in a String
Сложность: medium
Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".👨💻 Алгоритм: 1⃣Построить эталонный счетчик pCount для строки p. 2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева. 3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список. 😎 Решение:
class Solution {
func findAnagrams(_ s: String, _ p: String) -> [Int] {
let ns = s.count, np = p.count
if ns < np { return [] }
var pCount = [Character: Int]()
var sCount = [Character: Int]()
for ch in p {
pCount[ch, default: 0] += 1
}
var output = [Int]()
let sArray = Array(s)
for i in 0..<ns {
let ch = sArray[i]
sCount[ch, default: 0] += 1
if i >= np {
let leftChar = sArray[i - np]
if sCount[leftChar] == 1 {
sCount.removeValue(forKey: leftChar)
} else {
sCount[leftChar]! -= 1
}
}
if pCount == sCount {
output.append(i - np + 1)
}
}
return output
}
}1 365
Задача: 677. Map Sum Pairs
Сложность: medium
Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.
Пример:
Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]
Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
👨💻 Алгоритм:
1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.
2⃣Если ключ начинается с префикса, добавить его значение к ответу.
3⃣Вернуть полученную сумму как результат.
😎 Решение:
class MapSum {
private var mapData: [String: Int]
init() {
self.mapData = [:]
}
func insert(_ key: String, _ val: Int) {
mapData[key] = val
}
func sum(_ prefix: String) -> Int {
var ans = 0
for (key, val) in mapData {
if key.hasPrefix(prefix) {
ans += val
}
}
return ans
}
}1 365
Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy
Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.
Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.
Пример:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.👨💻 Алгоритм: 1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax. 2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j]. 3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers. 😎 Решение:
class Solution {
func luckyNumbers (_ matrix: [[Int]]) -> [Int] {
let N = matrix.count
let M = matrix[0].count
var rowMin = [Int]()
for i in 0..<N {
var rMin = Int.max
for j in 0..<M {
rMin = min(rMin, matrix[i][j])
}
rowMin.append(rMin)
}
var colMax = [Int]()
for i in 0..<M {
var cMax = Int.min
for j in 0..<N {
cMax = max(cMax, matrix[j][i])
}
colMax.append(cMax)
}
var luckyNumbers = [Int]()
for i in 0..<N {
for j in 0..<M {
if matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j] {
luckyNumbers.append(matrix[i][j])
}
}
}
return luckyNumbers
}
}1 365
Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
Пример:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.class Solution {
private func solve(_ root: TreeNode?, _ parent: Int, _ gParent: Int) -> Int {
guard let root = root else {
return 0
}
return solve(root.left, root.val, parent)
+ solve(root.right, root.val, parent)
+ (gParent % 2 == 0 ? root.val : 0)
}
func sumEvenGrandparent(_ root: TreeNode?) -> Int {
return solve(root, -1, -1)
}
}1 365
📱 Стажировки и вакансии для 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 365
Задача: 1066. Campus Bikes II
Сложность: medium
На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.
Мы назначаем каждому рабочему уникальный велосипед таким образом, чтобы сумма Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом была минимальной.
Верните минимально возможную сумму Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом.
Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]class Solution {
var smallestDistanceSum = Int.max
var visited = [Bool](repeating: false, count: 10)
func findDistance(_ worker: [Int], _ bike: [Int]) -> Int {
return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
}
func minimumDistanceSum(_ workers: [[Int]], _ workerIndex: Int,
_ bikes: [[Int]], _ currDistanceSum: Int) {
if workerIndex >= workers.count {
smallestDistanceSum = min(smallestDistanceSum, currDistanceSum)
return
}
if currDistanceSum >= smallestDistanceSum {
return
}
for bikeIndex in 0..<bikes.count {
if !visited[bikeIndex] {
visited[bikeIndex] = true
minimumDistanceSum(workers, workerIndex + 1, bikes,
currDistanceSum + findDistance(workers[workerIndex], bikes[bikeIndex]))
visited[bikeIndex] = false
}
}
}
func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
minimumDistanceSum(workers, 0, bikes, 0)
return smallestDistanceSum
}
}1 365
Задача: 354. Russian Doll Envelopes
Сложность: hard
Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.
Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).
Примечание: Вы не можете поворачивать конверт.
Пример:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).👨💻 Алгоритм: 1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте). 2⃣Извлеките вторую размерность (высоты) отсортированного массива. 3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот. 😎 Решение:
class Solution {
func lengthOfLIS(_ nums: [Int]) -> Int {
var dp = [Int](repeating: 0, count: nums.count)
var len = 0
for num in nums {
var i = dp.binarySearch(0..<len, num)
if i < 0 { i = -(i + 1) }
dp[i] = num
if i == len { len += 1 }
}
return len
}
func maxEnvelopes(_ envelopes: [[Int]]) -> Int {
let sortedEnvelopes = envelopes.sorted {
if $0[0] == $1[0] { return $0[1] > $1[1] }
return $0[0] < $1[0]
}
let secondDim = sortedEnvelopes.map { $0[1] }
return lengthOfLIS(secondDim)
}
}
extension Array where Element == Int {
func binarySearch(_ range: Range<Int>, _ target: Int) -> Int {
var left = range.lowerBound
var right = range.upperBound
while left < right {
let mid = left + (right - left) / 2
if self[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left < range.upperBound && self[left] == target ? left : -(left + 1)
}
}1 365
Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium
Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три.
Пример:
Input: nums = [3,6,5,1,8] Output: 18👨💻 Алгоритм: 1⃣Найдите сумму всех элементов массива. 2⃣Если сумма делится на 3, то она и есть ответ. 3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2). Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2). 😎 Решение:
class Solution {
func maxSumDivThree(_ nums: [Int]) -> Int {
let totalSum = nums.reduce(0, +)
if totalSum % 3 == 0 {
return totalSum
}
var mod1 = [Int]()
var mod2 = [Int]()
for num in nums {
if num % 3 == 1 {
mod1.append(num)
} else if num % 3 == 2 {
mod2.append(num)
}
}
mod1.sort()
mod2.sort()
if totalSum % 3 == 1 {
let remove1 = mod1.isEmpty ? Int.max : mod1[0]
let remove2 = mod2.count < 2 ? Int.max : mod2[0] + mod2[1]
return totalSum - min(remove1, remove2)
} else {
let remove2 = mod2.isEmpty ? Int.max : mod2[0]
let remove1 = mod1.count < 2 ? Int.max : mod1[0] + mod1[1]
return totalSum - min(remove2, remove1)
}
}
}1 365
Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy
Даны два массива строк
word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.
Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку.
Пример:
Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.class Solution {
func arrayStringsAreEqual(_ word1: [String], _ word2: [String]) -> Bool {
let list2 = word2.joined()
var index = list2.startIndex
for word in word1 {
for char in word {
if index == list2.endIndex || char != list2[index] {
return false
}
index = list2.index(after: index)
}
}
return index == list2.endIndex
}
}1 365
Задача: 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 365
Задача: 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 365
Задача: 1110. Delete Nodes And Return Forest
Сложность: medium
Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).
Верните корни деревьев в оставшемся лесу. Вы можете вернуть результат в любом порядке.
Пример:
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]👨💻 Алгоритм: 1⃣Инициализация: Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска. Создайте пустой список forest для хранения корней деревьев в результирующем лесу. 2⃣Рекурсивный обход: Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node): - рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением. 3⃣Оценка узла: Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить: - если у узла есть левый или правый дочерний узел, добавьте их в forest. - верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу. Если узел не нужно удалять, верните сам узел. 😎 Решение:
class Solution {
func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
var toDeleteSet = Set(to_delete)
var forest = [TreeNode?]()
func processNode(_ node: TreeNode?) -> TreeNode? {
guard let node = node else { return nil }
node.left = processNode(node.left)
node.right = processNode(node.right)
if toDeleteSet.contains(node.val) {
if let left = node.left { forest.append(left) }
if let right = node.right { forest.append(right) }
return nil
}
return node
}
let root = processNode(root)
if let root = root { forest.append(root) }
return forest
}
}1 365
Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard
Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.
Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами:
Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение.
В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше.
Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты.
Пример:
Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.class Solution {
func mincostToHireWorkers(_ quality: [Int], _ wage: [Int], _ k: Int) -> Double {
let n = quality.count
var totalCost = Double.greatestFiniteMagnitude
var currentTotalQuality = 0.0
var wageToQualityRatio = [(Double, Int)]()
for i in 0..<n {
wageToQualityRatio.append((Double(wage[i]) / Double(quality[i]), quality[i]))
}
wageToQualityRatio.sort { $0.0 < $1.0 }
var workers = PriorityQueue<Int>(sort: >)
for ratio in wageToQualityRatio {
workers.enqueue(ratio.1)
currentTotalQuality += Double(ratio.1)
if workers.count > k {
currentTotalQuality -= Double(workers.dequeue()!)
}
if workers.count == k {
totalCost = min(totalCost, currentTotalQuality * ratio.0)
}
}
return totalCost
}
}
struct PriorityQueue<Element: Comparable> {
private var elements: [Element] = []
private let sort: (Element, Element) -> Bool
init(sort: @escaping (Element, Element) -> Bool) {
self.sort = sort
}
var count: Int {
return elements.count
}
mutating func enqueue(_ element: Element) {
elements.append(element)
elements.sort(by: sort)
}
mutating func dequeue() -> Element? {
return elements.isEmpty ? nil : elements.removeFirst()
}
}1 365
Задача: 384. Shuffle an Array
Сложность: medium
Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.
Реализуйте класс Solution:
Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.
Пример:
Input: ransomNote = "a", magazine = "b" Output: false👨💻 Алгоритм: 1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива. 2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент. 3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие. 😎 Решение:
class Solution {
private var array: [Int]
private let original: [Int]
init(_ nums: [Int]) {
self.array = nums
self.original = nums
}
func reset() -> [Int] {
self.array = self.original
return self.original
}
func shuffle() -> [Int] {
for i in 0..<array.count {
let randIndex = Int.random(in: i..<array.count)
array.swapAt(i, randIndex)
}
return array
}
}1 365
Задача: 662. Maximum Width of Binary Tree
Сложность: medium
Дан корень бинарного дерева, верните максимальную ширину данного дерева.
Максимальная ширина дерева - это максимальная ширина среди всех уровней.
Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.
Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.
Пример:
Input: root = [1,3,2,5,3,null,9] Output: 4 Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).👨💻 Алгоритм: 1⃣Инициализация: Создайте очередь для хранения узлов и их позиций на уровне. Начните с корневого узла и его позиции 0. 2⃣Обработка каждого уровня: Для каждого уровня дерева получите его узлы и их позиции. Вычислите ширину уровня как разницу между максимальной и минимальной позициями плюс один. 3⃣Обновление максимальной ширины: Обновите максимальную ширину, если текущая ширина уровня больше. 😎 Решение:
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
class Solution {
func widthOfBinaryTree(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
var maxWidth = 0
var queue: [(TreeNode, Int)] = [(root, 0)]
while !queue.isEmpty {
let levelSize = queue.count
let firstPos = queue.first!.1
for _ in 0..<levelSize {
let (node, pos) = queue.removeFirst()
if let left = node.left {
queue.append((left, 2 * pos))
}
if let right = node.right {
queue.append((right, 2 * pos + 1))
}
if node === queue.last?.0 {
maxWidth = max(maxWidth, pos - firstPos + 1)
}
}
}
return maxWidth
}
}1 365
Задача: 897. Increasing Order Search Tree
Сложность: easy
Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.
Пример:
Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9] Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]👨💻 Алгоритм: 1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов. 2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null. 3⃣Вернуть новый корень дерева (первый элемент списка). 😎 Решение:
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
func increasingBST(_ root: TreeNode?) -> TreeNode? {
var nodes: [TreeNode] = []
func inorder(_ node: TreeNode?) {
guard let node = node else { return }
inorder(node.left)
nodes.append(node)
inorder(node.right)
}
inorder(root)
for i in 0..<nodes.count - 1 {
nodes[i].left = nil
nodes[i].right = nodes[i + 1]
}
nodes.last?.left = nil
nodes.last?.right = nil
return nodes.first
}1 365
Задача: 642. Design Search Autocomplete System
Сложность: hard
Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.
Пример:
Input ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 2, true, true, true, 4]👨💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:
class TrieNode {
var children = [Character: TrieNode]()
var count = [String: Int]()
}
class AutocompleteSystem {
private var root = TrieNode()
private var prefix = ""
init(_ sentences: [String], _ times: [Int]) {
for i in 0..<sentences.count {
add(sentences[i], times[i])
}
}
private func add(_ sentence: String, _ count: Int) {
var node = root
for char in sentence {
if node.children[char] == nil {
node.children[char] = TrieNode()
}
node = node.children[char]!
node.count[sentence, default: 0] += count
}
}
func input(_ c: Character) -> [String] {
if c == "#" {
add(prefix, 1)
prefix = ""
return []
}
prefix.append(c)
var node = root
for char in prefix {
if node.children[char] == nil {
return []
}
node = node.children[char]!
}
let pq = node.count.sorted { lhs, rhs in
if lhs.value == rhs.value {
return lhs.key < rhs.key
}
return lhs.value > rhs.value
}
return Array(pq.prefix(3)).map { $0.key }
}
}1 365
Задача: 521. Longest Uncommon Subsequence I
Сложность: easy
Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1.
Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них.
Пример:
Input: a = "aba", b = "cdc" Output: 3 Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc". Note that "cdc" is also a longest uncommon subsequence.👨💻 Алгоритм: 1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности. 2⃣В противном случае: Вычислите длины строк a и b. 3⃣Верните длину более длинной строки. 😎 Решение:
class Solution {
func findLUSlength(_ a: String, _ b: String) -> Int {
if a == b {
return -1
} else {
return max(a.count, b.count)
}
}
}1 365
Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium
Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.
Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:
Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.
Пример:
Input: grid = [[0,1],[1,0]] Output: 2👨💻 Алгоритм: 1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1. 2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки. 3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1. 😎 Решение:
class Solution {
private let directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
if grid[0][0] != 0 || grid[grid.count - 1][grid[0].count - 1] != 0 {
return -1
}
var grid = grid
var queue: [(Int, Int)] = [(0, 0)]
grid[0][0] = 1
while !queue.isEmpty {
let (row, col) = queue.removeFirst()
let distance = grid[row][col]
if row == grid.count - 1 && col == grid[0].count - 1 {
return distance
}
for direction in directions {
let newRow = row + direction.0
let newCol = col + direction.1
if newRow >= 0 && newCol >= 0 && newRow < grid.count && newCol < grid[0].count && grid[newRow][newCol] == 0 {
queue.append((newRow, newCol))
grid[newRow][newCol] = distance + 1
}
}
}
return -1
}
}1 365
Задача: 583. Delete Operation for Two Strings
Сложность: medium
Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.
Пример:
Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2. 2⃣ Заполнение массива: Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки. 3⃣ Обновление и результат: Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений. 😎 Решение:
class Solution {
func minDistance(_ word1: String, _ word2: String) -> Int {
let m = word1.count, n = word2.count
var dp = [Int](repeating: 0, count: n + 1)
let s1 = Array(word1), s2 = Array(word2)
for i in 0...m {
var temp = [Int](repeating: 0, count: n + 1)
for j in 0...n {
if i == 0 || j == 0 {
temp[j] = i + j
} else if s1[i - 1] == s2[j - 1] {
temp[j] = dp[j - 1]
} else {
temp[j] = 1 + min(dp[j], temp[j - 1])
}
}
dp = temp
}
return dp[n]
}
}