Python | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Show more
8 924
Subscribers
-1024 hours
-427 days
-12730 days
Posts Archive
8 922
#medium
Задача: 309. Best Time to Buy and Sell Stock with Cooldown
Дан массив prices, где prices[i] — цена данной акции в i-й день.
Найдите максимальную прибыль, которую можно получить. Вы можете совершить любое количество транзакций (т. е. купить и продать одну акцию несколько раз) с следующими ограничениями:
После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).
Пример:
Input: prices = [1] Output: 0👨💻 Алгоритм: 1⃣Инициализация состояний Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи. 2⃣Обновление состояний Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день. 3⃣Определение максимальной прибыли В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли. 😎 Решение:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
hold = -prices[0]
sold = 0
cooldown = 0
for i in range(1, n):
new_hold = max(hold, cooldown - prices[i])
new_sold = hold + prices[i]
new_cooldown = max(cooldown, sold)
hold = new_hold
sold = new_sold
cooldown = new_cooldown
return max(sold, cooldown)8 922
#medium
Задача: 669. Trim a Binary Search Tree
Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.
Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ.
Пример:
Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
if not root:
return None
if root.val > high:
return self.trimBST(root.left, low, high)
if root.val < low:
return self.trimBST(root.right, low, high)
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root8 922
#medium
Задача: 1530. Number of Good Leaf Nodes Pairs
Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance.
Верните количество хороших пар листовых узлов в дереве.
Пример:
Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.class Solution:
def countPairs(self, root: TreeNode, distance: int) -> int:
graph = defaultdict(list)
leafNodes = set()
self.traverseTree(root, None, graph, leafNodes)
ans = 0
for leaf in leafNodes:
bfsQueue = deque([leaf])
seen = set([leaf])
for i in range(distance + 1):
size = len(bfsQueue)
for _ in range(size):
currNode = bfsQueue.popleft()
if currNode in leafNodes and currNode != leaf:
ans += 1
for neighbor in graph[currNode]:
if neighbor not in seen:
bfsQueue.append(neighbor)
seen.add(neighbor)
return ans // 2
def traverseTree(self, currNode, prevNode, graph, leafNodes):
if not currNode:
return
if not currNode.left and not currNode.right:
leafNodes.add(currNode)
if prevNode:
graph[prevNode].append(currNode)
graph[currNode].append(prevNode)
self.traverseTree(currNode.left, currNode, graph, leafNodes)
self.traverseTree(currNode.right, currNode, graph, leafNodes)8 922
#medium
Задача: 565. Array Nesting
Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1].
Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:
Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.
Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.
Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.
Верните длину самого длинного множества s[k].
Пример:
Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation:
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}
👨💻 Алгоритм:
1⃣Создайте массив для отслеживания посещенных элементов.
2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.
3⃣Обновите максимальную длину найденного множества.
😎 Решение:
class Solution:
def arrayNesting(self, nums: List[int]) -> int:
visited = [False] * len(nums)
max_length = 0
for i in range(len(nums)):
if not visited[i]:
start = i
count = 0
while not visited[start]:
visited[start] = True
start = nums[start]
count += 1
max_length = max(max_length, count)
return max_length8 922
Учишь Python, но как дело доходит до собственного кода — всё, кирдык? 😥
На форумах только одно: «Больше практиковаться!» А толку? Ноль понимания и никакой поддержки от профи…
Плавали - знаем)) Поэтому специально для тебя - чат Python-щиков 🤝
Что получишь?
1️⃣ Сможешь задавать любые вопросы без страха и осуждения и получать ответы за минуты, а не часы поиска в инете
2️⃣ Регулярные плюшки в виде стримов от препода с 15-ти летним опытом
3️⃣ Общение с единомышленниками и заряд мотивации
➡️ А еще, забирай в закрепе БЕСПЛАТНЫЙ вводный курс по Python
Короче, всё для прокачки! Залетай к нам — ссылка на чат (тык)
8 922
#easy
Задача: 563. Binary Tree Tilt
Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.
Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.
Пример:
Input: root = [1,2,3] Output: 1 Explanation: Tilt of node 2 : |0-0| = 0 (no children) Tilt of node 3 : |0-0| = 0 (no children) Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3) Sum of every tilt : 0 + 0 + 1 = 1👨💻 Алгоритм: 1⃣Определите рекурсивную функцию, которая вычисляет сумму значений узлов поддерева и наклон текущего узла. 2⃣Для каждого узла вычислите сумму значений левого и правого поддерева, а также их наклон, добавляя наклон к общей сумме. 3⃣Верните общую сумму наклонов всех узлов. 😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def findTilt(self, root: TreeNode) -> int:
self.total_tilt = 0
def sum_and_tilt(node):
if not node:
return 0
left_sum = sum_and_tilt(node.left)
right_sum = sum_and_tilt(node.right)
node_tilt = abs(left_sum - right_sum)
self.total_tilt += node_tilt
return node.val + left_sum + right_sum
sum_and_tilt(root)
return self.total_tilt8 922
Repost from easyoffer
📊 Реклама в сети телеграм каналов easyoffer
✈️ Для заказа пишите @easyoffer_adv
easyoffer
Backend
Python | Вопросы
Python | Удалёнка
Python | LeetCode
Python | Тесты
Frontend | Вопросы
Frontend | Удалёнка
JavaScript | LeetCode
Frontend | Тесты
Java | Вопросы
Java | Удалёнка
Java | LeetCode
Java | Тесты
Тестировщик | Вопросы
Тестировщик | Удалёнка
Тестировщик | Тесты
Data Science | Вопросы
Data Science | Удалёнка
Data Science | Тесты
C# | Вопросы
C# | Удалёнка
C# | LeetCode
C# | Тесты
C/C++ | Вопросы
C/C++ | Удалёнка
C/C++ | LeetCode
C/C++ | Тесты
Golang | Вопросы
Golang | Удалёнка
Golang | LeetCode
Golang | Тесты
DevOps | Вопросы
DevOps | Удалёнка
DevOps | Тесты
PHP | Вопросы
PHP | Удалёнка
PHP | LeetCode
PHP | Тесты
Kotlin | Вопросы
Kotlin | Удалёнка
Kotlin | LeetCode
Kotlin | Тесты
Swift | Вопросы
Swift | Удалёнка
Swift | LeetCode
Swift | Тесты
📊 Реклама в сети телеграм каналов easyoffer
✈️ Для заказа пишите @easyoffer_adv
8 922
#medium
Задача: 562. Longest Line of Consecutive One in Matrix
Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.
Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.
Пример:
Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]] Output: 3👨💻 Алгоритм: 1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal. 2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии. 3⃣Верните максимальную длину. 😎 Решение:
class Solution:
def longestLine(self, mat: List[List[int]]) -> int:
if not mat or not mat[0]:
return 0
m, n = len(mat), len(mat[0])
max_length = 0
horizontal = [[0] * n for _ in range(m)]
vertical = [[0] * n for _ in range(m)]
diagonal = [[0] * n for _ in range(m)]
anti_diagonal = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if mat[i][j] == 1:
horizontal[i][j] = (horizontal[i][j-1] if j > 0 else 0) + 1
vertical[i][j] = (vertical[i-1][j] if i > 0 else 0) + 1
diagonal[i][j] = (diagonal[i-1][j-1] if i > 0 and j > 0 else 0) + 1
anti_diagonal[i][j] = (anti_diagonal[i-1][j+1] if i > 0 and j < n-1 else 0) + 1
max_length = max(max_length, horizontal[i][j], vertical[i][j], diagonal[i][j], anti_diagonal[i][j])
return max_length8 922
#easy
Задача: 561. Array Partition
Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.
Пример:
Input: nums = [1,4,3,2] Output: 4 Explanation: All possible pairings (ignoring the ordering of elements) are: 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 So the maximum possible sum is 4.👨💻 Алгоритм: 1⃣Отсортируйте массив nums в неубывающем порядке. 2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого). 3⃣Суммируйте выбранные элементы и верните эту сумму. 😎 Решение:
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
nums.sort()
return sum(nums[i] for i in range(0, len(nums), 2))8 922
#medium
Задача: 560. Subarray Sum Equals K
Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.
Подмассив - это непрерывная непустая последовательность элементов внутри массива.
Пример:
Input: nums = [1,1,1], k = 2 Output: 2👨💻 Алгоритм: 1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums. 2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k. 3⃣Всякий раз, когда сумма равна k, увеличить счетчик, используемый для хранения необходимого результата. 😎 Решение:
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = 0
for start in range(len(nums)):
for end in range(start + 1, len(nums) + 1):
sum_ = sum(nums[start:end])
if sum_ == k:
count += 1
return count8 922
#easy
Задача: 559. Maximum Depth of N-ary Tree
Дано n-арное дерево, найдите его максимальную глубину.
Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.
Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры).
Пример:
Input: root = [1,null,3,2,4,null,5,6] Output: 3👨💻 Алгоритм: 1⃣Интуитивный подход заключается в решении задачи с помощью рекурсии. 2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search). 3⃣Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину. 😎 Решение:
class Solution:
def maxDepth(self, root: 'Node') -> int:
if root is None:
return 0
elif not root.children:
return 1
else:
heights = [self.maxDepth(child) for child in root.children]
return max(heights) + 18 922
#hard
Задача: 632. Smallest Range Covering Elements from K Lists
У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c.
Пример:
Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] Output: [20,24]👨💻 Алгоритм: 1⃣Инициализация и сбор всех начальных элементов Создайте массив для хранения текущих индексов каждого списка и используйте минимальную кучу для отслеживания текущих минимальных элементов из каждого списка. 2⃣Нахождение минимального диапазона Используйте кучу для извлечения минимального элемента и обновления текущего диапазона. Обновляйте максимальный элемент в текущем диапазоне при добавлении новых элементов. 3⃣Проверка и обновление диапазона Продолжайте обновлять кучу и диапазон, пока возможно. Завершите, когда один из списков исчерпан. 😎 Решение:
from heapq import heappop, heappush
def smallestRange(nums):
min_heap = []
max_value = float('-inf')
for i in range(len(nums)):
heappush(min_heap, (nums[i][0], i, 0))
max_value = max(max_value, nums[i][0])
range_start, range_end = float('-inf'), float('inf')
while len(min_heap) == len(nums):
min_value, row, col = heappop(min_heap)
if max_value - min_value < range_end - range_start:
range_start, range_end = min_value, max_value
if col + 1 < len(nums[row]):
heappush(min_heap, (nums[row][col + 1], row, col + 1))
max_value = max(max_value, nums[row][col + 1])
return [range_start, range_end]8 922
#hard
Задача: 358. Rearrange String k Distance Apart
Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "".
Пример:
Input: s = "aabbcc", k = 3 Output: "abcabc" Explanation: The same letters are at least a distance of 3 from each other.👨💻 Алгоритм: 1⃣Создайте словарь частот для символов строки и определите максимальную частоту. 2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов. 3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку. 😎 Решение:
from collections import defaultdict
class Solution:
def rearrangeString(self, s: str, k: int) -> str:
freqs = defaultdict(int)
max_freq = 0
for char in s:
freqs[char] += 1
max_freq = max(max_freq, freqs[char])
most_chars = {char for char, freq in freqs.items() if freq == max_freq}
second_chars = {char for char, freq in freqs.items() if freq == max_freq - 1}
segments = [list() for _ in range(max_freq)]
for i in range(max_freq):
for char in most_chars:
segments[i].append(char)
if i < max_freq - 1:
for char in second_chars:
segments[i].append(char)
segment_id = 0
for char, freq in freqs.items():
if char in most_chars or char in second_chars:
continue
for _ in range(freq):
segments[segment_id].append(char)
segment_id = (segment_id + 1) % (max_freq - 1)
for i in range(max_freq - 1):
if len(segments[i]) < k:
return ""
return "".join("".join(segment) for segment in segments)8 922
#medium
Задача: 435. Non-overlapping Intervals
Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.
Пример:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.👨💻 Алгоритм: 1⃣Отсортируйте интервалы по времени окончания. 2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN. 3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans. 😎 Решение:
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
ans = 0
k = float('-inf')
for x, y in intervals:
if x >= k:
k = y
else:
ans += 1
return ans
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
ans = 0
k = float('-inf')
for x, y in intervals:
if x >= k:
k = y
else:
ans += 1
return ans8 922
#hard
Задача: 631. Design Excel Sum Formula
Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.
Пример:
Input ["Excel", "set", "sum", "set", "get"] [[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]] Output [null, null, 4, null, 6]👨💻 Алгоритм: 1⃣Инициализация Создайте класс Excel, который будет инициализировать матрицу нужного размера и хранить текущие значения ячеек. Реализуйте методы для установки значений, получения значений и вычисления суммы. 2⃣Метод установки значений Реализуйте метод set, который будет изменять значение ячейки в матрице. 3⃣Метод вычисления суммы Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек. 😎 Решение:
class Excel:
def __init__(self, height: int, width: str):
self.mat = [[0] * (ord(width) - ord('A') + 1) for _ in range(height)]
self.formulas = {}
def set(self, row: int, column: str, val: int) -> None:
self.mat[row - 1][ord(column) - ord('A')] = val
self.formulas.pop((row, column), None)
def get(self, row: int, column: str) -> int:
if (row, column) in self.formulas:
return self._evaluate_formula(row, column)
return self.mat[row - 1][ord(column) - ord('A')]
def sum(self, row: int, column: str, numbers: List[str]) -> int:
self.formulas[(row, column)] = numbers
return self._evaluate_formula(row, column)
def _evaluate_formula(self, row: int, column: str) -> int:
total = 0
for number in self.formulas[(row, column)]:
if ':' in number:
start, end = number.split(':')
start_row, start_col = int(start[1:]), start[0]
end_row, end_col = int(end[1:]), end[0]
for r in range(start_row, end_row + 1):
for c in range(ord(start_col), ord(end_col) + 1):
total += self.get(r, chr(c))
else:
r, c = int(number[1:]), number[0]
total += self.get(r, c)
return total8 922
#hard
Задача: 354. Russian Doll Envelopes
Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.
Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).
Примечание: Вы не можете поворачивать конверт.
Пример:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).👨💻 Алгоритм: 1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте). 2⃣Извлеките вторую размерность (высоты) отсортированного массива. 3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот. 😎 Решение:
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for num in nums:
i = bisect_left(dp, num)
if i < len(dp):
dp[i] = num
else:
dp.append(num)
return len(dp)
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
second_dim = [e[1] for e in envelopes]
return self.lengthOfLIS(second_dim)8 922
#easy
Задача: 434. Number of Segments in a String
Дана строка s, верните количество сегментов в строке.
Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.
Пример:
Input: s = "Hello, my name is John" Output: 5 Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]👨💻 Алгоритм: 1⃣Инициализируйте счетчик сегментов segment_count равным 0. 2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count. 3⃣Верните segment_count. 😎 Решение:
class Solution:
def countSegments(self, s: str) -> int:
segment_count = 0
for i in range(len(s)):
if (i == 0 or s[i-1] == ' ') and s[i] != ' ':
segment_count += 1
return segment_count8 922
#hard
Задача: 630. Course Schedule III
Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.
Пример:
Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]] Output: 3👨💻 Алгоритм: 1⃣Сортировка курсов Отсортируйте курсы по их конечным датам (lastDay). Это позволяет проходить курсы как можно ближе к их крайним срокам. 2⃣Проход по курсам Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов. 3⃣Добавление и удаление курсов Для каждого курса: Добавьте его продолжительность в приоритетную очередь и обновите общее время прохождения курсов. Если общее время превышает крайний срок текущего курса, удалите самый длительный курс из очереди и скорректируйте общее время. 😎 Решение:
import heapq
def scheduleCourse(courses):
courses.sort(key=lambda x: x[1])
total_time = 0
max_heap = []
for duration, last_day in courses:
heapq.heappush(max_heap, -duration)
total_time += duration
if total_time > last_day:
total_time += heapq.heappop(max_heap)
return len(max_heap)8 922
#hard
Задача: 629. K Inverse Pairs Array
Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.
Пример:
Input: n = 3, k = 0 Output: 1👨💻 Алгоритм: 1⃣Инициализация Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0. 2⃣Заполнение DP-таблицы Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1. 3⃣Возвращение результата Результатом будет значение dp[n][k]. 😎 Решение:
def kInversePairs(n, k):
MOD = 10**9 + 7
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
dp[i][0] = 1
for j in range(1, k + 1):
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
if j >= i:
dp[i][j] -= dp[i - 1][j - i]
dp[i][j] %= MOD
return dp[n][k]8 922
#medium
Задача: 628. Maximum Product of Three Numbers
Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.
Пример:
Input: nums = [1,2,3] Output: 6👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива. 3⃣Верните максимальное из двух найденных произведений. 😎 Решение:
def maximumProduct(nums):
nums.sort()
max1 = nums[-1] * nums[-2] * nums[-3]
max2 = nums[0] * nums[1] * nums[-1]
return max(max1, max2)