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

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

Пример:

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

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

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

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

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

😎 Решение:

from collections import Counter, defaultdict

def minWindow(s1, s2):
    if not s1 or not s2:
        return ""

    dict_t = Counter(s2)
    required = len(dict_t)
    l, r = 0, 0
    formed = 0
    window_counts = defaultdict(int)
    ans = float("inf"), None, None

    while r < len(s1):
        character = s1[r]
        window_counts[character] += 1

        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1

        while l <= r and formed == required:
            character = s1[l]

            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)

            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1

            l += 1

        r += 1

    return "" if ans[0] == float("inf") else 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⃣Добавьте саморазделяющиеся числа в результативный список и верните его.

😎 Решение:

func selfDividingNumbers(_ left: Int, _ right: Int) -> [Int] {
    func isSelfDividing(_ num: Int) -> Bool {
        var n = num
        while n > 0 {
            let digit = n % 10
            if digit == 0 || num % digit != 0 {
                return false
            }
            n /= 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 на основе состояния предыдущих подстрок.

😎 Решение:

def countPalindromicSubsequences(s):
    MOD = 10**9 + 7
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = 1
        
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                l, r = i + 1, j - 1
                while l <= r and s[l] != s[i]:
                    l += 1
                while l <= r and s[r] != s[j]:
                    r -= 1
                if l > r:
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 2
                elif 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⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎 Решение:

from collections import defaultdict

class MyCalendarThree:
    def __init__(self):
        self.start_times = defaultdict(int)
        self.end_times = defaultdict(int)

    def book(self, startTime, endTime):
        self.start_times[startTime] += 1
        self.end_times[endTime] += 1
        
        active = 0
        max_active = 0
        for time in sorted(self.start_times.keys()):
            active += self.start_times[time]
            if time in self.end_times:
                active -= self.end_times[time]
            max_active = max(max_active, active)
        
        return max_active

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

#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:
    def evaluate(self, expression: str) -> int:
        def evaluate(expression, env):
            if expression[0] != '(':
                if expression[0].isalpha():
                    return env[expression]
                return int(expression)
            
            tokens = tokenize(expression)
            if tokens[0] == 'let':
                for i in range(1, len(tokens) - 2, 2):
                    env[tokens[i]] = evaluate(tokens[i + 1], env)
                return evaluate(tokens[-1], env)
            elif tokens[0] == 'add':
                return evaluate(tokens[1], env) + evaluate(tokens[2], env)
            elif tokens[0] == 'mult':
                return evaluate(tokens[1], env) * evaluate(tokens[2], env)
        
        def tokenize(expression):
            tokens, token, parens = [], '', 0
            for char in expression:
                if char == '(':
                    parens += 1
                    if parens == 1:
                        continue
                elif char == ')':
                    parens -= 1
                    if parens == 0:
                        tokens.append(tokenize(token))
                        token = ''
                        continue
                elif char == ' ' and parens == 1:
                    if token:
                        tokens.append(token)
                        token = ''
                    continue
                token += char
            if token:
                tokens.append(token)
            return tokens
        
        return evaluate(expression, {})

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

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

😎 Решение:

def cherryPickup(grid):
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for _ in range(n)]
    dp[0][0][0] = grid[0][0]

    for k in range(1, 2 * (n - 1) + 1):
        for i1 in range(max(0, k - n + 1), min(n, k + 1)):
            for i2 in range(max(0, k - n + 1), min(n, k + 1)):
                j1, j2 = k - i1, k - i2
                if 0 <= j1 < n and 0 <= j2 < n and grid[i1][j1] != -1 and grid[i2][j2] != -1:
                    max_cherries = max(
                        dp[i1 - 1][i2 - 1][k - 1] if i1 > 0 and i2 > 0 else -float('inf'),
                        dp[i1 - 1][i2][k - 1] if i1 > 0 else -float('inf'),
                        dp[i1][i2 - 1][k - 1] if i2 > 0 else -float('inf'),
                        dp[i1][i2][k - 1]
                    )
                    if max_cherries != -float('inf'):
                        dp[i1][i2][k] = max_cherries + 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:
    def __init__(self, words):
        self.prefix_suffix_map = {}
        for index, word in enumerate(words):
            length = len(word)
            for prefix_length in range(1, length + 1):
                for suffix_length in range(1, length + 1):
                    key = word[:prefix_length] + '#' + word[-suffix_length:]
                    self.prefix_suffix_map[key] = index
    
    def f(self, pref, suff):
        key = pref + '#' + suff
        return self.prefix_suffix_map.get(key, -1)

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

#hard
Задача: 749. Contain Virus

Вирус быстро распространяется, и ваша задача - поместить зараженную область в карантин, установив стены. Мир моделируется как бинарная сетка m x n isInfected, где isInfected[i][j] == 0 обозначает незараженные клетки, а isInfected[i][j] == 1 - клетки, зараженные вирусом. Между любыми двумя соседними клетками, расположенными в четырех направлениях, может быть установлена стена (и только одна стена) на общей границе. Каждую ночь вирус распространяется на все соседние клетки во всех четырех направлениях, если не блокируется стеной. Ресурсы ограничены. Каждый день вы можете устанавливать стены только вокруг одного региона (то есть пораженной области (непрерывного блока зараженных клеток), которая угрожает наибольшим количеством незараженных клеток на следующую ночь). Ничьей не будет никогда. Верните количество стен, использованных для карантина всех зараженных регионов. Если мир будет полностью заражен, верните количество использованных стен.

Пример:

Input: isInfected = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]
Output: 10

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

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

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

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

😎 Решение:

def containVirus(isInfected):
    def neighbors(r, c):
        for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
            if 0 <= nr < len(isInfected) and 0 <= nc < len(isInfected[0]):
                yield nr, nc
    
    def dfs(r, c, region, frontiers, walls):
        stack = [(r, c)]
        region.add((r, c))
        while stack:
            r, c = stack.pop()
            for nr, nc in neighbors(r, c):
                if isInfected[nr][nc] == 1 and (nr, nc) not in region:
                    stack.append((nr, nc))
                    region.add((nr, nc))
                elif isInfected[nr][nc] == 0:
                    frontiers.add((nr, nc))
                    walls.add((r, c, nr, nc))
    
    total_walls = 0
    while True:
        regions = []
        frontiers = []
        walls = []
        visited = set()
        
        for r in range(len(isInfected)):
            for c in range(len(isInfected[0])):
                if isInfected[r][c] == 1 and (r, c) not in visited:
                    region = set()
                    frontier = set()
                    wall = set()
                    dfs(r, c, region, frontier, wall)
                    visited |= region
                    if frontier:
                        regions.append(region)
                        frontiers.append(frontier)
                        walls.append(wall)
        
        if not regions:
            break
        
        max_threat_index = max(range(len(frontiers)), key=lambda i: len(frontiers[i]))
        total_walls += len(walls[max_threat_index])
        
        for i, region in enumerate(regions):
            if i == max_threat_index:
                for r, c in region:
                    isInfected[r][c] = -1
            else:
                for r, c in frontiers[i]:
                    isInfected[r][c] = 1
    
    return total_walls

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

#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

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

2⃣Инициализируйте пустое множество для хранения чисел.

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

😎 Решение:

def minSetSize(intervals):
    intervals.sort(key=lambda x: x[1])
    nums = []
    for start, end in intervals:
        if not nums or nums[-1] < start:
            nums.append(end - 1)
            nums.append(end)
        elif nums[-1] == end - 1:
            nums.append(end)
    return len(nums)

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

#hard
Задача: 759. Employee Free Time

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

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

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

from typing import List

class Interval:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end

def employeeFreeTime(schedule: List[List[Interval]]) -> List[Interval]:
    intervals = []
    for employee in schedule:
        intervals.extend(employee)
    
    intervals.sort(key=lambda x: x.start)
    
    merged = []
    for interval in intervals:
        if not merged or merged[-1].end < interval.start:
            merged.append(interval)
        else:
            merged[-1].end = max(merged[-1].end, interval.end)
    
    free_time = []
    for i in range(1, len(merged)):
        if merged[i].start > merged[i-1].end:
            free_time.append(Interval(merged[i-1].end, merged[i].start))
    
    return free_time

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