Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
Сложность: hard

Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:

maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
      if (maximum_value  < arr[i]){
           maximum_value  = arr[i]
           maximum_index = i
           search_cost = search_cost + 1
      }
}
return maximum_index

Вам необходимо построить массив arr, который имеет следующие свойства:
arr содержит ровно n целых чисел.
1 <= arr[i] <= m, где (0 <= i < n).
После применения указанного алгоритма к arr, значение search_cost равно k.
Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7.

Пример:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

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

1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1.

2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений.

3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи.

😎 Решение:

class Solution {
    func numOfArrays(_ n: Int, _ m: Int, _ k: Int) -> Int {
        let MOD = 1_000_000_007
        var dp = Array(repeating: Array(repeating: Array(repeating: 0, count: k + 1), count: m + 1), count: n + 1)
        
        for num in 0...m {
            dp[n][num][0] = 1
        }
        
        for i in stride(from: n - 1, through: 0, by: -1) {
            for maxSoFar in stride(from: m, through: 0, by: -1) {
                for remain in 0...k {
                    var ans = 0
                    for num in 1...maxSoFar {
                        ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD
                    }
                    
                    if remain > 0 {
                        for num in (maxSoFar + 1)...m {
                            ans = (ans + dp[i + 1][num][remain - 1]) % MOD
                        }
                    }
                    
                    dp[i][maxSoFar][remain] = ans
                }
            }
        }
        
        return dp[0][0][k]
    }
}

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

Задача: 465. Optimal Account Balancing
Сложность: medium

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

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

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

class Solution {
    var creditList = [Int]()
    
    func minTransfers(_ transactions: [[Int]]) -> Int {
        var creditMap = [Int: Int]()
        for t in transactions {
            creditMap[t[0], default: 0] += t[2]
            creditMap[t[1], default: 0] -= t[2]
        }
        
        for amount in creditMap.values {
            if amount != 0 {
                creditList.append(amount)
            }
        }
        
        let n = creditList.count
        return dfs(0, n)
    }
    
    private func dfs(_ cur: Int, _ n: Int) -> Int {
        var cur = cur
        while cur < n && creditList[cur] == 0 {
            cur += 1
        }
        
        if cur == n {
            return 0
        }
        
        var cost = Int.max
        for nxt in cur+1..<n {
            if creditList[nxt] * creditList[cur] < 0 {
                creditList[nxt] += creditList[cur]
                cost = min(cost, 1 + dfs(cur + 1, n))
                creditList[nxt] -= creditList[cur]
            }
        }
        
        return cost
    }
}

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        var x = abs(a), y = abs(b)
        if x < y {
            return getSum(b, a)
        }
        let sign = a > 0 ? 1 : -1

        if a * b >= 0 {
            while y != 0 {
                let carry = (x & y) << 1
                x ^= y
                y = carry
            }
        } else {
            while y != 0 {
                let borrow = ((~x) & y) << 1
                x ^= y
                y = borrow
            }
        }
        return x * sign
    }
}

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

Задача: 907. Sum of Subarray Minimums
Сложность: medium

Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.

Пример:

Input: arr = [3,1,2,4]
Output: 17

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

1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива.

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

3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.

😎 Решение:

class Solution {
    func sumSubarrayMins(_ arr: [Int]) -> Int {
        let MOD = 1_000_000_007
        let n = arr.count
        var left = [Int](repeating: 0, count: n)
        var right = [Int](repeating: 0, count: n)
        var stack = [Int]()
        
        for i in 0..<n {
            while !stack.isEmpty && arr[stack.last!] > arr[i] {
                stack.removeLast()
            }
            left[i] = stack.isEmpty ? i + 1 : i - stack.last!
            stack.append(i)
        }
        
        stack = []
        
        for i in stride(from: n - 1, through: 0, by: -1) {
            while !stack.isEmpty && arr[stack.last!] >= arr[i] {
                stack.removeLast()
            }
            right[i] = stack.isEmpty ? n - i : stack.last! - i
            stack.append(i)
        }
        
        var result = 0
        for i in 0..<n {
            result = (result + arr[i] * left[i] * right[i]) % MOD
        }
        
        return result
    }
}

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

Задача: 641. Design Circular Deque
Сложность: medium

Разработайте свою реализацию круговой двусторонней очереди (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 MyCircularDeque {
    private var deque: [Int]
    private var front: Int
    private var rear: Int
    private var size: Int
    private var capacity: Int

    init(_ k: Int) {
        self.capacity = k
        self.deque = [Int](repeating: 0, count: k)
        self.front = 0
        self.rear = 0
        self.size = 0
    }

    func insertFront(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        front = (front - 1 + capacity) % capacity
        deque[front] = value
        size += 1
        return true
    }

    func insertLast(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        deque[rear] = value
        rear = (rear + 1) % capacity
        size += 1
        return true
    }

    func deleteFront() -> Bool {
        if isEmpty() {
            return false
        }
        front = (front + 1) % capacity
        size -= 1
        return true
    }

    func deleteLast() -> Bool {
        if isEmpty() {
            return false
        }
        rear = (rear - 1 + capacity) % capacity
        size -= 1
        return true
    }

    func getFront() -> Int {
        if isEmpty() {
            return -1
        }
        return deque[front]
    }

    func getRear() -> Int {
        if isEmpty() {
            return -1
        }
        return deque[(rear - 1 + capacity) % capacity]
    }

    func isEmpty() -> Bool {
        return size == 0
    }

    func isFull() -> Bool {
        return size == capacity
    }
}

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

Задача: 1166. Design File System
Сложность: medium

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

Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.

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

- bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.
- int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.

Пример:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

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

1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции.

2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем.

3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение.

😎 Решение

class FileSystem {
    var paths: [String: Int]

    init() {
        self.paths = [String: Int]()
    }

    func createPath(_ path: String, _ value: Int) -> Bool {
        if path.isEmpty || (path.count == 1 && path == "/") || self.paths[path] != nil {
            return false
        }
        
        let delimIndex = path.lastIndex(of: "/")!
        let parent = String(path[..<delimIndex])
        
        if parent.count > 1 && self.paths[parent] == nil {
            return false
        }
        
        self.paths[path] = value
        return true
    }

    func get(_ path: String) -> Int {
        return self.paths[path] ?? -1
    }
}

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

Задача: 334. Increasing Triplet Subsequence
Сложность: medium

Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.

Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

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

1⃣Инициализация переменных:
Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки.

2⃣Итерация по массиву:
Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки:
- если текущий элемент меньше или равен first_num, обновите first_num текущим элементом.
- иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом.
- иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true.

3⃣Возврат результата:
Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false.

😎 Решение:

class Solution {
    func increasingTriplet(_ nums: [Int]) -> Bool {
        var firstNum = Int.max
        var secondNum = Int.max
        
        for n in nums {
            if n <= firstNum {
                firstNum = n
            } else if n <= secondNum {
                secondNum = n
            } else {
                return true
            }
        }
        return false
    }
}

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

Задача: 527. Word Abbreviation
Сложность: hard

Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.

Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.

Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

1⃣ Инициализация и создание начальных сокращений:
Создайте массив для хранения сокращений и массив для отслеживания длины префикса каждого слова.
Для каждого слова создайте начальное сокращение с использованием первого символа, количества символов между первым и последним символом и последнего символа.

2⃣ Обработка коллизий:
Для каждого слова проверьте, не совпадает ли его сокращение с уже существующими сокращениями.
Если сокращение не уникально, увеличьте длину префикса и повторите проверку.

3⃣ Возврат результата:
Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны.

😎 Решение:

class Solution {
    func wordsAbbreviation(_ words: [String]) -> [String] {
        let n = words.count
        var ans = Array(repeating: "", count: n)
        var prefix = Array(repeating: 0, count: n)

        for i in 0..<n {
            ans[i] = abbrev(words[i], 0)
        }

        for i in 0..<n {
            while true {
                var dupes = Set<Int>()
                for j in (i+1)..<n {
                    if ans[i] == ans[j] {
                        dupes.insert(j)
                    }
                }

                if dupes.isEmpty { break }
                dupes.insert(i)
                for k in dupes {
                    ans[k] = abbrev(words[k], prefix[k] + 1)
                    prefix[k] += 1
                }
            }
        }

        return ans
    }

    private func abbrev(_ word: String, _ i: Int) -> String {
        let n = word.count
        if n - i <= 3 { return word }
        let start = word.prefix(i + 1)
        let end = word.suffix(1)
        return "\(start)\(n - i - 2)\(end)"
    }
}

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

Задача: 30. Substring with Concatenation of All Words
Сложность: hard

Вам дана строка s и массив строк words. Все строки в words имеют одинаковую длину.

Объединенная строка — это строка, которая в точности содержит все строки любой перестановки words.

Возвращает массив начальных индексов всех объединенных подстрок в s.

Пример:

Input: s = "barfoothefoobarman", words = ["foo","bar"]  
Output: [0,9]  

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

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

2⃣Создаем словарь wf с частотами слов в words.

3⃣Проходим по строке s, проверяя подстроки длиной cnt * len.

😎Решение:

class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        let len = words.first!.count
        let cnt = words.count

        guard s.count >= cnt * len else { return [] }
        
        let s = Array(s)
        let words = words.map(Array.init)
        let wf = words.reduce(into: [[Character]: Int]()) { $0[$1, default: 0] += 1 }
        let ws = Set(words)
        var res = [Int]()

        for i in 0...(s.count - cnt * len) {
            var sf = [[Character]: Int]()
            var j = i

            for _ in 0..<cnt {
                let w = Array(s[j..<j + len])
                guard ws.contains(w) else { break }

                let old = sf[w, default: 0]
                guard old + 1 <= wf[w]! else { break }

                sf[w] = old + 1
                j += len
            }

            guard j == i + cnt * len, sf == wf else { continue }
            res.append(i)
        }

        return res
    }
}

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