#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⃣Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.

😎 Решение:

func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
    projects := make([][2]int, len(profits))
    for i := range profits {
        projects[i] = [2]int{capital[i], profits[i]}
    }
    sort.Slice(projects, func(i, j int) bool {
        return projects[i][0] < projects[j][0]
    })

    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    ptr := 0

    for i := 0; i < k; i++ {
        for ptr < len(projects) && projects[ptr][0] <= w {
            heap.Push(maxHeap, projects[ptr][1])
            ptr++
        }
        if maxHeap.Len() == 0 {
            break
        }
        w += heap.Pop(maxHeap).(int)
    }

    return w
}

type MaxHeap []int

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

import (
    "fmt"
    "sort"
    "strconv"
    "unicode"
)

func countOfAtoms(formula string) string {
    stack := []map[string]int{{}}
    n := len(formula)
    i := 0

    for i < n {
        if formula[i] == '(' {
            stack = append(stack, map[string]int{})
            i++
        } else if formula[i] == ')' {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            i++
            iStart := i
            for i < n && unicode.IsDigit(rune(formula[i])) {
                i++
            }
            multiplicity, _ := strconv.Atoi(formula[iStart:i])
            if multiplicity == 0 {
                multiplicity = 1
            }
            for name, count := range top {
                stack[len(stack)-1][name] += count * multiplicity
            }
        } else {
            iStart := i
            i++
            for i < n && unicode.IsLower(rune(formula[i])) {
                i++
            }
            name := formula[iStart:i]
            iStart = i
            for i < n && unicode.IsDigit(rune(formula[i])) {
                i++
            }
            multiplicity, _ := strconv.Atoi(formula[iStart:i])
            if multiplicity == 0 {
                multiplicity = 1
            }
            stack[len(stack)-1][name] += multiplicity
        }
    }

    countMap := stack[0]
    keys := make([]string, 0, len(countMap))
    for key := range countMap {
        keys = append(keys, key)
    }
    sort.Strings(keys)
    result := ""
    for _, name := range keys {
        result += name
        if countMap[name] > 1 {
            result += strconv.Itoa(countMap[name])
        }
    }
    return result
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

func minWindow(s1 string, s2 string) string {
    if len(s1) == 0 || len(s2) == 0 {
        return ""
    }

    dictT := make(map[rune]int)
    for _, c := range s2 {
        dictT[c]++
    }

    required := len(dictT)
    l, r := 0, 0
    formed := 0
    windowCounts := make(map[rune]int)
    ans := []int{int(^uint(0) >> 1), 0, 0}

    for r < len(s1) {
        c := rune(s1[r])
        windowCounts[c]++

        if count, ok := dictT[c]; ok && windowCounts[c] == count {
            formed++
        }

        for l <= r && formed == required {
            c = rune(s1[l])

            if r-l+1 < ans[0] {
                ans[0] = r - l + 1
                ans[1] = l
                ans[2] = r
            }

            windowCounts[c]--
            if count, ok := dictT[c]; ok && windowCounts[c] < count {
                formed--
            }

            l++
        }

        r++
    }

    if ans[0] == int(^uint(0)>>1) {
        return ""
    }

    return s1[ans[1] : ans[2]+1]
}

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

#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⃣Добавьте саморазделяющиеся числа в результативный список и верните его.

😎 Решение:

package main

func selfDividingNumbers(left int, right int) []int {
    var result []int
    for num := left; num <= right; num++ {
        if isSelfDividing(num) {
            result = append(result, num)
        }
    }
    return result
}

func isSelfDividing(num int) bool {
    n := num
    for n > 0 {
        digit := n % 10
        if digit == 0 || num % digit != 0 {
            return false
        }
        n /= 10
    }
    return true
}

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

#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 на основе состояния предыдущих подстрок.

😎 Решение:

package main

func countPalindromicSubsequences(s string) int {
    const MOD = 1000000007
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for i := 0; i < n; i++ {
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] {
                l, r := i+1, j-1
                for l <= r && s[l] != s[i] {
                    l++
                }
                for l <= r && s[r] != s[j] {
                    r--
                }
                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⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎 Решение:

package main

import "sort"

type MyCalendarThree struct {
    events map[int]int
}

func Constructor() MyCalendarThree {
    return MyCalendarThree{events: make(map[int]int)}
}

func (this *MyCalendarThree) Book(startTime int, endTime int) int {
    this.events[startTime]++
    this.events[endTime]--
    
    times := make([]int, 0, len(this.events))
    for time := range this.events {
        times = append(times, time)
    }
    sort.Ints(times)
    
    active := 0
    maxActive := 0
    for _, time := range times {
        active += this.events[time]
        if active > maxActive {
            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⃣Используйте словарь для отслеживания значений переменных с учетом области видимости.

😎 Решение:

package main

import (
    "strconv"
    "strings"
)

func evaluate(expression string) int {
    return evaluateExpression(expression, map[string]int{})
}

func evaluateExpression(expression string, env map[string]int) int {
    if expression[0] != '(' {
        if val, err := strconv.Atoi(expression); err == nil {
            return val
        }
        return env[expression]
    }

    tokens := tokenize(expression)
    if tokens[0] == "let" {
        for i := 1; i < len(tokens)-2; i += 2 {
            env[tokens[i]] = evaluateExpression(tokens[i+1], env)
        }
        return evaluateExpression(tokens[len(tokens)-1], env)
    } else if tokens[0] == "add" {
        return evaluateExpression(tokens[1], env) + evaluateExpression(tokens[2], env)
    } else if tokens[0] == "mult" {
        return evaluateExpression(tokens[1], env) * evaluateExpression(tokens[2], env)
    }
    return 0
}

func tokenize(expression string) []string {
    tokens := []string{}
    token := ""
    parens := 0
    for _, char := range expression {
        switch char {
        case '(':
            parens++
            if parens == 1 {
                continue
            }
        case ')':
            parens--
            if parens == 0 {
                tokens = append(tokens, tokenize(token)...)
                token = ""
                continue
            }
        case ' ':
            if parens == 1 {
                if token != "" {
                    tokens = append(tokens, token)
                    token = ""
                }
                continue
            }
        }
        token += string(char)
    }
    if token != "" {
        tokens = append(tokens, token)
    }
    return tokens
}

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

#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⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.

😎 Решение:

package main

import "math"

func cherryPickup(grid [][]int) int {
    n := len(grid)
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, 2*n-1)
            for k := range dp[i][j] {
                dp[i][j][k] = math.MinInt32
            }
        }
    }
    dp[0][0][0] = grid[0][0]

    for k := 1; k < 2*n-1; k++ {
        for i1 := max(0, k-n+1); i1 <= min(n-1, k); i1++ {
            for i2 := max(0, k-n+1); i2 <= min(n-1, k); i2++ {
                j1, j2 := k-i1, k-i2
                if j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1 {
                    maxCherries := math.MinInt32
                    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 != math.MinInt32 {
                        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])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

#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⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

package main

type WordFilter struct {
    prefixSuffixMap map[string]int
}

func Constructor(words []string) WordFilter {
    prefixSuffixMap := make(map[string]int)
    for index, word := range words {
        length := len(word)
        for prefixLength := 1; prefixLength <= length; prefixLength++ {
            for suffixLength := 1; suffixLength <= length; suffixLength++ {
                prefix := word[:prefixLength]
                suffix := word[length-suffixLength:]
                key := prefix + "#" + suffix
                prefixSuffixMap[key] = index
            }
        }
    }
    return WordFilter{prefixSuffixMap}
}

func (wf *WordFilter) F(pref string, suff string) int {
    key := pref + "#" + suff
    if index, exists := wf.prefixSuffixMap[key]; exists {
        return index
    }
    return -1
}

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

#hard
Задача: 928. Minimize Malware Spread II

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎 Решение:

package main

import (
  "fmt"
  "math"
  "sort"
)

func minMalwareSpread(graph [][]int, initial []int) int {
  n := len(graph)

  dfs := func(node int, visited map[int]bool, component *[]int) {
    stack := []int{node}
    for len(stack) > 0 {
      u := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      *component = append(*component, u)
      for v := 0; v < n; v++ {
        if graph[u][v] == 1 && !visited[v] {
          visited[v] = true
          stack = append(stack, v)
        }
      }
    }
  }

  var components [][]int
  visited := make(map[int]bool)

  for i := 0; i < n; i++ {
    if !visited[i] {
      component := []int{}
      visited[i] = true
      dfs(i, visited, &component)
      components = append(components, component)
    }
  }

  infectedInComponent := make([]int, len(components))
  nodeToComponent := make(map[int]int)

  for idx, component := range components {
    for _, node := range component {
      nodeToComponent[node] = idx
    }
  }

  for _, node := range initial {
    componentIdx := nodeToComponent[node]
    infectedInComponent[componentIdx]++
  }

  minInfected := math.MaxInt32
  resultNode := initial[0]

  sort.Ints(initial)

  for _, node := range initial {
    componentIdx := nodeToComponent[node]
    if infectedInComponent[componentIdx] == 1 {
      componentSize := len(components[componentIdx])
      if componentSize < minInfected || (componentSize == minInfected && node < resultNode) {
        minInfected = componentSize
        resultNode = node
      }
    }
  }

  return resultNode
}

func main() {
  graph := [][]int{
    {1, 1, 0},
    {1, 1, 0},
    {0, 0, 1},
  }
  initial := []int{0, 1}
  fmt.Println(minMalwareSpread(graph, initial))
}

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