Python | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
نمایش بیشتر
شبکه:8 960
مشترکین
-424 ساعت
-327 روز
-10530 روز
آرشیو پست ها
8 960
Нейросеть проверит 100% закупок на стройке за минуты!
👍Контроль закупок за 15 минут в день. Нейросеть "Тринити" экономит ваше время и миллионы рублей
Вы - генеральный директор строительной компании, и у вас катастрофически не хватает времени? Работаете 12+ часов в день и не можете контролировать каждую закупку?
💰Тратите миллионы на закупки, но не уверены, что получаете лучшие цены и качество? Хотите спать спокойно, зная, что ваши деньги под защитой?
Просто загрузите счет или тендерный протокол в Telegram-бот
Получите детальный анализ по 18 параметрам за 1 минуту
Экономьте до 10% на каждой закупке без дополнительных усилий
В 3-5 раз дешевле, чем содержать штат контролеров! Работает 24/7 без выходных и отпусков.
👌Узнайте про наш телеграм-бот и тестируйте бесплатно 7 дней! Экономия в первый же день.
Перейти на сайт
#реклама 16+
trinitysafe.ru
О рекламодателе
8 960
Задача: 93. Restore IP Addresses
Сложность: medium
Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:
- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"
Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:
- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)
Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06". Для данной строки s, содержащей только цифры, верните количество способов декодирования. Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.
Пример:
Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).👨💻 Алгоритм: 1️⃣Входим в рекурсию с данной строкой, начиная с индекса 0. 2️⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов. 3️⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач. 😎 Решение:
class Solution(object):
def valid(self, s, start, length):
return length == 1 or (
s[start] != "0"
and (length < 3 or s[start : start + length] <= "255")
)
def helper(self, s, startIndex, dots, ans):
remainingLength = len(s) - startIndex
remainingNumberOfIntegers = 4 - len(dots)
if (
remainingLength > remainingNumberOfIntegers * 3
or remainingLength < remainingNumberOfIntegers
):
return
if len(dots) == 3:
if self.valid(s, startIndex, remainingLength):
temp = ""
last = 0
for dot in dots:
temp += s[last : last + dot] + "."
last += dot
temp += s[startIndex:]
ans.append(temp)
return
for curPos in range(1, min(4, remainingLength + 1)):
dots.append(curPos)
if self.valid(s, startIndex, curPos):
self.helper(s, startIndex + curPos, dots, ans)
dots.pop()
def restoreIpAddresses(self, s):
answer = []
self.helper(s, 0, [], answer)
return answer8 960
Бесплатный онлайн-марафон для руководителей
Два дня практических онлайн-встреч с топ-экспертами в области управления — на них расскажем, как выстроить слаженную работу сотрудников и забыть о хаосе с помощью автоматизации.
Спикеры Битрикс24, SETTERS EDUCATION, «ВкусВилл» и Максим Батырев расскажут:
— как обеспечить рост команды без регламентов и ручного управления
— как мотивировать сотрудников и давать обратную связь
— как управлять большим потоком задач и контролировать их выполнение
— как выстраивать эффективную коммуникацию с командой
Бонусы для всех участников:
— чек-лист: «Как обезопасить команду от кибермошенников?»
— бесплатная консультация по автоматизации командной работы
Бесплатно. 17–18 марта.
Подробная программа мероприятия и регистрация — на сайте.
Узнать больше
#реклама 16+
marathon.bitrix24.works
О рекламодателе
8 960
Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium
Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.
Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.
Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.
Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.
Пример:
Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.class Solution:
def getSmallestString(self, n: int, k: int) -> str:
result = ['a'] * n
for position in range(n):
positionsLeft = (n - position - 1)
if k > positionsLeft * 26:
add = k - (positionsLeft * 26)
result[position] = chr(ord('a') + add - 1)
k -= add
else:
k -= 1
return ''.join(result8 960
Где чатиться с аутсорсерами и подрядчиками?
Пригласите подрядчиков и клиентов в ваш рабочий мессенджер Битрикс24. Они увидят только свои чаты, задачи и звонки, а внутренние данные компании остаются закрытыми.
Всё нужное для работы:
• Общий чат проекта со всеми участниками
• Доступ к задачам, файлам и календарю проекта
• Гибкие права доступа и безопасность данных
Общайтесь, созванивайтесь и согласовывайте прямо в Битрикс24, можно в мобильном приложении.
Зарегистрироваться
#реклама 16+
bitrix24.ru
О рекламодателе
8 960
Задача: 258. Add Digits
Сложность: easy
Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.
Пример:
Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it.👨💻 Алгоритм: 1️⃣Инициализируйте переменную digital_root значением 0. 2️⃣В цикле, пока num больше 0: Добавьте к digital_root последнюю цифру num. Уменьшите num, удалив последнюю цифру. Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0. 3️⃣Верните значение digital_root. 😎 Решение:
class Solution:
def addDigits(self, num: int) -> int:
digital_root = 0
while num > 0:
digital_root += num % 10
num //= 10
if num == 0 and digital_root > 9:
num = digital_root
digital_root = 0
return digital_root8 960
Задача: 979. Distribute Coins in Binary Tree
Сложность: medium
Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.
За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.
Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету.
Пример:
Input: root = [3,0,0] Output: 2 Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.👨💻 Алгоритм: 1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0. 2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves. 3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves. 😎 Решение:
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.moves = 0
self.dfs(root)
return self.moves
def dfs(self, current: Optional[TreeNode]) -> int:
if not current:
return 0
leftCoins = self.dfs(current.left)
rightCoins = self.dfs(current.right)
self.moves += abs(leftCoins) + abs(rightCoins)
return current.val - 1 + leftCoins + rightCoins8 960
Ищу желающих заполнять карточки товаров на ВБ!
Работа полностью на удаленке с зп до 150 000 рублей в месяц.
Без опыта, нужен только телефон, занятость 3-6 часов в день.
Всему обучат на бесплатном курсе и после возьму на работу:
✅ 3 дня уроков по 30 минут
✅ Домашки с проверкой и оплатой бонусами
✅ Плачу 10 тыс за каждую выполненную домашку
Все кто пройдет курс, получат сертификат от школы с образовательной лицензией.
⚡ Набор заканчивается завтра.
👍 Для регистрации жмите кнопку "Зарегистрироваться"
Зарегистрироваться
#реклама 16+
course.wildmanager.ru
О рекламодателе
8 960
Задача: 397. Integer Replacement
Сложность: medium
К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1.
Пример:
Input: n = 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1👨💻 Алгоритм: 1⃣Начните с данного числа n и выполните одну из следующих операций: Если n четное, замените n на n / 2. Если n нечетное, замените n на n + 1 или n - 1. 2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов. 3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат. 😎 Решение:
class Solution:
def integerReplacement(self, n: int) -> int:
def helper(n, memo):
if n == 1:
return 0
if n in memo:
return memo[n]
if n % 2 == 0:
memo[n] = 1 + helper(n // 2, memo)
else:
memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo))
return memo[n]
return helper(n, {})8 960
Задача: 1051. Height Checker
Сложность: easy
Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i].
Пример:
Input: heights = [1,1,4,2,1,3] Output: 3👨💻 Алгоритм: 1⃣Создай отсортированную копию массива heights, чтобы получить ожидаемый порядок высот. 2⃣Пройди по обоим массивам и сравни элементы. 3⃣Подсчитай количество индексов, где элементы двух массивов не равны 😎 Решение:
def heightChecker(heights):
expected = sorted(heights)
count = 0
for i in range(len(heights)):
if heights[i] != expected[i]:
count += 1
return count8 960
Задача: 567. Permutation in String
Сложность: medium
Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.
Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.
Пример:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
👨💻 Алгоритм:
1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.
2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.
3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.
😎 Решение:
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
from collections import Counter
s1Count = Counter(s1)
s2Count = Counter(s2[:len(s1)])
if s1Count == s2Count:
return True
for i in range(len(s1), len(s2)):
s2Count[s2[i]] += 1
s2Count[s2[i - len(s1)]] -= 1
if s2Count[s2[i - len(s1)]] == 0:
del s2Count[s2[i - len(s1)]]
if s1Count == s2Count:
return True
return False8 960
Задача: 200. Number of Islands
Сложность: medium
Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.
Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой.
Пример:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1👨💻 Алгоритм: 1️⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS). 2️⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый. 3️⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров. 😎 Решение:
class Solution:
def numIslands(self, grid):
if not grid:
return 0
num_islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
self.dfs(grid, i, j)
num_islands += 1
return num_islands
def dfs(self, grid, r, c):
if (
r < 0
or c < 0
or r >= len(grid)
or c >= len(grid[0])
or grid[r][c] != "1"
):
return
grid[r][c] = "0"
self.dfs(grid, r - 1, c)
self.dfs(grid, r + 1, c)
self.dfs(grid, r, c - 1)
self.dfs(grid, r, c + 1)8 960
Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium
Вам дан массив целых чисел
nums и целое число target.
Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
mod = 10**9 + 7
power = [1] * n
for i in range(1, n):
power[i] = power[i - 1] * 2 % mod
answer = 0
left, right = 0, n - 1
while left <= right:
if nums[left] + nums[right] <= target:
answer = (answer + power[right - left]) % mod
left += 1
else:
right -= 1
return answer8 960
Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium
В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.
Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.
Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.
Пример:
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4 Output: 3 Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.👨💻 Алгоритм: 1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они. 2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск": Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b). Каждое объединение добавляет новые связи между участниками. 3⃣Следите за количеством групп: Изначально каждый участник рассматривается как отдельная группа. Количество групп уменьшается с каждым полезным объединением. Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени. Если такого момента не существует, верните -1. 😎 Решение:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
return True
return False
class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
logs.sort()
uf = UnionFind(n)
group_count = n
for timestamp, friendA, friendB in logs:
if uf.union(friendA, friendB):
group_count -= 1
if group_count == 1:
return timestamp
return -18 960
Щипцы с паром DEWAL BEAUTY – это забота о ваших волосах
Укладка мечты без вреда для волос! Инновационные паровые щипцы Elite DEWAL BEAUTY дарят бережную укладку с фантастическим блеском.
• Пар мягко увлажняет волосы во время укладки
• Минимизирует повреждения и сухость
• Делает волосы мягкими и блестящими
• Сохраняет здоровье ваших волос
✨ Преимущества:
• Керамико-турмалиновое покрытие
• 4 температурных режима (160-220°C)
• Нагрев за 30 секунд
• Автоотключение через 30 минут
• Легкие (всего 290 г)
Забудьте о сухости и ломкости, только шелковистые и здоровые волосы❤️
Дарим скидку 10% по промокоду SALE10 на все товары!
Купить
#реклама
dewalbeauty.ru
О рекламодателе
8 960
Задача: 1351. Count Negative Numbers in a Sorted Matrix
Сложность: easy
Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid.
Пример:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix.👨💻 Алгоритм: 1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице. 2⃣Использовать два вложенных цикла для итерации по каждому элементу матрицы grid, и если элемент отрицательный, увеличить count на 1. 3⃣Вернуть count. 😎 Решение:
class Solution:
def countNegatives(self, grid):
count = 0
for row in grid:
for element in row:
if element < 0:
count += 1
return count8 960
Задача: 936. Stamping The Sequence
Сложность: hard
Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив
Пример:
Input: stamp = "abc", target = "ababc" Output: [0,2]👨💻 Алгоритм: 1⃣Инициализировать переменные: s как массив символов '?', длиной target.length. res как список для хранения результатов. done как массив булевых значений для отслеживания того, какие позиции уже штампованы. target как массив символов для удобства. 2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i. Использовать функцию doStamp для штампования stamp в target начиная с индекса i. Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length): Перебрать все возможные начальные позиции для штампа. Проверить, можно ли штамповать в текущей позиции. Если можно, штамповать и добавить индекс в res. 3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив. 😎 Решение:
def movesToStamp(stamp, target):
s, t = list(stamp), list(target)
m, n = len(s), len(t)
res = []
done = [False] * n
def canStamp(i):
for j in range(m):
if t[i + j] != '?' and t[i + j] != s[j]:
return False
return True
def doStamp(i):
for j in range(m):
t[i + j] = '?'
res.append(i)
done[i] = True
changed = True
while changed:
changed = False
for i in range(n - m + 1):
if not done[i] and canStamp(i):
doStamp(i)
changed = True
if all(c == '?' for c in t):
return res[::-1]
return []8 960
Задача: 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:
def numOfArrays(self, n: int, m: int, k: int) -> int:
MOD = 10**9 + 7
dp = [[[0] * (k + 1) for _ in range(m + 1)] for _ in range(n + 1)]
for num in range(m + 1):
dp[n][num][0] = 1
for i in range(n - 1, -1, -1):
for maxSoFar in range(m, -1, -1):
for remain in range(k + 1):
ans = 0
for num in range(1, maxSoFar + 1):
ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD
if remain > 0:
for num in range(maxSoFar + 1, m + 1):
ans = (ans + dp[i + 1][num][remain - 1]) % MOD
dp[i][maxSoFar][remain] = ans
return dp[0][0][k]8 960
Задача: 210. Course Schedule II
Сложность: medium
Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.
Пример 1:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0. Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].👨💻 Алгоритм: 1️⃣Инициализация и построение графа: Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе. Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма. 2️⃣Запуск поиска в глубину (DFS): Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла. Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны. 3️⃣Обработка узлов и возвращение результата: После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке. После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания. 😎 Решение:
from collections import defaultdict
class Solution:
WHITE = 1
GRAY = 2
BLACK = 3
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj_list = defaultdict(list)
for dest, src in prerequisites:
adj_list[src].append(dest)
topological_sorted_order = []
is_possible = True
color = {k: Solution.WHITE for k in range(numCourses)}
def dfs(node: int) -> None:
nonlocal is_possible
if not is_possible:
return
color[node] = Solution.GRAY
if node in adj_list:
for neighbor in adj_list[node]:
if color[neighbor] == Solution.WHITE:
dfs(neighbor)
elif color[neighbor] == Solution.GRAY:
is_possible = False
color[node] = Solution.BLACK
topological_sorted_order.append(node)
for vertex in range(numCourses):
if color[vertex] == Solution.WHITE:
dfs(vertex)
return topological_sorted_order[::-1] if is_possible else []8 960
Аукцион выделенных серверов!
Серверы дешевеют у вас на глазах!
Новые лоты каждый день, скидки до -35% на весь срок аренды.
Успейте арендовать, пока лот не ушел другому!
Получить предложение
#реклама 16+
selectel.ru
О рекламодателе
