Python | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:9 162
Subscribers
-324 hours
-227 days
-7030 days
Posts Archive
9 162
Задача: 931. Minimum Falling Path Sum
Сложность: medium
Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).
Пример:
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]] Output: 13👨💻 Алгоритм: 1⃣Использовать динамическое программирование для хранения минимальных сумм падающих путей для каждой позиции. 2⃣Инициализировать dp массив копией первой строки исходной матрицы. Пройти по каждой строке, обновляя dp массив на основе значений из предыдущей строки. 3⃣Вернуть минимальное значение в последней строке dp массива. 😎 Решение:
def minFallingPathSum(matrix):
n = len(matrix)
dp = matrix[0][:]
for i in range(1, n):
new_dp = [0] * n
for j in range(n):
new_dp[j] = matrix[i][j] + min(dp[j], dp[j-1] if j > 0 else float('inf'), dp[j+1] if j < n - 1 else float('inf'))
dp = new_dp
return min(dp)9 162
Repost from easyoffer
Новая фича на easyoffer – Автоотлики
Вы автоматически откликаетесь на подходящие вам вакансии. Попробуйте её бесплатно и начните получать больше предложений о работе.
🚀 Запуск занимаем всего 3 минуты, а экономит очень много времени
🛡 Это безопасно: easyoffer официально одобрен HeadHunter и прошел его модерацию.
🥷🏻 Автоотклик незаметен для рекртера. Автоотклик ничем не отличается от обычного отклика, который вы делаете вручную
Рекрутеры давно используют автоматизацию для поиска кандидатов. Так почему вы должны откликаться вручную?
💡Совет – Добавьте шаблон сопроводительного письма, чтобы откликаться на большее количество вакансий (на некоторые вакансии нельзя откликнуться без сопроводительного)
Попробовать бесплатно → https://easyoffer.ru/autoapply
9 162
Задача: 482. License Key Formatting
Сложность: easy
Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.
Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные.
Верните переформатированный лицензионный ключ.
Пример:
Input: s = "5F3Z-2e-9-w", k = 4 Output: "5F3Z-2E9W" Explanation: The string s has been split into two parts, each part has 4 characters. Note that the two extra dashes are not needed and can be removed.👨💻 Алгоритм: 1⃣Инициализация Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата. 2⃣Итерация по входной строке в обратном порядке Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count. 3⃣Завершение Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её. 😎 Решение:
class Solution:
def licenseKeyFormatting(self, s: str, k: int) -> str:
count = 0
ans = []
for char in reversed(s):
if char != '-':
ans.append(char.upper())
count += 1
if count == k:
ans.append('-')
count = 0
if ans and ans[-1] == '-':
ans.pop()
return ''.join(reversed(ans))9 162
Задача: 1000. Minimum Cost to Merge Stones
Сложность: hard
Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.
Пример:
Input: stones = [3,2,4,1], k = 2 Output: 20👨💻 Алгоритм: 1⃣Проверка на возможность объединения: Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1. 2⃣Инициализация и динамическое программирование: Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней. Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве. 3⃣Заполнение таблицы dp: Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование. Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения. 😎 Решение:
class Solution:
def mergeStones(self, stones: List[int], k: int) -> int:
n = len(stones)
if (n - 1) % (k - 1) != 0:
return -1
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + stones[i]
dp = [[0] * n for _ in range(n)]
for m in range(k, n + 1):
for i in range(n - m + 1):
j = i + m - 1
dp[i][j] = min(dp[i][t] + dp[t + 1][j] for t in range(i, j, k - 1))
if (j - i) % (k - 1) == 0:
dp[i][j] += prefix[j + 1] - prefix[i]
return dp[0][n - 1]9 162
Задача: 1165. Single-Row Keyboard
Сложность: easy
Есть специальная клавиатура, на которой все клавиши расположены в один ряд.
Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.
Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.
Пример:
Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.class Solution:
def calculateTime(self, keyboard: str, word: str) -> int:
key_indices = [-1] * 26
for i, c in enumerate(keyboard):
key_indices[ord(c) - ord('a')] = i
prev = 0
result = 0
for c in word:
index = key_indices[ord(c) - ord('a')]
result += abs(prev - index)
prev = index
return result9 162
Задача: 924. Minimize Malware Spread
Сложность: hard
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.
Пример:
Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8 Output: 20👨💻 Алгоритм: 1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial. 2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО. 3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом. 😎 Решение:
def minMalwareSpread(graph, initial):
def dfs(node, infected):
for neighbor in range(len(graph)):
if graph[node][neighbor] == 1 and neighbor not in infected:
infected.add(neighbor)
dfs(neighbor, infected)
n = len(graph)
initial_set = set(initial)
initial.sort()
min_infected = float('inf')
best_node = initial[0]
for node in initial:
infected = set(initial_set)
infected.remove(node)
for i in initial_set:
if i != node:
dfs(i, infected)
if len(infected) < min_infected:
min_infected = len(infected)
best_node = node
return best_node9 162
Задача: 617. Merge Two Binary Trees
Сложность: medium
Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев.
Пример:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] Output: [3,4,5,5,4,null,7]👨💻 Алгоритм: 1⃣Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null. 2⃣Если оба узла не пустые, создаем новый узел, значение которого равно сумме значений двух узлов. Рекурсивно объединяем левые и правые поддеревья. 3⃣Возвращаем новый узел, который является корнем объединенного дерева. 😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mergeTrees(root1, root2):
if not root1:
return root2
if not root2:
return root1
mergedNode = TreeNode(root1.val + root2.val)
mergedNode.left = mergeTrees(root1.left, root2.left)
mergedNode.right = mergeTrees(root1.right, root2.right)
return mergedNode9 162
Изиоффер переходит в публичное бета-тестирование!
🎉 Что нового:
🟢Анализ IT собеседований на основе 4500+ реальных интервью
🟢Вопросы из собеседований с вероятностью встречи
🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов
🟢Пример лучшего ответа
🟢Задачи из собеседований
🟢Тестовые задания
🟢Примеры собеседований
🟢Фильтрация всего контента по грейдам, компаниям
🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек
🟢Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро)
🟢Автоотклики на HeadHunter
🟢Закрытое сообщество easyoffer
💎 Акция в честь открытия для первых 500 покупателей:
🚀 Скидка 50% на PRO тариф на 1 год
🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro
9 162
Задача: 1406. Stone Game III
Сложность: hard
Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.
Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.
Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.
Пример:
Input: stoneValue = [1,2,3,7] Output: "Bob" Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.👨💻 Алгоритм: 1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0. 2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре. 3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья. 😎 Решение:
class Solution:
def stoneGameIII(self, stoneValue: List[int]) -> str:
n = len(stoneValue)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
dp[i] = stoneValue[i] - dp[i + 1]
if i + 2 <= n:
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2])
if i + 3 <= n:
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3])
if dp[0] > 0:
return "Alice"
elif dp[0] < 0:
return "Bob"
else:
return "Tie"9 162
Запустите рекламу в телеграм-каналах с Яндекс Директом
Перфоманс-реклама теперь в телеграм-каналах ⚡
Яндекс Директ знает, как привлечь целевую аудиторию 💰👌
Попробовать
#реклама
yandex.ru
О рекламодателе
9 162
Задача: 1161. Maximum Level Sum of a Binary Tree
Сложность: medium
Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее.
Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна.
Пример:
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.from collections import deque
class Solution:
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
maxSum = float('-inf')
ans = 0
level = 0
q = deque([root])
while q:
level += 1
sumAtCurrentLevel = 0
for _ in range(len(q)):
node = q.popleft()
sumAtCurrentLevel += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if maxSum < sumAtCurrentLevel:
maxSum = sumAtCurrentLevel
ans = level
return ans9 162
📺 База 1000+ реальных собеседований
На программиста, тестировщика, аналитика, проджекта и другие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
9 162
Подключите корпоративный ДМС в Совкомбанк Страхование
Позаботьтесь о своей команде! ✨
ДМС от Совкомбанк Страхование – это решения под любой бюджет и потребности.
25 лет опыта, телемедицина, офисный врач и доступ к 10 000+ клиник по России.
Сэкономьте до 30% с ДМС с франшизой и получите налоговые льготы.
Собственная диспетчерская служба 24/7 всегда на связи. Здоровые сотрудники – успешный бизнес!
Узнайте больше на сайте и оформите ДМС уже сегодня! 🏃♂️⚡
Перейти на сайт
Финансовые услуги оказывает: ПАО "Совкомбанк", АО "Совкомбанк Страхование".
#реклама
sovcomins.ru
О рекламодателе
9 162
Задача: 132. Palindrome Partitioning II
Сложность: Hard
Дана строка s. Разделите строку так, чтобы каждая подстрока разделения была палиндромом.
Верните минимальное количество разрезов, необходимых для разделения строки s на палиндромы.
Пример:
Input: s = "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.👨💻 Алгоритм: 1️⃣Определение задачи и начальные условия: Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end. Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut. Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом). 2️⃣Генерация подстрок и рекурсивный поиск: Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки. 3️⃣Условие палиндрома и рекурсивное разделение: Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки 😎 Решение:
class Solution:
def minCut(self, s: str) -> int:
return self.findMinimumCut(s, 0, len(s) - 1, len(s) - 1)
def findMinimumCut(self, s: str, start: int, end: int, minimumCut: int) -> int:
if start == end or self.isPalindrome(s, start, end):
return 0
for currentEndIndex in range(start, end + 1):
if self.isPalindrome(s, start, currentEndIndex):
minimumCut = min(
minimumCut,
1 + self.findMinimumCut(s, currentEndIndex + 1, end, minimumCut)
)
return minimumCut
def isPalindrome(self, s: str, start: int, end: int) -> bool:
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True9 162
EXLANTIX ET от EXEED. Уже в продаже!
Гибридный кроссовер будущего!
Премиальный гибридный автомобиль EXLANTIX ET в продаже!
Запас хода 1180 км, Ускорение за 4,8 сек до 100 км/ч, 8 лет гарантии или 200 000 км!
Благодаря надежным и современным системам EXLANTIX ET устанавливает новые стандарты гибридных автомобилей, обеспечивая защиту водителя и пассажиров при любых дорожных ситуациях.
Хотите приобрести автомобиль или узнать больше?
Узнать цену
#реклама
exeed.ru
О рекламодателе
9 162
Задача: 1231. Divide Chocolate
Сложность: hard
У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.
Пример:
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5 Output: 6👨💻 Алгоритм: 1⃣Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить. 2⃣Двоичный поиск: Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения. 3⃣Проверка делимости: Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения. 😎 Решение:
def maximizeSweetness(sweetness, k):
def canDivide(minSweetness):
current_sum = 0
cuts = 0
for sweet in sweetness:
current_sum += sweet
if current_sum >= minSweetness:
cuts += 1
current_sum = 0
return cuts >= k + 1
left, right = min(sweetness), sum(sweetness) // (k + 1)
while left < right:
mid = (left + right + 1) // 2
if canDivide(mid):
left = mid
else:
right = mid - 1
return left9 162
Задача: 130. Surrounded Regions
Сложность: Medium
Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:
Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.
Пример:
Input: board = [["X"]] Output: [["X"]]👨💻 Алгоритм: 1️⃣Выбор начальных ячеек и инициация DFS: Начинаем с выбора всех ячеек, расположенных на границах доски. Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS). 2️⃣Логика и выполнение DFS: Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'. Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'. 3️⃣Классификация и финальная обработка ячеек: После обхода всех граничных ячеек мы получаем три типа ячеек: Ячейки с буквой 'X': эти ячейки можно считать стеной. Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'. Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'. 😎 Решение:
class Solution(object):
def solve(self, board: List[List[str]]) -> None:
if not board or not board[0]:
return
self.ROWS = len(board)
self.COLS = len(board[0])
from itertools import product
borders = list(product(range(self.ROWS), [0, self.COLS - 1])) + list(
product([0, self.ROWS - 1], range(self.COLS))
)
for row, col in borders:
self.DFS(board, row, col)
for r in range(self.ROWS):
for c in range(self.COLS):
if board[r][c] == "O":
board[r][c] = "X"
elif board[r][c] == "E":
board[r][c] = "O"
def DFS(self, board: List[List[str]], row: int, col: int) -> None:
if board[row][col] != "O":
return
board[row][col] = "E"
if col < self.COLS - 1:
self.DFS(board, row, col + 1)
if row < self.ROWS - 1:
self.DFS(board, row + 1, col)
if col > 0:
self.DFS(board, row, col - 1)
if row > 0:
self.DFS(board, row - 1, col)9 162
Задача: 199. Binary Tree Right Side View
Сложность: medium
Дано корень бинарного дерева, представьте, что вы стоите с правой стороны от него, верните значения узлов, которые вы видите, упорядоченные сверху вниз.
Пример:
Input: root = [1,2,3,null,5,null,4] Output: [1,3,4]👨💻 Алгоритм: 1️⃣Инициализируйте список правого обзора rightside. Инициализируйте две очереди: одну для текущего уровня и одну для следующего. Добавьте корень в очередь nextLevel. 2️⃣Пока очередь nextLevel не пуста: Инициализируйте текущий уровень: currLevel = nextLevel и очистите очередь следующего уровня nextLevel. Пока очередь текущего уровня не пуста: Извлеките узел из очереди текущего уровня. Добавьте сначала левый, а затем правый дочерний узел в очередь nextLevel. Теперь очередь currLevel пуста, и узел, который у нас есть, является последним и составляет часть правого обзора. Добавьте его в rightside. 3️⃣Верните rightside. 😎 Решение:
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if root is None:
return []
next_level = deque([root])
rightside = []
while next_level:
curr_level = next_level
next_level = deque()
while curr_level:
node = curr_level.popleft()
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
rightside.append(node.val)
return rightside9 162
Задача: 940. Distinct Subsequences II
Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.
Пример:
Input: s = "abc" Output: 7👨💻 Алгоритм: 1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j. 2⃣Инициализировать матрицу DP нулями. Пройти по каждому символу строки: Если символ еще не был встречен, все подпоследовательности до текущего символа + текущий символ. Если символ уже был встречен, учет всех подпоследовательностей, включающих текущий символ, с учетом предыдущих вхождений. 3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7. 😎 Решение:
MOD = 10**9 + 7
def countSubsequences(s):
dp = [0] * 26
for c in s:
index = ord(c) - ord('a')
dp[index] = (sum(dp) + 1) % MOD
return sum(dp) % MOD9 162
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте 30 дней бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
