متاح الآن! بحث تيليغرام 2025 — أهم رؤى العام 
Swift | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
إظهار المزيد1 343
المشتركون
-424 ساعات
-97 أيام
-2230 أيام
أرشيف المشاركات
1 343
Задача: 631. Design Excel Sum Formula
Сложность: hard
Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.
Пример:
Input ["Excel", "set", "sum", "set", "get"] [[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]] Output [null, null, 4, null, 6]👨💻 Алгоритм: 1⃣Инициализация Создайте класс Excel, который будет инициализировать матрицу нужного размера и хранить текущие значения ячеек. Реализуйте методы для установки значений, получения значений и вычисления суммы. 2⃣Метод установки значений Реализуйте метод set, который будет изменять значение ячейки в матрице. 3⃣Метод вычисления суммы Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек. 😎 Решение:
class Excel {
private var mat: [[Int]]
private var formulas: [String: [String]]
init(_ height: Int, _ width: Character) {
mat = Array(repeating: Array(repeating: 0, count: Int(width.asciiValue! - Character("A").asciiValue!) + 1), count: height)
formulas = [String: [String]]()
}
func set(_ row: Int, _ column: Character, _ val: Int) {
mat[row - 1][Int(column.asciiValue! - Character("A").asciiValue!)] = val
formulas.removeValue(forKey: "\(row)\(column)")
}
func get(_ row: Int, _ column: Character) -> Int {
let key = "\(row)\(column)"
if let _ = formulas[key] {
return evaluateFormula(key)
}
return mat[row - 1][Int(column.asciiValue! - Character("A").asciiValue!)]
}
func sum(_ row: Int, _ column: Character, _ numbers: [String]) -> Int {
let key = "\(row)\(column)"
formulas[key] = numbers
return evaluateFormula(key)
}
private func evaluateFormula(_ key: String) -> Int {
guard let numbers = formulas[key] else { return 0 }
var total = 0
for number in numbers {
if let rangeIndex = number.firstIndex(of: ":") {
let start = String(number.prefix(upTo: rangeIndex))
let end = String(number.suffix(from: number.index(after: rangeIndex)))
let startRow = Int(start.suffix(start.count - 1))!
let startCol = start.prefix(1).first!
let endRow = Int(end.suffix(end.count - 1))!
let endCol = end.prefix(1).first!
for r in startRow...endRow {
for c in startCol.asciiValue!...endCol.asciiValue! {
total += get(r, Character(UnicodeScalar(c)))
}
}
} else {
let row = Int(number.suffix(number.count - 1))!
let col = number.prefix(1).first!
total += get(row, col)
}
}
return total
}
}1 343
Задача: 1046. Last Stone Weight
Сложность: easy
Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.
Пример:
Input: stones = [2,7,4,1,8,1] Output: 1👨💻 Алгоритм: 1⃣Создай максимальную кучу из массива камней. 2⃣Извлекай два самых тяжелых камня, разбивай их, и, если необходимо, возвращай оставшийся камень обратно в кучу. 3⃣Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0, если камней не осталось. 😎 Решение:
func lastStoneWeight(_ stones: [Int]) -> Int {
var maxHeap = Heap(array: stones, sort: >)
while maxHeap.count > 1 {
let first = maxHeap.remove()!
let second = maxHeap.remove()!
if first != second {
maxHeap.insert(first - second)
}
}
return maxHeap.peek() ?? 0
}
struct Heap<Element: Equatable> {
var elements: [Element]
let sort: (Element, Element) -> Bool
init(array: [Element], sort: @escaping (Element, Element) -> Bool) {
self.elements = array
self.sort = sort
buildHeap()
}
var isEmpty: Bool { return elements.isEmpty }
var count: Int { return elements.count }
func peek() -> Element? { return elements.first }
mutating func buildHeap() {
for index in (0 ..< count / 2).reversed() {
siftDown(from: index)
}
}
mutating func insert(_ value: Element) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func remove() -> Element? {
guard !isEmpty else { return nil }
elements.swapAt(0, count - 1)
defer { siftDown(from: 0) }
return elements.removeLast()
}
mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var candidate = parent
if left < count && sort(elements[left], elements[candidate]) {
candidate = left
}
if right < count && sort(elements[right], elements[c1 343
Задача: 625. Minimum Factorization
Сложность: medium
Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.
Пример:
Input: num = 48 Output: 68👨💻 Алгоритм: 1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей. 2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0. 3⃣Постройте результат, собирая найденные множители в обратном порядке. Если результат больше 32-битного целого числа, верните 0. 😎 Решение:
func smallestFactorization(_ num: Int) -> Int {
if num == 1 {
return 1
}
var num = num
var factors = [Int]()
for i in stride(from: 9, through: 2, by: -1) {
while num % i == 0 {
factors.append(i)
num /= i
}
}
if num > 1 {
return 0
}
var result: Int64 = 0
for factor in factors.reversed() {
result = result * 10 + Int64(factor)
if result > Int32.max {
return 0
}
}
return Int(result)
}1 343
Задача: 279. Perfect Squares
Сложность: medium
Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.
Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.
Пример:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.👨💻 Алгоритм: 1⃣Инициализация: Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0. Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums. 2⃣Заполнение массива dp: Для каждого числа i от 1 до n: Для каждого совершенного квадрата s из массива square_nums: Если i меньше текущего совершенного квадрата s, прервите внутренний цикл. Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i. 3⃣Возврат результата: Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n. 😎 Решение:
class Solution {
func numSquares(_ n: Int) -> Int {
var dp = [Int](repeating: Int.max, count: n + 1)
dp[0] = 0
let maxSquareIndex = Int(Double(n).squareRoot()) + 1
var squareNums = [Int](repeating: 0, count: maxSquareIndex)
for i in 1..<maxSquareIndex {
squareNums[i] = i * i
}
for i in 1...n {
for s in 1..<maxSquareIndex {
if i < squareNums[s] {
break
}
dp[i] = min(dp[i], dp[i - squareNums[s]] + 1)
}
}
return dp[n]
}
}1 343
Задача: 1160. Find Words That Can Be Formed by Characters
Сложность: easy
Вам дан массив строк words и строка chars.
Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз).
Верните сумму длин всех хороших строк в words.
Пример:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.class Solution {
func countCharacters(_ words: [String], _ chars: String) -> Int {
var counts = [Character: Int]()
for c in chars {
counts[c, default: 0] += 1
}
var ans = 0
for word in words {
var wordCount = [Character: Int]()
for c in word {
wordCount[c, default: 0] += 1
}
var good = true
for (c, freq) in wordCount {
if counts[c, default: 0] < freq {
good = false
break
}
}
if good {
ans += word.count
}
}
return ans
}
}1 343
Задача: 517. Super Washing Machines
Сложность: hard
У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.
За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.
Дан целочисленный массив machines, представляющий количество платьев в каждой стиральной машине слева направо по линии. Верните минимальное количество ходов, необходимых для того, чтобы во всех стиральных машинах стало одинаковое количество платьев. Если это невозможно, верните -1.
Пример:
Input: machines = [1,0,5] Output: 3 Explanation: 1st move: 1 0 <-- 5 => 1 1 4 2nd move: 1 <-- 1 <-- 4 => 2 1 3 3rd move: 2 1 <-- 3 => 2 2 2👨💻 Алгоритм: 1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение). 2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)). 3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res. 😎 Решение:
class Solution {
func findMinMoves(_ machines: [Int]) -> Int {
let n = machines.count
let dressTotal = machines.reduce(0, +)
if dressTotal % n != 0 { return -1 }
let dressPerMachine = dressTotal / n
var machines = machines.map { $0 - dressPerMachine }
var currSum = 0
var maxSum = 0
var res = 0
for m in machines {
currSum += m
maxSum = max(maxSum, abs(currSum))
res = max(res, max(maxSum, m))
}
return res
}
}1 343
Задача: 1042. Flower Planting With No Adjacent
Сложность: medium
У вас есть n садов, помеченных от 1 до n, и массив paths, где paths[i] = [xi, yi] описывает двунаправленный путь между садом xi и садом yi. В каждом саду вы хотите посадить один из 4 типов цветов. Все сады имеют не более 3 путей, входящих и выходящих из него. Ваша задача - выбрать тип цветка для каждого сада так, чтобы для любых двух садов, соединенных путем, они имели разные типы цветов. Верните любой такой выбор в виде массива answer, где answer[i] - тип цветка, посаженного в (i+1)-м саду. Типы цветов обозначаются 1, 2, 3 или 4. Ответ гарантированно существует.
Пример:
Input: n = 3, paths = [[1,2],[2,3],[3,1]] Output: [1,2,3]👨💻 Алгоритм: 1⃣Построение графа: Создайте граф из садов и путей между ними. 2⃣Присваивание цветов: Для каждого сада выберите тип цветка, который не используется соседними садами. 3⃣Мы будем проходить по каждому саду и выбирать тип цветка, который не совпадает с типами цветов в соседних садах. Поскольку у каждого сада не более трех соседей, всегда будет возможность выбрать тип цветка из 4 возможных типов. 😎 Решение:
class Solution {
func gardenNoAdj(_ n: Int, _ paths: [[Int]]) -> [Int] {
var graph = [[Int]](repeating: [], count: n)
for path in paths {
graph[path[0] - 1].append(path[1] - 1)
graph[path[1] - 1].append(path[0] - 1)
}
var answer = [Int](repeating: 0, count: n)
for garden in 0..<n {
var used = Set(answer[graph[garden]])
for flower in 1...4 {
if !used.contains(flower) {
answer[garden] = flower
break
}
}
}
return answer
}
}1 343
Задача: 1033. Moving Stones Until Consecutive
Сложность: medium
На оси X расположены три камня в разных позициях. Вам даны три целых числа a, b и c - позиции камней. За одно движение вы берете камень в конечной точке (т. е. либо в самой низкой, либо в самой высокой позиции камня) и перемещаете его в незанятую позицию между этими конечными точками. Формально, допустим, камни в данный момент находятся в позициях x, y и z, причем x < y < z. Вы берете камень в позиции x или z и перемещаете его в целочисленную позицию k, причем x < k < z и k != y. Игра заканчивается, когда вы больше не можете сделать ни одного хода (то есть камни находятся в трех последовательных позициях). Возвращается целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сыграть, а answer[1] - максимальное количество ходов, которое вы можете сыграть.
Пример:
Input: a = 3, b = 5, c = 1 Output: [1,2]👨💻 Алгоритм: 1⃣Сортировка позиций: Убедитесь, что позиции камней отсортированы в порядке возрастания. Обозначим отсортированные позиции как x, y и z. 2⃣Вычисление минимальных ходов: Если камни уже находятся в последовательных позициях (то есть y - x == 1 и z - y == 1), минимальное количество ходов равно 0. Если два камня находятся в соседних позициях, а третий камень на расстоянии более чем одна позиция, минимальное количество ходов равно 1. В остальных случаях минимальное количество ходов равно 2. 3⃣Вычисление максимальных ходов: Максимальное количество ходов равно сумме расстояний между соседними камнями минус 2, то есть (y - x - 1) + (z - y - 1). 😎 Решение:
class Solution {
func numMovesStones(_ a: Int, _ b: Int, _ c: Int) -> [Int] {
let stones = [a, b, c].sorted()
let x = stones[0], y = stones[1], z = stones[2]
let minMoves = (y - x <= 2 || z - y <= 2) ? ((y - x == 1 && z - y == 1) ? 0 : 1) : 2
let maxMoves = (y - x - 1) + (z - y - 1)
return [minMoves, maxMoves]
}
}1 343
Задача: 368. Largest Divisible Subset
Сложность: medium
Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию:
answer[i] % answer[j] == 0, или
answer[j] % answer[i] == 0
Если существует несколько решений, вернуть любое из них.
Пример:
Input: nums = [1,2,3] Output: [1,2] Explanation: [1,3] is also accepted.👨💻 Алгоритм: 1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4). 2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8). 3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}. 😎 Решение:
class Solution {
func largestDivisibleSubset(_ nums: [Int]) -> [Int] {
let n = nums.count
if n == 0 { return [] }
var EDS = Array(repeating: [Int](), count: n)
var nums = nums.sorted()
// Calculate all the values of EDS(X_i)
for i in 0..<n {
var maxSubset = [Int]()
for k in 0..<i {
if nums[i] % nums[k] == 0 && maxSubset.count < EDS[k].count {
maxSubset = EDS[k]
}
}
EDS[i] = maxSubset + [nums[i]]
}
var ret = [Int]()
for subset in EDS {
if ret.count < subset.count {
ret = subset
}
}
return ret
}
}1 343
Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard
Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.
Пример:
Input: left = 10, right = 15 Output: 5👨💻 Алгоритм: 1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа. 2⃣Создайте функцию для проверки, является ли число простым. 3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом. 😎 Решение:
func countPrimeSetBits(_ left: Int, _ right: Int) -> Int {
func countBits(_ x: Int) -> Int {
return String(x, radix: 2).filter { $0 == "1" }.count
}
func isPrime(_ x: Int) -> Bool {
if x < 2 { return false }
for i in 2..<Int(Double(x).squareRoot()) + 1 {
if x % i == 0 { return false }
}
return true
}
var count = 0
for num in left...right {
if isPrime(countBits(num)) {
count += 1
}
}
return count
}1 343
Задача: 142. Linked List Cycle II
Сложность: medium
Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.
Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.
Не модифицируйте связный список.
Пример:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.👨💻 Алгоритм: 1⃣Инициализация и начало обхода: Инициализируйте узел указателем на голову связного списка и создайте пустое множество nodes_seen для отслеживания посещенных узлов. Начните обход со связного списка, перемещая узел на один шаг за раз. 2⃣Проверка на наличие узла в множестве: Для каждого посещенного узла проверьте, содержится ли он уже в множестве nodes_seen. Если узел найден в множестве, это означает, что был найден цикл. Верните текущий узел как точку входа в цикл. 3⃣Добавление узла в множество или завершение обхода: Если узел не найден в nodes_seen, добавьте его в множество и перейдите к следующему узлу. Если узел становится равным null (конец списка), верните null. В списке нет цикла, так как в случае наличия цикла вы бы застряли в петле и не достигли бы конца списка. 😎 Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int, _ next: ListNode? = nil) {
self.val = val
self.next = next
}
}
func detectCycle(_ head: ListNode?) -> ListNode? {
var nodesSeen = Set<ListNode>()
var node = head
while node != nil {
if nodesSeen.contains(node!) {
return node
} else {
nodesSeen.insert(node!)
node = node!.next
}
}
return nil
}1 343
Задача: 159. Longest Substring with At Most Two Distinct Characters
Сложность: medium
Дана строка s. Вернуть длину самой длинной подстроки, которая содержит не более двух различных символов.
Пример:
Input: s = "eceba" Output: 3 Explanation: The substring is "ece" which its length is 3.👨💻 Алгоритм: 1⃣Вернуть N, если длина строки N меньше 3. 2⃣Установить оба указателя в начало строки: left = 0 и right = 0, и инициализировать максимальную длину подстроки max_len = 2. 3⃣Пока указатель right меньше N: Если хеш-таблица содержит менее 3 различных символов, добавить текущий символ s[right] в хеш-таблицу и сдвинуть указатель right вправо. Если хеш-таблица содержит 3 различных символа, удалить самый левый символ из хеш-таблицы и сдвинуть указатель left так, чтобы скользящее окно содержало только 2 различных символа. Обновить max_len. 😎 Решение:
func lengthOfLongestSubstringTwoDistinct(_ s: String) -> Int {
let n = s.count
if n < 3 { return n }
let chars = Array(s)
var left = 0
var right = 0
var hashmap = [Character: Int]()
var max_len = 2
while right < n {
hashmap[chars[right]] = right
right += 1
if hashmap.count == 3 {
let del_idx = hashmap.values.min()!
hashmap.removeValue(forKey: chars[del_idx])
left = del_idx + 1
}
max_len = max(max_len, right - left)
}
return max_len
}1 343
Задача: 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 343
Задача: 624. Maximum Distance in Arrays
Сложность: medium
Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.
Пример:
Input: root = [4,2,6,3,1,5], val = 1, depth = 2 Output: [4,1,1,2,null,null,6,3,1,5]👨💻 Алгоритм: 1⃣Найдите минимальный элемент из всех первых элементов массивов и максимальный элемент из всех последних элементов массивов. 2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами. 3⃣Верните это максимальное расстояние. 😎 Решение:
func maxDistance(_ arrays: [[Int]]) -> Int {
var minElement = arrays[0][0]
var maxElement = arrays[0].last!
var maxDistance = 0
for array in arrays[1...] {
maxDistance = max(maxDistance, abs(array.last! - minElement), abs(maxElement - array[0]))
minElement = min(minElement, array[0])
maxElement = max(maxElement, array.last!)
}
return maxDistance
}1 343
Задача: 1242. Web Crawler Multithreaded
Сложность: medium
Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.
Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.
Пример:
Input: urls = [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.google.com", "http://news.yahoo.com/us" ] edges = [[2,0],[2,1],[3,2],[3,1],[0,4]] startUrl = "http://news.yahoo.com/news/topics/" Output: [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.yahoo.com/us" ]👨💻 Алгоритм: 1⃣Извлечь имя хоста из startUrl. Использовать многопоточность для обработки URL-адресов. 2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения. 3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц. 😎 Решение:
import Foundation
class HtmlParser {
func getUrls(_ url: String) -> [String] {
return []
}
}
class Solution {
private var visited = Set<String>()
private let lock = NSLock()
func crawl(_ startUrl: String, _ htmlParser: HtmlParser) -> [String] {
let hostname = extractHostname(from: startUrl)
let queue = DispatchQueue(label: "crawler", attributes: .concurrent)
let group = DispatchGroup()
visited.insert(startUrl)
crawlHelper(startUrl, htmlParser, hostname, queue, group)
group.wait()
return Array(visited)
}
private func extractHostname(from url: String) -> String {
let components = URLComponents(string: url)
return components?.host ?? ""
}
private func crawlHelper(_ url: String, _ htmlParser: HtmlParser, _ hostname: String, _ queue: DispatchQueue, _ group: DispatchGroup) {
group.enter()
queue.async {
defer { group.leave() }
let urls = htmlParser.getUrls(url)
for nextUrl in urls {
if self.extractHostname(from: nextUrl) == hostname {
self.lock.lock()
if self.visited.insert(nextUrl).inserted {
self.lock.unlock()
self.crawlHelper(nextUrl, htmlParser, hostname, queue, group)
} else {
self.lock.unlock()
}
}
}
}
}
}1 343
Задача: 138. Copy List with Random Pointer
Сложность: medium
Дан связный список длиной n, в котором каждый узел содержит дополнительный случайный указатель (random pointer), который может указывать на любой узел в списке или быть равным null.
Создайте глубокую копию списка. Глубокая копия должна состоять из ровно n совершенно новых узлов, где каждый новый узел имеет значение, равное значению соответствующего оригинального узла. Указатели next и random новых узлов должны указывать на новые узлы в скопированном списке таким образом, чтобы указатели в оригинальном и скопированном списке представляли одно и то же состояние списка. Ни один из указателей в новом списке не должен указывать на узлы в оригинальном списке.
Например, если в оригинальном списке есть два узла X и Y, где X.random --> Y, то для соответствующих узлов x и y в скопированном списке, x.random должен указывать на y.
Верните голову скопированного связного списка.
Связный список представлен во входных/выходных данных как список из n узлов. Каждый узел представлен парой [val, random_index], где:
val: целое число, представляющее Node.val
random_index: индекс узла (в диапазоне от 0 до n-1), на который указывает случайный указатель, или null, если он не указывает ни на какой узел.
Вашему коду будет дана только голова оригинального связного списка.
Пример:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]👨💻 Алгоритм: 1⃣Инициализация и начало обхода: Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов. 2⃣Проверка и клонирование узлов: Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary. Если клонированная копия существует, используйте ссылку на этот клонированный узел. Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон. 3⃣Рекурсивные вызовы для обработки связей: Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next. Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next. 😎 Решение:
class Node {
var val: Int
var next: Node?
var random: Node?
init(_ val: Int, _ next: Node?, _ random: Node?) {
self.val = val
self.next = next
self.random = random
}
}
func copyRandomList(_ head: Node?) -> Node? {
var visitedHash = [Node: Node]()
func cloneNode(_ node: Node?) -> Node? {
guard let node = node else {
return nil
}
if let visitedNode = visitedHash[node] {
return visitedNode
}
let newNode = Node(node.val, nil, nil)
visitedHash[node] = newNode
newNode.next = cloneNode(node.next)
newNode.random = cloneNode(node.random)
return newNode
}
return cloneNode(head)
}1 343
Задача: 336. Palindrome Pairs
Сложность: hard
Вам дан массив уникальных строк words, индексируемый с 0.
Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.
Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).
Пример:
Input: words = ["abcd","dcba","lls","s","sssll"] Output: [[0,1],[1,0],[3,2],[2,4]] Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]👨💻 Алгоритм: 1⃣ Инициализация и подготовка данных: Создайте структуру для хранения результатов (список пар индексов). Создайте словарь для хранения слов и их индексов, чтобы ускорить поиск. 2⃣ Итерация по всем парам слов и проверка: Пройдите по всем парам слов в массиве words, используя два вложенных цикла. Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии. 3⃣ Добавление найденных пар в результат: Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов. Верните итоговый список всех найденных пар. 😎 Решение:
class Solution {
func palindromePairs(_ words: [String]) -> [[Int]] {
var pairs = [[Int]]()
for i in 0..<words.count {
for j in 0..<words.count {
if i == j { continue }
let combined = words[i] + words[j]
if combined == String(combined.reversed()) {
pairs.append([i, j])
}
}
}
return pairs
}
}1 343
Задача: 85. Maximal Rectangle
Сложность: hard
Дана бинарная матрица размером rows x cols, заполненная 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: 6 Explanation: The maximal rectangle is shown in the above picture.👨💻 Алгоритм: 1⃣Вычисление максимальной ширины прямоугольника для каждой координаты: Для каждой ячейки в каждой строке сохраняем количество последовательных единиц. При прохождении по строке обновляем максимально возможную ширину в этой точке, используя формулу row[i] = row[i - 1] + 1, если row[i] == '1'. 2⃣Определение максимальной площади прямоугольника с нижним правым углом в данной точке: При итерации вверх по столбцу максимальная ширина прямоугольника от исходной точки до текущей точки является минимальным значением среди всех максимальных ширин, с которыми мы сталкивались. Используем формулу maxWidth = min(maxWidth, widthHere) и curArea = maxWidth * (currentRow - originalRow + 1), затем обновляем maxArea = max(maxArea, curArea). 3⃣Применение алгоритма для каждой точки ввода для глобального максимума: Преобразуя входные данные в набор гистограмм, где каждый столбец является новой гистограммой, мы вычисляем максимальную площадь для каждой гистограммы. 😎 Решение:
func maximalRectangle(matrix: [[Character]]) -> Int {
if matrix.isEmpty { return 0 }
var maxArea = 0
var dp = Array(repeating: Array(repeating: 0, count: matrix[0].count), count: matrix.count)
for i in 0..<matrix.count {
for j in 0..<matrix[0].count {
if matrix[i][j] == "1" {
dp[i][j] = j == 0 ? 1 : dp[i][j-1] + 1
var width = dp[i][j]
for k in stride(from: i, through: 0, by: -1) {
width = min(width, dp[k][j])
maxArea = max(maxArea, width * (i - k + 1))
}
}
}
}
return maxArea
}1 343
Задача: 426. Convert Binary Search Tree to Sorted Doubly Linked List
Сложность: medium
Преобразуйте двоичное дерево поиска в отсортированный кольцевой двусвязный список на месте.
Вы можете считать, что указатели "влево" и "вправо" аналогичны указателям на предшественника и последователя в двусвязном списке. Для кольцевого двусвязного списка предшественник первого элемента является последним элементом, а последователь последнего элемента является первым элементом.
Мы хотим выполнить преобразование на месте. После преобразования левый указатель узла дерева должен указывать на его предшественника, а правый указатель должен указывать на его последователя. Вы должны вернуть указатель на самый маленький элемент списка.
Пример:
Input: root = [4,2,5,1,3] Output: [1,2,3,4,5] Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.👨💻 Алгоритм: 1⃣Инициализируйте первые и последние узлы как null. 2⃣Вызовите стандартную вспомогательную рекурсивную функцию helper(root): Если узел не равен null: Вызовите рекурсию для левого поддерева helper(node.left). Если последний узел не равен null, свяжите последний узел и текущий узел. Иначе инициализируйте первый узел. Пометьте текущий узел как последний: last = node. Вызовите рекурсию для правого поддерева helper(node.right). 3⃣Свяжите первые и последние узлы, чтобы замкнуть кольцевой двусвязный список, затем верните первый узел. 😎 Решение:
class Node {
var val: Int
var left: Node?
var right: Node?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
class Solution {
var first: Node? = nil
var last: Node? = nil
func helper(_ node: Node?) {
guard let node = node else { return }
helper(node.left)
if let last = last {
last.right = node
node.left = last
} else {
first = node
}
last = node
helper(node.right)
}
func treeToDoublyList(_ root: Node?) -> Node? {
guard let root = root else { return nil }
helper(root)
last?.right = first
first?.left = last
return first
}
}1 343
Задача: 1009. Complement of Base 10 Integer
Сложность: easy
Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.
Пример:
Input: n = 5 Output: 2👨💻 Алгоритм: 1⃣Определение длины двоичного представления: Найдите длину двоичного представления числа n. 2⃣Создание маски: Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n. 3⃣Вычисление дополнения: Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа. 😎 Решение:
class Solution {
func findComplement(_ num: Int) -> Int {
let length = Int.bitWidth - num.leadingZeroBitCount
let mask = (1 << length) - 1
return num ^ mask
}
}