#hard
Задача: 499. The Maze III

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

Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).

Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

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

1⃣Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

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

3⃣Поиск кратчайшего пути
Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible".

😎 Решение:

class State: Comparable {
    var row: Int, col: Int, dist: Int
    var path: String
    init(_ r: Int, _ c: Int, _ d: Int, _ p: String) {
        row = r; col = c; dist = d; path = p
    }
    static func < (lhs: State, rhs: State) -> Bool {
        lhs.dist == rhs.dist ? lhs.path < rhs.path : lhs.dist < rhs.dist
    }
    static func == (lhs: State, rhs: State) -> Bool {
        lhs.row == rhs.row && lhs.col == rhs.col && lhs.dist == rhs.dist && lhs.path == rhs.path
    }
}

class Solution {
    let directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
    let textDirections = ["l", "u", "r", "d"]
    var m = 0, n = 0

    func findShortestWay(_ maze: [[Int]], _ ball: [Int], _ hole: [Int]) -> String {
        m = maze.count; n = maze[0].count
        var heap = [State(State(ball[0], ball[1], 0, ""))]
        var seen = Array(repeating: Array(repeating: false, count: n), count: m)
        
        while !heap.isEmpty {
            heap.sort(by: <)
            let curr = heap.removeFirst()
            if seen[curr.row][curr.col] { continue }
            if curr.row == hole[0] && curr.col == hole[1] { return curr.path }
            seen[curr.row][curr.col] = true
            
            for (dy, dx, direction) in zip(directions, textDirections, 0..<4) {
                var currRow = curr.row, currCol = curr.col, dist = 0
                while valid(currRow + dy, currCol + dx, maze) {
                    currRow += dy; currCol += dx; dist += 1
                    if currRow == hole[0] && currCol == hole[1] { break }
                }
                heap.append(State(currRow, currCol, curr.dist + dist, curr.path + direction))
            }
        }
        return "impossible"
    }

    func valid(_ row: Int, _ col: Int, _ maze: [[Int]]) -> Bool {
        row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == 0
    }
}

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

#hard
Задача: 502. IPO

Предположим, что LeetCode скоро начнет свое IPO. Чтобы продать свои акции по хорошей цене венчурным капиталистам, LeetCode хочет выполнить несколько проектов для увеличения своего капитала перед IPO. Поскольку у компании ограниченные ресурсы, она может завершить не более k различных проектов до IPO. Помогите LeetCode разработать лучший способ максимизации общего капитала после завершения не более k различных проектов.

Вам дано n проектов, где i-й проект имеет чистую прибыль profits[i] и требует минимального капитала capital[i] для его начала.

Изначально у вас есть капитал w. Когда вы завершаете проект, вы получаете его чистую прибыль, и эта прибыль добавляется к вашему общему капиталу.

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

Ответ гарантированно поместится в 32-битное целое число со знаком.

Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

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

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

2⃣Выбор проектов
Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм.

3⃣Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.

😎 Решение:

class Solution {
    func findMaximizedCapital(_ k: Int, _ w: Int, _ profits: [Int], _ capital: [Int]) -> Int {
        let projects = zip(capital, profits).sorted { $0.0 < $1.0 }
        var maxHeap = MaxHeap<Int>()
        var ptr = 0
        var w = w
        
        for _ in 0..<k {
            while ptr < projects.count && projects[ptr].0 <= w {
                maxHeap.insert(projects[ptr].1)
                ptr += 1
            }
            if maxHeap.isEmpty { break }
            w += maxHeap.remove()
        }
        
        return w
    }
}

struct MaxHeap<T: Comparable> {
    private var heap = [T]()
    var isEmpty: Bool { heap.isEmpty }
    
    mutating func insert(_ value: T) {
        heap.append(value)
        var index = heap.count - 1
        while index > 0 {
            let parent = (index - 1) / 2
            if heap[index] <= heap[parent] { break }
            heap.swapAt(index, parent)
            index = parent
        }
    }
    
    mutating func remove() -> T {
        heap.swapAt(0, heap.count - 1)
        let removed = heap.removeLast()
        var index = 0
        while 2 * index + 1 < heap.count {
            var j = 2 * index + 1
            if j + 1 < heap.count && heap[j + 1] > heap[j] { j += 1 }
            if heap[index] >= heap[j] { break }
            heap.swapAt(index, j)
            index = j
        }
        return removed
    }
}

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

#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]
    }
}

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