#hard
Задача: 726. Number of Atoms

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

2⃣Пройдите по строке формулы, анализируя каждый символ: Если символ - это открывающая скобка '(', создайте новый словарь для хранения атомов внутри скобок. Если символ - это закрывающая скобка ')', извлеките словарь из стека и умножьте количества атомов на последующее число, если оно присутствует. Если символ - это атом (начинается с заглавной буквы), извлеките имя атома и его количество, и добавьте его в текущий словарь.

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

import Foundation

func countOfAtoms(_ formula: String) -> String {
    var stack = [Dictionary<String, Int>]()
    stack.append(Dictionary<String, Int>())
    let formula = Array(formula)
    var i = 0
    let n = formula.count
    
    while i < n {
        if formula[i] == "(" {
            stack.append(Dictionary<String, Int>())
            i += 1
        } else if formula[i] == ")" {
            let top = stack.removeLast()
            i += 1
            var multiplicity = 0
            while i < n && formula[i].isNumber {
                multiplicity = multiplicity * 10 + Int(String(formula[i]))!
                i += 1
            }
            multiplicity = multiplicity == 0 ? 1 : multiplicity
            for (name, count) in top {
                stack[stack.count - 1][name, default: 0] += count * multiplicity
            }
        } else {
            var start = i
            i += 1
            while i < n && formula[i].isLowercase {
                i += 1
            }
            let name = String(formula[start..<i])
            start = i
            var multiplicity = 0
            while i < n && formula[i].isNumber {
                multiplicity = multiplicity * 10 + Int(String(formula[i]))!
                i += 1
            }
            multiplicity = multiplicity == 0 ? 1 : multiplicity
            stack[stack.count - 1][name, default: 0] += multiplicity
        }
    }
    
    let last = stack.removeLast()
    var result = ""
    for key in last.keys.sorted() {
        result += key
        if last[key]! > 1 {
            result += "\(last[key]!)"
        }
    }
    return result
}

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

#hard
Задача: 727. Minimum Window Subsequence

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

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

2⃣Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.

3⃣Перемещайте правый указатель, чтобы найти подходящее окно, и левый указатель, чтобы минимизировать его.

😎 Решение:

func minWindow(_ s1: String, _ s2: String) -> String {
    if s1.isEmpty || s2.isEmpty {
        return ""
    }

    var dictT = [Character: Int]()
    for char in s2 {
        dictT[char, default: 0] += 1
    }

    let required = dictT.count
    var l = 0, r = 0, formed = 0
    var windowCounts = [Character: Int]()
    var ans = (length: Int.max, start: 0, end: 0)
    let s1Array = Array(s1)

    while r < s1Array.count {
        let char = s1Array[r]
        windowCounts[char, default: 0] += 1

        if let count = dictT[char], windowCounts[char] == count {
            formed += 1
        }

        while l <= r && formed == required {
            let char = s1Array[l]

            if r - l + 1 < ans.length {
                ans = (r - l + 1, l, r)
            }

            windowCounts[char, default: 0] -= 1
            if let count = dictT[char], windowCounts[char]! < count {
                formed -= 1
            }

            l += 1
        }

        r += 1
    }

    return ans.length == Int.max ? "" : String(s1Array[ans.start...ans.end])
}

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

#hard
Задача: 728. Self Dividing Numbers

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

1⃣Переберите все числа в диапазоне от left до right.

2⃣Для каждого числа проверьте, является ли оно саморазделяющимся: Разделите число на его цифры. Убедитесь, что ни одна цифра не равна нулю и число делится на каждую из своих цифр без остатка.

3⃣Добавьте саморазделяющиеся числа в результативный список и верните его.

😎 Решение:

class Solution {
    func selfDividingNumbers(_ left: Int, _ right: Int) -> [Int] {
        func isSelfDividing(_ num: Int) -> Bool {
            var temp = num
            while temp > 0 {
                let digit = temp % 10
                if digit == 0 || num % digit != 0 {
                    return false
                }
                temp /= 10
            }
            return true
        }
        
        var result = [Int]()
        for num in left...right {
            if isSelfDividing(num) {
                result.append(num)
            }
        }
        return result
    }
}

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

#hard
Задача: 730. Count Different Palindromic Subsequences

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

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

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

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

func countPalindromicSubsequences(_ s: String) -> Int {
    let MOD = 1_000_000_007
    let n = s.count
    var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
    let sArray = Array(s)
    
    for i in 0..<n {
        dp[i][i] = 1
    }
    
    for length in 2...n {
        for i in 0...(n - length) {
            let j = i + length - 1
            if sArray[i] == sArray[j] {
                var l = i + 1
                var r = j - 1
                while l <= r && sArray[l] != sArray[i] {
                    l += 1
                }
                while l <= r && sArray[r] != sArray[j] {
                    r -= 1
                }
                if l > r {
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 2
                } else if l == r {
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 1
                } else {
                    dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1]
                }
            } else {
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
            }
            dp[i][j] = (dp[i][j] + MOD) % MOD
        }
    }
    
    return dp[0][n - 1]
}

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

#hard
Задача: 732. My Calendar III

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

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

2⃣Для каждого нового события обновите словари начала и конца событий.

3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎 Решение:

class MyCalendarThree {
    private var events: [Int: Int]
    
    init() {
        events = [:]
    }
    
    func book(_ startTime: Int, _ endTime: Int) -> Int {
        events[startTime, default: 0] += 1
        events[endTime, default: 0] -= 1
        
        var active = 0
        var maxActive = 0
        for time in events.keys.sorted() {
            active += events[time]!
            maxActive = max(maxActive, active)
        }
        
        return maxActive
    }
}

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

#hard
Задача: 736. Parse Lisp Expression

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

1⃣Определите функцию для оценки выражений.

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

3⃣Используйте словарь для отслеживания значений переменных с учетом области видимости.

😎 Решение:

class Solution {
    func evaluate(_ expression: String) -> Int {
        func evaluate(_ expression: String, _ env: inout [String: Int]) -> Int {
            if expression.first != "(" {
                if let val = Int(expression) {
                    return val
                }
                return env[expression]!
            }
            
            var tokens = tokenize(expression)
            if tokens[0] == "let" {
                for i in stride(from: 1, to: tokens.count - 2, by: 2) {
                    env[tokens[i]] = evaluate(tokens[i + 1], &env)
                }
                return evaluate(tokens.last!, &env)
            } else if tokens[0] == "add" {
                return evaluate(tokens[1], &env) + evaluate(tokens[2], &env)
            } else if tokens[0] == "mult" {
                return evaluate(tokens[1], &env) * evaluate(tokens[2], &env)
            }
            return 0
        }
        
        func tokenize(_ expression: String) -> [String] {
            var tokens: [String] = []
            var token: String = ""
            var parens: Int = 0
            for char in expression {
                if char == "(" {
                    parens += 1
                    if parens == 1 {
                        continue
                    }
                } else if char == ")" {
                    parens -= 1
                    if parens == 0 {
                        tokens.append(tokenize(token))
                        token = ""
                        continue
                    }
                } else if char == " " && parens == 1 {
                    if !token.isEmpty {
                        tokens.append(token)
                        token = ""
                    }
                    continue
                }
                token.append(char)
            }
            if !token.isEmpty {
                tokens.append(token)
            }
            return tokens
        }
        
        var env: [String: Int] = [:]
        return evaluate(expression, &env)
    }
}

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

#hard
Задача: 741. Cherry Pickup

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

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

😎 Решение:

func cherryPickup(_ grid: [[Int]]) -> Int {
    let n = grid.count
    var dp = Array(repeating: Array(repeating: Array(repeating: Int.min, count: n), count: n), count: n)
    dp[0][0][0] = grid[0][0]
    
    for k in 1...(2 * (n - 1)) {
        for i1 in max(0, k - n + 1)...min(n - 1, k) {
            for i2 in max(0, k - n + 1)...min(n - 1, k) {
                let j1 = k - i1
                let j2 = k - i2
                if j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1 {
                    var maxCherries = Int.min
                    if i1 > 0 && i2 > 0 { maxCherries = max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]) }
                    if i1 > 0 { maxCherries = max(maxCherries, dp[i1 - 1][i2][k - 1]) }
                    if i2 > 0 { maxCherries = max(maxCherries, dp[i1][i2 - 1][k - 1]) }
                    maxCherries = max(maxCherries, dp[i1][i2][k - 1])
                    if maxCherries != Int.min {
                        dp[i1][i2][k] = maxCherries + grid[i1][j1]
                        if i1 != i2 { dp[i1][i2][k] += grid[i2][j2] }
                    }
                }
            }
        }
    }
    
    return max(0, dp[n - 1][n - 1][2 * (n - 1)])
}

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

#hard
Задача: 745. Prefix and Suffix Search

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter {
    private var prefixSuffixMap = [String: Int]()
    
    init(_ words: [String]) {
        for (index, word) in words.enumerated() {
            let length = word.count
            for prefixLength in 1...length {
                for suffixLength in 1...length {
                    let prefix = String(word.prefix(prefixLength))
                    let suffix = String(word.suffix(suffixLength))
                    let key = prefix + "#" + suffix
                    prefixSuffixMap[key] = index
                }
            }
        }
    }
    
    func f(_ pref: String, _ suff: String) -> Int {
        let key = pref + "#" + suff
        return prefixSuffixMap[key, default: -1]
    }
}

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