Задача: 1242. Web Crawler Multithreaded
Сложность: medium

Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.

Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.

Пример:

Input:
urls = [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.google.com",
  "https://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "https://news.yahoo.com/news/topics/"
Output: [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://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()
                    }
                }
            }
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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]
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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.

👨‍💻 Алгоритм:

1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0.

2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл.

3⃣Если good = true, добавьте длину слова к ans. Верните ans.

😎 Решение

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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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]
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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)
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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[c

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

Input: n = 2, trust = [[1,2]]
Output: 2

👨‍💻 Алгоритм:

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

2⃣Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.

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 insertIntoMaxTree(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        guard let root = root else { return TreeNode(val) }
        if val > root.val {
            return TreeNode(val, root, nil)
        }
        root.right = insertIntoMaxTree(root.right, val)
        return root
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1216. Valid Palindrome III
Сложность: hard

Дана строка s и целое число k. Верните true, если s является k-палиндромом.
Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.

Пример:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

👨‍💻 Алгоритм:

1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j.

2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo.

3⃣Реализуйте основные случаи рекурсивного вычисления: если символы на позициях i и j совпадают, продолжайте проверку для подстроки без этих символов. В противном случае, рассмотрите два варианта удаления символов и выберите минимальное количество удалений, добавив 1 за текущее удаление.

😎 Решение:

class Solution {
    var memo: [[Int?]] = []

    func isValidPalindrome(_ s: String, _ k: Int) -> Bool {
        let n = s.count
        memo = Array(repeating: Array(repeating: nil, count: n), count: n)
        let sArray = Array(s)
        return isValidPalindromeHelper(sArray, 0, n - 1) <= k
    }

    private func isValidPalindromeHelper(_ s: [Character], _ i: Int, _ j: Int) -> Int {
        if i == j {
            return 0
        }
        if i == j - 1 {
            return s[i] != s[j] ? 1 : 0
        }
        if let res = memo[i][j] {
            return res
        }
        if s[i] == s[j] {
            memo[i][j] = isValidPalindromeHelper(s, i + 1, j - 1)
        } else {
            memo[i][j] = 1 + min(isValidPalindromeHelper(s, i + 1, j), isValidPalindromeHelper(s, i, j - 1))
        }
        return memo[i][j]!
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 986. Interval List Intersections
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

👨‍💻 Алгоритм:

1⃣Инициализация указателей:
Завести два указателя i и j, указывающие на начало firstList и secondList соответственно.

2⃣Поиск пересечений:
Пока оба указателя находятся в пределах своих списков, выполнить следующие действия:
Найти максимальное начало и минимальный конец текущих интервалов.
Если начало меньше или равно концу, добавить пересечение в результат.
Сдвинуть указатель списка, у которого текущий интервал заканчивается раньше.

3⃣Возврат результата:
Вернуть список пересечений.

😎 Решение:

func intervalIntersection(_ firstList: [[Int]], _ secondList: [[Int]]) -> [[Int]] {
    var i = 0, j = 0
    var result = [[Int]]()

    while i < firstList.count && j < secondList.count {
        let start = max(firstList[i][0], secondList[j][0])
        let end = min(firstList[i][1], secondList[j][1])
        
        if start <= end {
            result.append([start, end])
        }
        
        if firstList[i][1] < secondList[j][1] {
            i += 1
        } else {
            j += 1
        }
    }
    
    return result
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

Вам дан массив целых чисел nums.

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов.

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

👨‍💻 Алгоритм:

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

2⃣Итерация по первым четырем элементам отсортированного массива: для каждого индекса left от 0 до 3 вычислите соответствующий правый индекс, разницу между элементами на этих индексах и обновите minDiff с минимальным значением.

3⃣Верните minDiff, которое хранит минимальную разницу между наибольшими и наименьшими значениями после удаления до трех элементов.

😎 Решение

class Solution {
    func minDifference(_ nums: [Int]) -> Int {
        let numsSize = nums.count
        
        if numsSize <= 4 { return 0 }
        
        let sortedNums = nums.sorted()
        
        var minDiff = Int.max
        
        for left in 0..<4 {
            let right = numsSize - 4 + left
            minDiff = min(minDiff, sortedNums[right] - sortedNums[left])
        }
        
        return minDiff
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1020. Number of Enclaves
Сложности: medium

Вам дана двоичная матричная сетка m x n, где 0 обозначает морскую ячейку, а 1 - сухопутную. Ход состоит из перехода от одной сухопутной ячейки к другой соседней (в 4-х направлениях) или выхода за границу сетки. Верните количество сухопутных ячеек в сетке, для которых мы не можем выйти за границу сетки за любое количество ходов.

Пример:

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3

👨‍💻 Алгоритм:

1⃣Обработка граничных сухопутных ячеек:
Пройдитесь по всем ячейкам, которые находятся на границе сетки (первый и последний ряды, первый и последний столбцы). Если ячейка содержит 1, начните поиск в глубину (DFS) или поиск в ширину (BFS), чтобы пометить все достижимые из нее сухопутные ячейки как посещенные.

2⃣Проверка всех ячеек:
Пройдите по всем ячейкам матрицы, считая количество сухопутных ячеек, которые не были посещены в предыдущем шаге.

3⃣Возврат результата:
Верните количество не посещенных сухопутных ячеек.

😎 Решение:

class Solution {
    func numEnclaves(_ grid: [[Int]]) -> Int {
        var grid = grid
        let m = grid.count
        let n = grid[0].count
        
        func dfs(_ x: Int, _ y: Int) {
            if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1 {
                return
            }
            grid[x][y] = 0
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        }
        
        for i in 0..<m {
            if grid[i][0] == 1 {
                dfs(i, 0)
            }
            if grid[i][n - 1] == 1 {
                dfs(i, n - 1)
            }
        }
        
        for j in 0..<n {
            if grid[0][j] == 1 {
                dfs(0, j)
            }
            if grid[m - 1][j] == 1 {
                dfs(m - 1, j)
            }
        }
        
        var count = 0
        for i in 0..<m {
            for j in 0..<n {
                if grid[i][j] == 1 {
                    count += 1
                }
            }
        }
        
        return count
    }
}

Ставь 👍 и забирай 📚 Базу знаний