Swift | LeetCode

Задача: 337. House Robber III Сложность: medium Вор снова нашел себе новое место для краж. В этом районе есть только один вход, который называется корнем. Кроме корня, каждый дом имеет только один родительский дом. После осмотра, умный вор понял, что все дома в этом месте образуют бинарное дерево. Полиция будет автоматически уведомлена, если два дома, напрямую связанные между собой, будут ограблены в одну ночь. Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию. Пример:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

👨‍💻 Алгоритм: 1⃣ Инициализация и базовый случай: Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел. Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0]. 2⃣ Рекурсивное исследование дерева: В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла. Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся. Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка. 3⃣ Возврат результата: В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper. 😎 Решение:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}

class Solution {
    func rob(_ root: TreeNode?) -> Int {
        let answer = helper(root)
        return max(answer[0], answer[1])
    }
    
    func helper(_ node: TreeNode?) -> [Int] {
        if node == nil {
            return [0, 0]
        }
        let left = helper(node?.left)
        let right = helper(node?.right)
        let rob = node!.val + left[1] + right[1]
        let notRob = max(left[0], left[1]) + max(right[0], right[1])
        return [rob, notRob]
    }
}

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

Задача: 186. Reverse Words in a String II Сложность: medium Дан массив символов s, переверните порядок слов. Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом. Ваш код должен решать задачу на месте, то есть без выделения дополнительного пространства. Пример:

Input: s = ["a"]
Output: ["a"]

👨‍💻 Алгоритм: 1⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца. 2⃣Перевернуть каждое слово: пройти по всей строке, идентифицировать границы каждого слова и использовать функцию reverse для переворачивания символов в пределах каждого слова. 3⃣Окончательная корректировка: проверить, чтобы между словами оставался только один пробел, и удалить лишние пробелы в начале и конце строки, если это необходимо. 😎 Решение:

class Solution {
    func reverseWords(_ s: inout [Character]) {
        s.reverse()
        var start = 0
        let n = s.count
        var end = 0

        while start < n {
            while end < n && s[end] != " " {
                end += 1
            }
            s[start..<end].reverse()
            end += 1
            start = end
        }
    }
}

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

Задача: 1295. Find Numbers with Even Number of Digits Сложность: easy Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр. Пример:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

👨‍💻 Алгоритм: 1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false. 2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0. 3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount. 😎 Решение:

class Solution {
    func hasEvenDigits(_ num: Int) -> Bool {
        var digitCount = 0
        var num = num
        while num > 0 {
            digitCount += 1
            num /= 10
        }
        return (digitCount & 1) == 0
    }

    func findNumbers(_ nums: [Int]) -> Int {
        var evenDigitCount = 0
        for num in nums {
            if hasEvenDigits(num) {
                evenDigitCount += 1
            }
        }
        return evenDigitCount
    }
}

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

Задача: 32. Longest Valid Parentheses Сложность: hard Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками. Пример:

Input: s = "(()"
Output: 2

👨‍💻 Алгоритм: 1⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека. 2⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной. 3⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки. 😎 Решение:

func isValid(_ s: String) -> Bool {
    var stack = [Character]()
    for char in s {
        if char == "(" {
            stack.append("(")
        } else if !stack.isEmpty && stack.last == "(" {
            stack.removeLast()
        } else {
            return false
        }
    }
    return stack.isEmpty
}

func longestValidParentheses(_ s: String) -> Int {
    var maxlen = 0
    for i in 0..<s.count {
        for j in stride(from: i + 2, through: s.count, by: 2) {
            let start = s.index(s.startIndex, offsetBy: i)
            let end = s.index(s.startIndex, offsetBy: j)
            let substring = String(s[start..<end])
            if isValid(substring) {
                maxlen = max(maxlen, j - i)
            }
        }
    }
    return maxlen
}

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

Задача: 1485. Clone Binary Tree With Random Pointer Сложность: medium Дано бинарное дерево, такое что каждый узел содержит дополнительный случайный указатель, который может указывать на любой узел в дереве или быть null. Верните глубокую копию дерева. Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где: - val: целое число, представляющее Node.val - random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел. Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами. Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

👨‍💻 Алгоритм: 1⃣Глубокое копирование дерева: Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева. Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень. 2⃣Сопоставление случайных указателей: Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs. 3⃣Возвращение клонированного дерева: Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень. 😎 Решение:

class Node {
    var val: Int
    var left: Node?
    var right: Node?
    var random: Node?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
        self.random = nil
    }
}

class NodeCopy {
    var val: Int
    var left: NodeCopy?
    var right: NodeCopy?
    var random: NodeCopy?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
        self.random = nil
    }
}

class Solution {
    private var newOldPairs = [Node: NodeCopy]()

    private func deepCopy(_ root: Node?) -> NodeCopy? {
        guard let root = root else { return nil }
        let newRoot = NodeCopy(root.val)
        newRoot.left = deepCopy(root.left)
        newRoot.right = deepCopy(root.right)
        newOldPairs[root] = newRoot
        return newRoot
    }

    private func mapRandomPointers(_ oldNode: Node?) {
        guard let oldNode = oldNode else { return }
        if let newNode = newOldPairs[oldNode] {
            newNode.random = newOldPairs[oldNode.random]
            mapRandomPointers(oldNode.left)
            mapRandomPointers(oldNode.right)
        }
    }

    func copyRandomBinaryTree(_ root: Node?) -> NodeCopy? {
        let newRoot = deepCopy(root)
        mapRandomPointers(root)
        return newRoot
    }
}

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

Задача: 1023. Camelcase Matching Сложность: medium Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа. Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив answer для хранения результатов соответствия каждого запроса шаблону. 2⃣Проверка каждого запроса: Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу. Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса. 3⃣Возврат результата: Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false. Верните массив answer. 😎 Решение:

class Solution {
    func camelMatch(_ queries: [String], _ pattern: String) -> [Bool] {
        func matches(_ query: String, _ pattern: String) -> Bool {
            var i = 0, j = 0
            let queryArray = Array(query), patternArray = Array(pattern)
            
            while i < queryArray.count {
                if j < patternArray.count && queryArray[i] == patternArray[j] {
                    j += 1
                } else if queryArray[i].isUppercase {
                    return false
                }
                i += 1
            }
            return j == patternArray.count
        }
        
        return queries.map { matches($0, pattern) }
    }
}

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

Зарплата 207.000р у Middle-разработчика в Яндекс «В день уходит несколько часов на созвоны, в остальное время закрываю задачки из спринта, редко перерабатываю. У компании топовый офис, но с коллективом как-то не заладилось. Радуюсь классному ДМС и стабильной зарплате» - middle разработчик из Яндекса. Бигтех по-русски - канал с реальными зарплатами и историями IT-специалистов российского БигТеха. Там уже опубликованы рассказы программистов Альфа-банка, Сбера и Тинькофф 🤯 Читайте: @bigtech_russia

Задача: 102. Binary Tree Level Order Traversal Сложность: medium Дан корень бинарного дерева. Верните обход узлов дерева по уровням (то есть слева направо, уровень за уровнем). Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

👨‍💻 Алгоритм: 1⃣Самый простой способ решения задачи — использование рекурсии. Сначала убедимся, что дерево не пустое, а затем рекурсивно вызовем функцию helper(node, level), которая принимает текущий узел и его уровень в качестве аргументов. 2⃣Эта функция выполняет следующее: Выходной список здесь называется levels, и, таким образом, текущий уровень — это просто длина этого списка len(levels). Сравниваем номер текущего уровня len(levels) с уровнем узла level. Если вы все еще на предыдущем уровне, добавьте новый, добавив новый список в levels. 3⃣Добавьте значение узла в последний список в levels. Рекурсивно обработайте дочерние узлы, если они не равны None: helper(node.left / node.right, level + 1). 😎 Решение:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        var levels: [[Int]] = []
        if root == nil {
            return levels
        }

        func helper(_ node: TreeNode?, _ level: Int) {
            guard let node = node else { return }
            if level == levels.count {
                levels.append([Int]())
            }

            levels[level].append(node.val)

            helper(node.left, level + 1)
            helper(node.right, level + 1)
        }

        helper(root, 0)
        return levels
    }
}

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

Задача: 345. Reverse Vowels of a String Сложность: easy Дана строка s, переверните только все гласные в строке и верните её. Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры. Пример:

Input: s = "hello"
Output: "holle"

👨‍💻 Алгоритм: 1⃣Инициализация указателей и гласных: Создайте набор гласных для быстрой проверки. Установите два указателя: один на начало строки (left), другой на конец строки (right). 2⃣Перестановка гласных: Пока левый указатель меньше правого, перемещайте указатели к центру, пока не найдёте гласные. Обменивайте найденные гласные и продолжайте сдвигать указатели. 3⃣Завершение работы: Когда указатели пересекутся, остановите процесс и верните строку. 😎 Решение:

class Solution {
    func reverseVowels(_ s: String) -> String {
        var s = Array(s)
        let vowels = Set("aeiouAEIOU")
        var left = 0, right = s.count - 1
        
        while left < right {
            if !vowels.contains(s[left]) {
                left += 1
            } else if !vowels.contains(s[right]) {
                right -= 1
            } else {
                s.swapAt(left, right)
                left += 1
                right -= 1
            }
        }
        
        return String(s)
    }
}

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

Telegram опубликовал список 8 самых быстрорастущих каналов для программистов: Only Python — Подборки приёмов и фич, о которых не рассказывают в курсах. Only Tech — Главные тренды и инсайды из мира технологий, маркетинга и интернет-культуры. Only Hack — Реальные кейсы кибератак, инструменты и методы защиты, которые используют хакеры. Only GitHub — Репозитории, которые решают реальные задачи. Скрипты, фреймворки и готовые решения Only IT — Без мнений и слухов — только факты и важные IT-события. Only Apple — Новые апдейты, утечки и фишки, которые Apple ещё не показала. Only GPT — Промпты, хаки и свежие инструменты, о которых молчат даже AI-каналы. Only Memes — Если ты когда-нибудь деплоил в пятницу вечером — ты поймешь Подписывайтесь и прокачивайте свои скиллы.

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 779. K-th Symbol in Grammar Сложность: medium Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10. Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110. Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк. Пример:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

👨‍💻 Алгоритм: 1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal. 2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal). 3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal). 😎 Решение:

class Solution {
    func depthFirstSearch(_ n: Int, _ k: Int, _ rootVal: Int) -> Int {
        if n == 1 {
            return rootVal
        }
        let totalNodes = 1 << (n - 1)
        if k > totalNodes / 2 {
            let nextRootVal = rootVal == 0 ? 1 : 0
            return depthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal)
        } else {
            let nextRootVal = rootVal == 0 ? 0 : 1
            return depthFirstSearch(n - 1, k, nextRootVal)
        }
    }

    func kthGrammar(_ n: Int, _ k: Int) -> Int {
        return depthFirstSearch(n, k, 0)
    }
}

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

Задача: 1266. Minimum Time Visiting All Points Сложность: easy На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение. Пример:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную для хранения минимального времени. 2⃣Последовательно проходите по всем точкам и вычисляйте минимальное время для перехода от текущей точки к следующей. 3⃣Суммируйте время переходов для получения общего минимального времени. 😎 Решение:

class Solution {
    func minTimeToVisitAllPoints(_ points: [[Int]]) -> Int {
        var time = 0
        for i in 0..<points.count - 1 {
            time += distance(points[i], points[i + 1])
        }
        return time
    }

    private func distance(_ p1: [Int], _ p2: [Int]) -> Int {
        return max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))
    }
}

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

Задача: 1474. Delete N Nodes After M Nodes of a Linked List Сложность: easy Вам дано начало связанного списка и два целых числа m и n. Пройдите по связанному списку и удалите некоторые узлы следующим образом: Начните с головы как текущего узла. Сохраните первые m узлов, начиная с текущего узла. Удалите следующие n узлов. Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка. Верните голову изменённого списка после удаления указанных узлов. Пример:

Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List  (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.

👨‍💻 Алгоритм: 1⃣Инициализация указателей: Инициализируйте currentNode на голову связанного списка. Этот указатель будет использоваться для линейного прохода по каждому узлу списка. Инициализируйте lastMNode на голову связанного списка. 2⃣Итерация по списку: Итеративно удаляйте n узлов после m узлов, продолжая до конца списка. Проходите m узлов, обновляя lastMNode на текущий узел. После m итераций lastMNode указывает на m-й узел. Продолжайте итерацию по n узлам. 3⃣Удаление узлов: Чтобы удалить n узлов, измените указатель next у lastMNode, чтобы он указывал на currentNode после пропуска n узлов. 😎 Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class Solution {
    func deleteNodes(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
        var currentNode = head
        var lastMNode = head

        while currentNode != nil {
            var mCount = m
            var nCount = n

            while currentNode != nil && mCount > 0 {
                lastMNode = currentNode
                currentNode = currentNode?.next
                mCount -= 1
            }

            while currentNode != nil && nCount > 0 {
                currentNode = currentNode?.next
                nCount -= 1
            }

            lastMNode?.next = currentNode
        }
        return head
    }
}

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

Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed Сложность: hard RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента. Реализуйте класс RandomizedCollection: RandomizedCollection(): Инициализирует пустой объект RandomizedCollection. bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае. bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них. int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество. Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени. Пример:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

👨‍💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества. 2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае. Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента. 😎 Решение:

class RandomizedCollection {
    private var dict: [Int: Set<Int>]
    private var list: [Int]

    init() {
        dict = [Int: Set<Int>]()
        list = [Int]()
    }

    func insert(_ val: Int) -> Bool {
        let exists = dict[val] != nil
        if !exists {
            dict[val] = Set<Int>()
        }
        dict[val]?.insert(list.count)
        list.append(val)
        return !exists
    }

    func remove(_ val: Int) -> Bool {
        guard let indices = dict[val], !indices.isEmpty else {
            return false
        }
        let index = indices.first!
        dict[val]?.remove(index)
        let lastElement = list.removeLast()
        if index < list.count {
            list[index] = lastElement
            dict[lastElement]?.remove(list.count)
            dict[lastElement]?.insert(index)
        }
        if dict[val]?.isEmpty ?? false {
            dict[val] = nil
        }
        return true
    }

    func getRandom() -> Int {
        return list.randomElement()!
    }
}

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

Задача: 322. Coin Change Сложность: medium Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег. Верните минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, верните -1. Вы можете предположить, что у вас есть неограниченное количество монет каждого типа. Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

👨‍💻 Алгоритм: 1⃣Инициализация и вызов функции backtracking Инициализируйте переменные для хранения минимального количества монет и вызовите функцию backtracking с начальными параметрами. 2⃣Функция backtracking Внутри функции backtracking для каждой монеты из массива coins: Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет. 3⃣Возврат результата Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1. 😎 Решение:

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        return coinChange(0, coins, amount)
    }

    private func coinChange(_ idxCoin: Int, _ coins: [Int], _ amount: Int) -> Int {
        if amount == 0 {
            return 0
        }
        if idxCoin < coins.count && amount > 0 {
            let maxVal = amount / coins[idxCoin]
            var minCost = Int.max
            for x in 0...maxVal {
                if amount >= x * coins[idxCoin] {
                    let res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin])
                    if res != -1 {
                        minCost = min(minCost, res + x)
                    }
                }
            }
            return minCost == Int.max ? -1 : minCost
        }
        return -1
    }
}

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

Задача: 218. The Skyline Problem Сложность: hard Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности. Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]: lefti — это координата x левого края i-го здания. righti — это координата x правого края i-го здания. heighti — это высота i-го здания. Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0. Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

👨‍💻 Алгоритм: 1⃣Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights. 2⃣Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex). 3⃣Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат. 😎 Решение:

class Solution {
    func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
        var edgeSet = Set<Int>()
        for building in buildings {
            edgeSet.insert(building[0])
            edgeSet.insert(building[1])
        }
        let edges = Array(edgeSet).sorted()
        var edgeIndexMap = [Int: Int]()
        for i in 0..<edges.count {
            edgeIndexMap[edges[i]] = i
        }
        var heights = [Int](repeating: 0, count: edges.count)
        for building in buildings {
            let left = building[0], right = building[1], height = building[2]
            let leftIndex = edgeIndexMap[left]!, rightIndex = edgeIndexMap[right]!
            for idx in leftIndex..<rightIndex {
                heights[idx] = max(heights[idx], height)
            }
        }
        var answer = [[Int]]()
        for i in 0..<heights.count {
            let currHeight = heights[i], currPos = edges[i]
            if answer.isEmpty || answer.last![1] != currHeight {
                answer.append([currPos, currHeight])
            }
        }
        return answer
    }
}

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

"Ты че, дурак?" – базовая реакция сеньора на тех, кто покупает IT курсы Дело в том, что онлайн школы создают инкубаторных айтишников, которые в реальных условиях попросту зависнут. Трушные ребята учатся на жизненных каналах для айтишников. Вот топ-5 от тимлида из Сбера: ⚙️ Технолоджия – для тех, кто хочет быть в курсе новостей в айти 🧠 Ai-чница – способы превратить нейросети в заработок $$$ 💻 ИИ тебя заменит! – тенденции айти рынка в связке с нейросетями 4️⃣ Войти в IT – тонны бесплатного обучения для прогеров 😄 IT индус – сборник айти мемов

Задача: 914. X of a Kind in a Deck of Cards Сложность: easy Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае. Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

👨‍💻 Алгоритм: 1⃣Создать словарь для подсчета частоты каждого числа в массиве deck. 2⃣Найти наибольший общий делитель (НОД) всех частот. 3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы. 😎 Решение:

class Solution {
    func hasGroupsSizeX(_ deck: [Int]) -> Bool {
        let count = deck.reduce(into: [:]) { counts, num in
            counts[num, default: 0] += 1
        }
        let freqValues = Array(count.values)
        let g = freqValues.reduce(freqValues[0], gcd)
        return g > 1
    }
    
    private func gcd(_ a: Int, _ b: Int) -> Int {
        var a = a, b = b
        while b != 0 {
            let temp = a % b
            a = b
            b = temp
        }
        return a
    }
}

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

Айтишники, это вам — в телеграм есть комьюнити по каждому направлению в IT Там есть буквально всё: чаты для общения, тонны материала(книги, курсы, ресурсы и гайды), свежие новости и конечно же мемы Выбирайте своё направление: 💩 Frontend 🐍 Python 🐧 Linux 👩‍💻 С/С++ 👩‍💻 C# 🤔 Хакинг & ИБ 📱 GitHub 🖥 SQL 👩‍💻 Сисадмин 🤟 DevOps ⚙️ Backend 🖥 Data Science 🧑‍💻 Java 🐞 Тестирование 🖥 PM / PdM 👩‍💻 GameDev 🧑‍💻 Golang 🤵‍♂️ IT-Митапы 🧑‍💻 PHP 💻 WebDev 🖥 Моб. Dev 🖥Анали.(SA&BA) 👩‍💻 Дизайн 🖥 Нейросети 💛 1C 🤓 Книги IT ➡️ Сохраняйте в закладки