Задача: 405. Convert a Number to Hexadecimal
Сложность: easy

Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи.

Пример:

Input: num = 26
Output: "1a"

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

1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF.

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

3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0".

😎 Решение:

func toHex(_ num: Int) -> String {
    if num == 0 {
        return "0"
    }
    let hexChars = "0123456789abcdef"
    var num = num
    if num < 0 {
        num += 1 << 32
    }
    var result = ""
    while num > 0 {
        result.append(hexChars[hexChars.index(hexChars.startIndex, offsetBy: num % 16)])
        num /= 16
    }
    return String(result.reversed())
}

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

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

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

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

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

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

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

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

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

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

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

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

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