Swift | LeetCode

Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard

Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.

Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами:

Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение.
В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше.
Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты.

Пример:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

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

1⃣Инициализируйте переменные: n для размера массивов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте массив wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию.

2⃣Создайте приоритетную очередь workers (максимальная куча) для хранения выбранных работников. Итерируйте через отсортированный wageToQualityRatio: добавляйте качество текущего работника в workers и обновляйте currentTotalQuality.

3⃣Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. Верните totalCost.

😎 Решение:

class Solution {
    func mincostToHireWorkers(_ quality: [Int], _ wage: [Int], _ k: Int) -> Double {
        let n = quality.count
        var totalCost = Double.greatestFiniteMagnitude
        var currentTotalQuality = 0.0
        var wageToQualityRatio = [(Double, Int)]()

        for i in 0..<n {
            wageToQualityRatio.append((Double(wage[i]) / Double(quality[i]), quality[i]))
        }

        wageToQualityRatio.sort { $0.0 < $1.0 }
        var workers = PriorityQueue<Int>(sort: >)

        for ratio in wageToQualityRatio {
            workers.enqueue(ratio.1)
            currentTotalQuality += Double(ratio.1)

            if workers.count > k {
                currentTotalQuality -= Double(workers.dequeue()!)
            }

            if workers.count == k {
                totalCost = min(totalCost, currentTotalQuality * ratio.0)
            }
        }
        return totalCost
    }
}

struct PriorityQueue<Element: Comparable> {
    private var elements: [Element] = []
    private let sort: (Element, Element) -> Bool

    init(sort: @escaping (Element, Element) -> Bool) {
        self.sort = sort
    }

    var count: Int {
        return elements.count
    }

    mutating func enqueue(_ element: Element) {
        elements.append(element)
        elements.sort(by: sort)
    }

    mutating func dequeue() -> Element? {
        return elements.isEmpty ? nil : elements.removeFirst()
    }
}

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

Задача: 384. Shuffle an Array
Сложность: medium

Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.

Реализуйте класс Solution:

Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.

2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.

3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие.

😎 Решение:

class Solution {
    private var array: [Int]
    private let original: [Int]

    init(_ nums: [Int]) {
        self.array = nums
        self.original = nums
    }

    func reset() -> [Int] {
        self.array = self.original
        return self.original
    }

    func shuffle() -> [Int] {
        for i in 0..<array.count {
            let randIndex = Int.random(in: i..<array.count)
            array.swapAt(i, randIndex)
        }
        return array
    }
}

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

Задача: 662. Maximum Width of Binary Tree
Сложность: medium

Дан корень бинарного дерева, верните максимальную ширину данного дерева.

Максимальная ширина дерева - это максимальная ширина среди всех уровней.

Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.

Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

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

1⃣Инициализация:
Создайте очередь для хранения узлов и их позиций на уровне.
Начните с корневого узла и его позиции 0.

2⃣Обработка каждого уровня:
Для каждого уровня дерева получите его узлы и их позиции.
Вычислите ширину уровня как разницу между максимальной и минимальной позициями плюс один.

3⃣Обновление максимальной ширины:
Обновите максимальную ширину, если текущая ширина уровня больше.

😎 Решение:

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

class Solution {
    func widthOfBinaryTree(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        
        var maxWidth = 0
        var queue: [(TreeNode, Int)] = [(root, 0)]
        
        while !queue.isEmpty {
            let levelSize = queue.count
            let firstPos = queue.first!.1
            for _ in 0..<levelSize {
                let (node, pos) = queue.removeFirst()
                if let left = node.left {
                    queue.append((left, 2 * pos))
                }
                if let right = node.right {
                    queue.append((right, 2 * pos + 1))
                }
                if node === queue.last?.0 {
                    maxWidth = max(maxWidth, pos - firstPos + 1)
                }
            }
        }
        
        return maxWidth
    }
}

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

Задача: 897. Increasing Order Search Tree
Сложность: easy

Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

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

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

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

func increasingBST(_ root: TreeNode?) -> TreeNode? {
    var nodes: [TreeNode] = []
    
    func inorder(_ node: TreeNode?) {
        guard let node = node else { return }
        inorder(node.left)
        nodes.append(node)
        inorder(node.right)
    }
    
    inorder(root)
    
    for i in 0..<nodes.count - 1 {
        nodes[i].left = nil
        nodes[i].right = nodes[i + 1]
    }
    
    nodes.last?.left = nil
    nodes.last?.right = nil
    return nodes.first
}

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

Задача: 642. Design Search Autocomplete System
Сложность: hard

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди.

2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.

3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class TrieNode {
    var children = [Character: TrieNode]()
    var count = [String: Int]()
}

class AutocompleteSystem {
    private var root = TrieNode()
    private var prefix = ""

    init(_ sentences: [String], _ times: [Int]) {
        for i in 0..<sentences.count {
            add(sentences[i], times[i])
        }
    }

    private func add(_ sentence: String, _ count: Int) {
        var node = root
        for char in sentence {
            if node.children[char] == nil {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!
            node.count[sentence, default: 0] += count
        }
    }

    func input(_ c: Character) -> [String] {
        if c == "#" {
            add(prefix, 1)
            prefix = ""
            return []
        }

        prefix.append(c)
        var node = root
        for char in prefix {
            if node.children[char] == nil {
                return []
            }
            node = node.children[char]!
        }

        let pq = node.count.sorted { lhs, rhs in
            if lhs.value == rhs.value {
                return lhs.key < rhs.key
            }
            return lhs.value > rhs.value
        }

        return Array(pq.prefix(3)).map { $0.key }
    }
}

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

Задача: 521. Longest Uncommon Subsequence I
Сложность: easy

Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1.

Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них.

Пример:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

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

1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности.

2⃣В противном случае: Вычислите длины строк a и b.

3⃣Верните длину более длинной строки.

😎 Решение:

class Solution {
    func findLUSlength(_ a: String, _ b: String) -> Int {
        if a == b {
            return -1
        } else {
            return max(a.count, b.count)
        }
    }
}

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

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

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

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.

3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.

😎 Решение:

class Solution {
    private let directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    
    func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
        if grid[0][0] != 0 || grid[grid.count - 1][grid[0].count - 1] != 0 {
            return -1
        }
        
        var grid = grid
        var queue: [(Int, Int)] = [(0, 0)]
        grid[0][0] = 1
        
        while !queue.isEmpty {
            let (row, col) = queue.removeFirst()
            let distance = grid[row][col]
            if row == grid.count - 1 && col == grid[0].count - 1 {
                return distance
            }
            for direction in directions {
                let newRow = row + direction.0
                let newCol = col + direction.1
                if newRow >= 0 && newCol >= 0 && newRow < grid.count && newCol < grid[0].count && grid[newRow][newCol] == 0 {
                    queue.append((newRow, newCol))
                    grid[newRow][newCol] = distance + 1
                }
            }
        }
        return -1
    }
}

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

Задача: 583. Delete Operation for Two Strings
Сложность: medium

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.

На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

1⃣ Инициализация массива:
Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.

2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

3⃣ Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎 Решение:

class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let m = word1.count, n = word2.count
        var dp = [Int](repeating: 0, count: n + 1)
        let s1 = Array(word1), s2 = Array(word2)

        for i in 0...m {
            var temp = [Int](repeating: 0, count: n + 1)
            for j in 0...n {
                if i == 0 || j == 0 {
                    temp[j] = i + j
                } else if s1[i - 1] == s2[j - 1] {
                    temp[j] = dp[j - 1]
                } else {
                    temp[j] = 1 + min(dp[j], temp[j - 1])
                }
            }
            dp = temp
        }
        return dp[n]
    }
}

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

Задача: 1328. Break a Palindrome
Сложность: medium

Дана палиндромная строка из строчных английских букв palindrome. Замените ровно один символ на любую строчную английскую букву так, чтобы результирующая строка не была палиндромом и чтобы она была лексикографически наименьшей из возможных.

Верните получившуюся строку. Если нет способа заменить символ, чтобы строка перестала быть палиндромом, верните пустую строку.

Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'.

Пример:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

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

1⃣Если длина строки равна 1, верните пустую строку, так как невозможно создать непалиндромическую строку в этом случае.

2⃣Итерируйтесь по строке слева до середины строки: если символ не равен 'a', измените его на 'a' и верните строку.

3⃣Если вы прошли всю левую часть строки и все еще не получили непалиндромическую строку, это означает, что строка состоит только из 'a'. Следовательно, измените последний символ на 'b' и верните полученную строку.

😎 Решение

class Solution {
    func breakPalindrome(_ palindrome: String) -> String {
        var palindromeArray = Array(palindrome)
        let length = palindromeArray.count
        
        if length == 1 {
            return ""
        }
        
        for i in 0..<length / 2 {
            if palindromeArray[i] != "a" {
                palindromeArray[i] = "a"
                return String(palindromeArray)
            }
        }
        
        palindromeArray[length - 1] = "b"
        return String(palindromeArray)
    }
}

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

Задача: 717. 1-bit and 2-bit Characters
Сложность: easy

У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.

Пример:

Input: bits = [1,0,0]
Output: true

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

1⃣Инициализируйте индекс для итерации по массиву.

2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1.

3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат.

😎 Решение:

func isOneBitCharacter(_ bits: [Int]) -> Bool {
    var i = 0
    while i < bits.count - 1 {
        i += bits[i] + 1
    }
    return i == bits.count - 1
}

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

Задача: 435. Non-overlapping Intervals
Сложность: medium

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

1⃣Отсортируйте интервалы по времени окончания.

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

class Solution {
    func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
        let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
        var ans = 0
        var k = Int.min
        
        for interval in sortedIntervals {
            let x = interval[0]
            let y = interval[1]
            if x >= k {
                k = y
            } else {
                ans += 1
            }
        }
        
        return ans
    }
}

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

Задача: 245. Shortest Word Distance II
Сложность: medium

Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.

Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

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

1⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.

2⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.

3⃣Верните значение переменной shortestDistance.

😎 Решение:

class Solution {
    func shortestWordDistance(_ wordsDict: [String], _ word1: String, _ word2: String) -> Int {
        var indices1 = [Int]()
        var indices2 = [Int]()
        for (i, word) in wordsDict.enumerated() {
            if word == word1 {
                indices1.append(i)
            }
            if word == word2 {
                indices2.append(i)
            }
        }

        var shortestDistance = Int.max
        for index in indices1 {
            let x = indices2.partitioningIndex(where: { $0 > index })
            if x < indices2.count {
                shortestDistance = min(shortestDistance, indices2[x] - index)
            }
            if x > 0 && indices2[x - 1] != index {
                shortestDistance = min(shortestDistance, index - indices2[x - 1])
            }
        }
        return shortestDistance
    }
}

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

Задача: 567. Permutation in String
Сложность: medium

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        let s1Len = s1.count, s2Len = s2.count
        if s1Len > s2Len { return false }
        
        let s1Arr = Array(s1), s2Arr = Array(s2)
        var s1Count = [Int](repeating: 0, count: 26)
        var s2Count = [Int](repeating: 0, count: 26)
        
        for i in 0..<s1Len {
            s1Count[Int(s1Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
            s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
        }
        
        for i in 0..<(s2Len - s1Len) {
            if s1Count == s2Count { return true }
            s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] -= 1
            s2Count[Int(s2Arr[i + s1Len].asciiValue! - Character("a").asciiValue!)] += 1
        }
        
        return s1Count == s2Count
    }
}

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

Задача: 442. Find All Duplicates in an Array
Сложность: medium

Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.

Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.

Пример:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

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

1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива.

2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет).

3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива.

😎 Решение:

class Solution {
    func findDuplicates(_ nums: [Int]) -> [Int] {
        var ans = [Int]()
        
        for i in 0..<nums.count {
            for j in (i+1)..<nums.count {
                if nums[j] == nums[i] {
                    ans.append(nums[i])
                    break
                }
            }
        }
        
        return ans
    }
}

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

Задача: 946. Validate Stack Sequences
Сложность: medium

Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

1⃣Инициализировать пустой стек.
Использовать указатель j для отслеживания текущей позиции в массиве popped.

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

class Solution {
    func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
        var stack = [Int]()
        var j = 0
        for x in pushed {
            stack.append(x)
            while !stack.isEmpty && j < popped.count && stack.last == popped[j] {
                stack.removeLast()
                j += 1
            }
        }
        return j == popped.count
    }
}

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

Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium

У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.

Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

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

1⃣Начните с:
Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент.
Сумма чисел на предыдущих кубиках currSum равна 0.
Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию.

2⃣Базовые случаи:
Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target.

3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum.

😎 Решение

class Solution {
    let MOD = 1_000_000_007
    
    func waysToTarget(_ memo: inout [[Int]], _ diceIndex: Int, _ n: Int, _ currSum: Int, _ target: Int, _ k: Int) -> Int {
        if diceIndex == n {
            return currSum == target ? 1 : 0
        }
        
        if memo[diceIndex][currSum] != -1 {
            return memo[diceIndex][currSum]
        }
        
        var ways = 0
        for i in 1...min(k, target - currSum) {
            ways = (ways + waysToTarget(&memo, diceIndex + 1, n, currSum + i, target, k)) % MOD
        }
        memo[diceIndex][currSum] = ways
        return ways
    }
    
    func numRollsToTarget(_ n: Int, _ k: Int, _ target: Int) -> Int {
        var memo = Array(repeating: Array(repeating: -1, count: target + 1), count: n + 1)
        return waysToTarget(&memo, 0, n, 0, target, k)
    }
}

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

Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

Задача: 434. Number of Segments in a String
Сложность: easy

Дана строка s, верните количество сегментов в строке.

Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.

Пример:

Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

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

1⃣Инициализируйте счетчик сегментов segment_count равным 0.

2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count.

3⃣Верните segment_count.

😎 Решение:

class Solution {
    func countSegments(_ s: String) -> Int {
        var segmentCount = 0
        let chars = Array(s)
        
        for i in 0..<chars.count {
            if (i == 0 || chars[i - 1] == " ") && chars[i] != " " {
                segmentCount += 1
            }
        }
        
        return segmentCount
    }
}

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

Задача: 316. Remove Duplicate Letters
Сложность: medium

Дана строка s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.

Пример:

Input: s = "bcabc"
Output: "abc"

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

1⃣Инициализация стека
Создайте стек, который будет хранить результат, построенный по мере итерации строки.

2⃣Итерация по строке
На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок.

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

😎 Решение:

class Solution {
    func removeDuplicateLetters(_ s: String) -> String {
        var stack = [Character]()
        var seen = Set<Character>()
        let lastOccurrence = Dictionary(uniqueKeysWithValues: s.enumerated().map { ($1, $0) })

        for (i, c) in s.enumerated() {
            if !seen.contains(c) {
                while let last = stack.last, c < last, i < lastOccurrence[last]! {
                    seen.remove(stack.popLast()!)
                }
                seen.insert(c)
                stack.append(c)
            }
        }
        return String(stack)
    }
}

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

Задача: 496. Next Greater Element I
Сложность: easy

Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.

Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.

Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.

Пример:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

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

1⃣Инициализация и поиск совпадений
Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2.

2⃣Поиск следующего большего элемента
После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res.

3⃣Заполнение результата
Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res.

😎 Решение:

class Solution {
    func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var res = [Int](repeating: -1, count: nums1.count)
        
        for i in 0..<nums1.count {
            var found = false
            for j in 0..<nums2.count {
                if nums2[j] == nums1[i] {
                    found = true
                }
                if found && nums2[j] > nums1[i] {
                    res[i] = nums2[j]
                    break
                }
            }
        }
        
        return res
    }
}

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