Python | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Ko'proq ko'rsatish
Tarmoq:9 165
Obunachilar
-624 soatlar
-197 kunlar
-7230 kunlar
Postlar arxiv
9 163
Ищете стабильную видеосвязь и мессенджер?
⚡WhatsApp и Telegram работают с перебоями, Skype с октября без техподдержки — публичные мессенджеры не подходят для бизнеса.
✅Российская платформа МТС Линк доступна 99,9% времени. Попробуйте и убедитесь сами.
Попробовать
#реклама 16+
mts-link.ru
О рекламодателе
9 163
Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium
Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.
Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:
Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.
Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].
Пример:
Input: root = [1,2], voyage = [2,1] Output: [-1] Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.👨💻 Алгоритм: 1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1]. 2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка. 3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage. 😎 Решение:
class Solution:
def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
self.flipped = []
self.index = 0
self.voyage = voyage
self.dfs(root)
if self.flipped and self.flipped[0] == -1:
return [-1]
return self.flipped
def dfs(self, node):
if node:
if node.val != self.voyage[self.index]:
self.flipped = [-1]
return
self.index += 1
if self.index < len(self.voyage) and node.left and node.left.val != self.voyage[self.index]:
self.flipped.append(node.val)
self.dfs(node.right)
self.dfs(node.left)
else:
self.dfs(node.left)
self.dfs(node.right)9 163
Задача: 835. Image Overlap
Сложность: medium
Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.
Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.
Верните максимальное возможное перекрытие.
Пример:
Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]] Output: 3 Explanation: We translate img1 to right by 1 unit and down by 1 unit.👨💻 Алгоритм: 1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия. 2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift). 3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий. 😎 Решение:
class Solution:
def shiftAndCount(self, xShift, yShift, M, R):
leftShiftCount = 0
rightShiftCount = 0
rRow = 0
for mRow in range(yShift, len(M)):
rCol = 0
for mCol in range(xShift, len(M)):
if M[mRow][mCol] == 1 and M[mRow][mCol] == R[rRow][rCol]:
leftShiftCount += 1
if M[mRow][rCol] == 1 and M[mRow][rCol] == R[rRow][mCol]:
rightShiftCount += 1
rCol += 1
rRow += 1
return max(leftShiftCount, rightShiftCount)
def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
maxOverlaps = 0
for yShift in range(len(A)):
for xShift in range(len(A)):
maxOverlaps = max(maxOverlaps, self.shiftAndCount(xShift, yShift, A, B))
maxOverlaps = m9 163
Задача: 751. IP to CIDR
Сложность: medium
Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.
Пример:
Input: ip = "255.0.0.7", n = 10 Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]👨💻 Алгоритм: 1⃣Преобразовать начальный IP-адрес в целое число. 2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n. 3⃣Преобразовать блоки обратно в формат CIDR и вернуть их. 😎 Решение:
def ip_to_int(ip):
parts = ip.split('.')
return (int(parts[0]) << 24) + (int(parts[1]) << 16) + (int(parts[2]) << 8) + int(parts[3])
def int_to_ip(num):
return f"{(num >> 24) & 255}.{(num >> 16) & 255}.{(num >> 8) & 255}.{num & 255}"
def cidr(ip, prefix_length):
return f"{ip}/{prefix_length}"
def find_cidr_blocks(start_ip, n):
start = ip_to_int(start_ip)
result = []
while n > 0:
max_size = 1
while max_size <= start and max_size <= n:
max_size <<= 1
max_size >>= 1
while start % max_size != 0:
max_size >>= 1
result.append(cidr(int_to_ip(start), 32 - max_size.bit_length() + 1))
start += max_size
n -= max_size
return result9 163
Задача: 154. Find Minimum in Rotated Sorted Array II
Сложность: Hard
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать: [4,5,6,7,0,1,4], если он был повернут 4 раза. [0,1,4,4,5,6,7], если он был повернут 7 раз. Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Для данного отсортированного и повернутого массива nums, который может содержать дубликаты, верните минимальный элемент этого массива. Необходимо максимально уменьшить количество операций.
Пример:
Input: nums = [1,3,5] Output: 1👨💻 Алгоритм: 1️⃣Сравнение с правой границей: В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]). 2️⃣Обновление указателей: Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid. Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid. Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента. 3️⃣Итерация до сужения диапазона поиска: Продолжаем процесс, пока левый указатель не встретится с правым. В конечном итоге правый указатель укажет на минимальный элемент массива после всех поворотов. 😎 Решение:
class Solution:
def findMin(self, nums: List[int]) -> int:
low = 0
high = len(nums) - 1
while high > low:
pivot = low + (high - low) // 2
if nums[pivot] < nums[high]:
high = pivot
elif nums[pivot] > nums[high]:
low = pivot + 1
else:
high -= 1
return nums[low]9 163
Как IT-компании увеличить продажи с помощью вебинаров?
Делимся гайдом для маркетологов IT-компаний с рекомендациями ведущих российских разработчиков и экспертов МТС Линк.
Вы узнаете:
- Как правильно использовать онлайн-мероприятия для продвижения;
- Как собрать 10 000 потенциальных клиентов из любой точки мира в одном месте;
- Как увеличить узнаваемость бренда и создать комьюнити вокруг него;
- Как оценить вклад онлайн-мероприятия в продвижение компании и правильно обработать лиды;
Бонус: кейс IT-компании с доходимостью до вебинаров 70%
Получите методичку бесплатно на сайте!
Скачать
#реклама 16+
mts-link.ru
О рекламодателе
9 163
Задача: 480. Sliding Window Median
Сложность: hard
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000] Explanation: Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6👨💻 Алгоритм: 1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента. 2⃣ Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна. 3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления. 😎 Решение:
from typing import List
def medianSlidingWindow(nums: List[int], k: int) -> List[float]:
medians = []
for i in range(len(nums) - k + 1):
window = sorted(nums[i:i + k])
if k % 2 == 1:
medians.append(window[k // 2])
else:
medians.append((window[k // 2 - 1] + window[k // 2]) / 2)
return medians9 163
Задача: 1219. Path with Maximum Gold
Сложность: medium
В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста.
Верните максимальное количество золота, которое вы можете собрать при следующих условиях:
- Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки.
- Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз.
- Вы не можете посещать одну и ту же ячейку более одного раза.
- Никогда не посещайте ячейку с 0 золотом.
- Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото.
Пример:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]] Output: 24 Explanation: [[0,6,0], [5,8,7], [0,9,0]] Path to get the maximum gold, 9 -> 8 -> 7.👨💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте константный массив DIRECTIONS для направления перемещений. Определите количество строк и столбцов в сетке. Инициализируйте переменную maxGold для хранения максимального количества собранного золота. 2⃣Функция DFS и обратный трек: Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека. Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота. Пометьте текущую ячейку как посещённую и сохраните её значение. Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь. Сбросьте текущую ячейку до её исходного значения для дальнейших исследований. 3⃣Поиск максимального золота: Используйте вложенные циклы для каждой ячейки в сетке, чтобы найти максимальное количество золота, начиная с этой ячейки, с помощью функции dfsBacktrack. Обновите maxGold при нахождении лучшего пути. Верните maxGold. 😎 Решение:
class Solution:
def getMaximumGold(self, grid):
def dfsBacktrack(grid, rows, cols, row, col):
if row < 0 or col < 0 or row >= rows or col >= cols or grid[row][col] == 0:
return 0
originalVal = grid[row][col]
grid[row][col] = 0
maxGold = 0
for dr, dc in directions:
maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row + dr, col + dc))
grid[row][col] = originalVal
return maxGold + originalVal
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
rows, cols = len(grid), len(grid[0])
maxGold = 0
for row in range(rows):
for col in range(cols):
maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row, col))
return maxGold9 163
+3
Продвижение в Telegram с помощью Яндекс Директа
⚡Запустите продвижение в телеграм-каналах и привлекайте целевую аудиторию
📱 Таргетинг по тематикам, регионам и каналам в Telegram
Попробовать
#реклама
yandex.ru
О рекламодателе
9 163
Задача: 1273. Delete Tree Nodes
Сложность: medium
Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.
Пример:
Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1] Output: 2👨💻 Алгоритм: 1⃣Постройте дерево из заданных узлов, значений и родителей. 2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю. 3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов. 😎 Решение:
def deleteTreeNodes(nodes, parent, value):
from collections import defaultdict, deque
tree = defaultdict(list)
for i in range(nodes):
if parent[i] != -1:
tree[parent[i]].append(i)
def dfs(node):
total_sum = value[node]
total_count = 1
for child in tree[node]:
child_sum, child_count = dfs(child)
total_sum += child_sum
total_count += child_count
if total_sum == 0:
return 0, 0
return total_sum, total_count
return dfs(0)[1]9 163
Бесплатный курс по дизайну: веб, графический и UX/UI
Получи востребованные навыки:
- создание дизайна сайтов и приложений
- создание инфографики и карточек для маркетплейсов
- работа в графическом редакторе Figma и др.
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Зарегистрироваться
#реклама 16+
ydaev.ru
О рекламодателе
9 163
Задача: 684. Redundant Connection
Сложность: medium
В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.
Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.
Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]class Solution:
def __init__(self):
self.seen = set()
self.MAX_EDGE_VAL = 1000
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
graph = [[] for _ in range(self.MAX_EDGE_VAL + 1)]
for edge in edges:
self.seen.clear()
if graph[edge[0]] and graph[edge[1]] and self.dfs(graph, edge[0], edge[1]):
return edge
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
return []
def dfs(self, graph: List[List[int]], source: int, target: int) -> bool:
if source not in self.seen:
self.seen.add(source)
if source == target:
return True
for nei in graph[source]:
if self.dfs(graph, nei, target):
return True
return False9 163
Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля
Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰
Научись ей бесплатно!
- Бесплатный доступ
- Разбор ДЗ от наставника
- Мощные кейсы в портфолио
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
9 163
Задача: 814. Binary Tree Pruning
Сложность: medium
Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.
Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.
Пример:
Input: root = [1,null,0,0,1] Output: [1,null,0,null,1] Explanation: Only the red nodes satisfy the property "every subtree not containing a 1". The diagram on the right represents the answer.👨💻 Алгоритм: 1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу. 2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null. 3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево. 😎 Решение:
class Solution:
def pruneTree(self, root):
def containsOne(node):
if not node:
return False
leftContainsOne = containsOne(node.left)
rightContainsOne = containsOne(node.right)
if not leftContainsOne:
node.left = None
if not rightContainsOne:
node.right = None
return node.val == 1 or leftContainsOne or rightContainsOne
return root if containsOne(root) else None9 163
Задача: 30. Substring with Concatenation of All Words
Сложность: hard
Вам дана строка s и массив строк-слов. Все строки-слова имеют одинаковую длину.
Объединенная строка - это строка, которая точно содержит все строки из любой перестановки слов, которые были объединены.
Например, если
words = ["ab", "cd","ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются связанными строками. "acdbef" не является объединенной строкой, потому что это не объединение какой-либо перестановки слов.
Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.
Пример:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]👨💻 Алгоритм: 1️⃣Создаем словарь с подсчетом количества слов в
words.
2️⃣Проходим по строке s, проверяя подстроки длины, равной len(words) * len(words[0]).
3️⃣Проверяем, содержит ли подстрока все слова из words в нужном количестве.
😎 Решение:
from collections import defaultdict
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
word_count = defaultdict(int)
for word in words:
word_count[word] += 1
substr_len = len(words) * len(words[0])
word_len = len(words[0])
result = []
for i in range(len(s) - substr_len + 1):
seen = defaultdict(int)
for j in range(i, i + substr_len, word_len):
word = s[j:j+word_len]
if word in word_count:
seen[word] += 1
if seen[word] > word_count[word]:
break
else:
break
else:
result.append(i)
return result9 163
Надежные VDS-сервера в NetAngels от 73₽/месяц
Подберем мощные VDS-сервер для любых задач. Техподдержка 24/7. Защита от DDoS-атак. Гибкая конфигурация. Бесплатный перенос VDS с сохранением всех данных.
Выбери тариф под свои задачи:
Старт (Для низкой нагрузки: хранение файлов, раздача статики и простые веб-проекты)
Оптима (NVMe-диски для высокой скорости и баланс цены и производительности)
Турбо (Элитный VDS на базе топового оборудования с высокочастотными процессорами)
Про (Мощный VDS с гарантированными ресурсами для масштабных проектов)
ТурбоПро (VDS уровня enterprise с гарантированными ядрами и высокочастотными процессорами)
Ультра (Высокопроизводительный VDS для ресурсоемких проектов и корпоративных систем. В тариф включена поддержка GPU)
Попробуйте VDS-сервер от NetAngels!
Перейти на сайт
#реклама 16+
netangels.ru
О рекламодателе
9 163
Задача: 647. Palindromic Substrings
Сложность: medium
Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.
Пример:
Input: s = "abc" Output: 3👨💻 Алгоритм: 1⃣Инициализируйте счетчик для подсчета палиндромных подстрок. 2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины. 3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется. 😎 Решение:
def countSubstrings(s):
def expandAroundCenter(left, right):
count = 0
while left >= 0 and right < len(s) and s[left] == s[right]:
count += 1
left -= 1
right += 1
return count
total_count = 0
for i in range(len(s)):
total_count += expandAroundCenter(i, i) # For odd length palindromes
total_count += expandAroundCenter(i, i + 1) # For even length palindromes
return total_count9 163
Зарплата 207.000р у Middle-разработчика в Яндекс
«В день уходит несколько часов на созвоны, в остальное время закрываю задачки из спринта, редко перерабатываю. У компании топовый офис, но с коллективом как-то не заладилось. Радуюсь классному ДМС и стабильной зарплате» - middle разработчик из Яндекса.
Бигтех по-русски - канал с реальными зарплатами и историями IT-специалистов российского БигТеха. Там уже опубликованы рассказы программистов Альфа-банка, Сбера и Тинькофф 🤯
Читайте: @bigtech_russia
9 163
Новинка Gipopo! Готовые блюда для тех, кто учится жевать
Неизмельчённая еда в удобных тарелочках, которую осталось только разогреть в микроволновке – идеальное решение для малышей с 12 месяцев!
Узнать больше
#реклама
gipopo-baby.ru
О рекламодателе
9 163
Задача: 465. Optimal Account Balancing
Сложность: medium
Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.
Верните минимальное количество транзакций, необходимых для урегулирования долгов.
Пример:
Input: transactions = [[0,1,10],[2,0,5]] Output: 2👨💻 Алгоритм: 1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека. 2⃣Собрать все ненулевые чистые балансы в массив balance_list. 3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]: Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1. Если cur = n, вернуть 0. В противном случае установить cost на большое значение, например, inf. Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0, Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur]. Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1). Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат). Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации. Вернуть cost, когда итерация завершена. Вернуть dfs(0). 😎 Решение:
class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
from collections import defaultdict
credit_map = defaultdict(int)
for t in transactions:
credit_map[t[0]] += t[2]
credit_map[t[1]] -= t[2]
credit_list = [amount for amount in credit_map.values() if amount != 0]
n = len(credit_list)
def dfs(cur):
while cur < n and credit_list[cur] == 0:
cur += 1
if cur == n:
return 0
cost = float('inf')
for nxt in range(cur + 1, n):
if credit_list[nxt] * credit_list[cur] < 0:
credit_list[nxt] += credit_list[cur]
cost = min(cost, 1 + dfs(cur + 1))
credit_list[nxt] -= credit_list[cur]
return cost
return dfs(0)