Python | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Показати більше
Сітка:8 959
Підписники
-424 години
-327 днів
-10530 днів
Архів дописів
8 959
Задача: 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]8 959
Как IT-компании увеличить продажи с помощью вебинаров?
Делимся гайдом для маркетологов IT-компаний с рекомендациями ведущих российских разработчиков и экспертов МТС Линк.
Вы узнаете:
- Как правильно использовать онлайн-мероприятия для продвижения;
- Как собрать 10 000 потенциальных клиентов из любой точки мира в одном месте;
- Как увеличить узнаваемость бренда и создать комьюнити вокруг него;
- Как оценить вклад онлайн-мероприятия в продвижение компании и правильно обработать лиды;
Бонус: кейс IT-компании с доходимостью до вебинаров 70%
Получите методичку бесплатно на сайте!
Скачать
#реклама 16+
mts-link.ru
О рекламодателе
8 959
Задача: 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 medians8 959
Задача: 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 maxGold8 959
+3
Продвижение в Telegram с помощью Яндекс Директа
⚡Запустите продвижение в телеграм-каналах и привлекайте целевую аудиторию
📱 Таргетинг по тематикам, регионам и каналам в Telegram
Попробовать
#реклама
yandex.ru
О рекламодателе
8 959
Задача: 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]8 959
Бесплатный курс по дизайну: веб, графический и UX/UI
Получи востребованные навыки:
- создание дизайна сайтов и приложений
- создание инфографики и карточек для маркетплейсов
- работа в графическом редакторе Figma и др.
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Зарегистрироваться
#реклама 16+
ydaev.ru
О рекламодателе
8 959
Задача: 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 False8 959
Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля
Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰
Научись ей бесплатно!
- Бесплатный доступ
- Разбор ДЗ от наставника
- Мощные кейсы в портфолио
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
8 959
Задача: 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 None8 959
Задача: 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 result8 959
Надежные VDS-сервера в NetAngels от 73₽/месяц
Подберем мощные VDS-сервер для любых задач. Техподдержка 24/7. Защита от DDoS-атак. Гибкая конфигурация. Бесплатный перенос VDS с сохранением всех данных.
Выбери тариф под свои задачи:
Старт (Для низкой нагрузки: хранение файлов, раздача статики и простые веб-проекты)
Оптима (NVMe-диски для высокой скорости и баланс цены и производительности)
Турбо (Элитный VDS на базе топового оборудования с высокочастотными процессорами)
Про (Мощный VDS с гарантированными ресурсами для масштабных проектов)
ТурбоПро (VDS уровня enterprise с гарантированными ядрами и высокочастотными процессорами)
Ультра (Высокопроизводительный VDS для ресурсоемких проектов и корпоративных систем. В тариф включена поддержка GPU)
Попробуйте VDS-сервер от NetAngels!
Перейти на сайт
#реклама 16+
netangels.ru
О рекламодателе
8 959
Задача: 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_count8 959
Зарплата 207.000р у Middle-разработчика в Яндекс
«В день уходит несколько часов на созвоны, в остальное время закрываю задачки из спринта, редко перерабатываю. У компании топовый офис, но с коллективом как-то не заладилось. Радуюсь классному ДМС и стабильной зарплате» - middle разработчик из Яндекса.
Бигтех по-русски - канал с реальными зарплатами и историями IT-специалистов российского БигТеха. Там уже опубликованы рассказы программистов Альфа-банка, Сбера и Тинькофф 🤯
Читайте: @bigtech_russia
8 959
Новинка Gipopo! Готовые блюда для тех, кто учится жевать
Неизмельчённая еда в удобных тарелочках, которую осталось только разогреть в микроволновке – идеальное решение для малышей с 12 месяцев!
Узнать больше
#реклама
gipopo-baby.ru
О рекламодателе
8 959
Задача: 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)8 959
Найти свое место, место у моря
В современном ритме жизни очень легко потерять себя и свой ориентир. Мир диктует нам все новые правила, и за ними мы можем перестать слышать себя. Чего хотите для себя Вы? В чем Ваше предназначение? Где Ваш путь?
Где Ваше место? Вы его выбираете, или место выбирает Вас?
Найти себя вы можете в
ЖК Резиденция Морей - быть на своем месте, месте у моря.
Узнать больше
#реклама
ssk-rezidenciya-morey.ru
О рекламодателе
8 959
Задача: 715. Range Module
Сложность: hard
Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).
Пример:
Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8👨💻 Алгоритм: 1⃣Инициализируйте класс RangeModule с пустым списком диапазонов. 2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах. 3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части. 😎 Решение:
class RangeModule:
def __init__(self):
self.ranges = []
def addRange(self, left, right):
new_ranges = []
i = 0
while i < len(self.ranges) and self.ranges[i][1] < left:
new_ranges.append(self.ranges[i])
i += 1
while i < len(self.ranges) and self.ranges[i][0] <= right:
left = min(left, self.ranges[i][0])
right = max(right, self.ranges[i][1])
i += 1
new_ranges.append((left, right))
while i < len(self.ranges):
new_ranges.append(self.ranges[i])
i += 1
self.ranges = new_ranges
def queryRange(self, left, right):
for l, r in self.ranges:
if l <= left and right <= r:
return True
return False
def removeRange(self, left, right):
new_ranges = []
for l, r in self.ranges:
if l < left:
new_ranges.append((l, min(r, left)))
if right < r:
new_ranges.append((max(l, right), r))
self.ranges = new_ranges8 959
Telegram опубликовал список 8 самых быстрорастущих каналов для программистов:
Only Python — Подборки приёмов и фич, о которых не рассказывают в курсах.
Only Tech — Главные тренды и инсайды из мира технологий, маркетинга и интернет-культуры.
Only Hack — Реальные кейсы кибератак, инструменты и методы защиты, которые используют хакеры.
Only GitHub — Репозитории, которые решают реальные задачи.
Скрипты, фреймворки и готовые решения
Only IT — Без мнений и слухов — только факты и важные IT-события.
Only Apple — Новые апдейты, утечки и фишки, которые Apple ещё не показала.
Only GPT — Промпты, хаки и свежие инструменты, о которых молчат даже AI-каналы.
Only Memes — Если ты когда-нибудь деплоил в пятницу вечером — ты поймешь
Подписывайтесь и прокачивайте свои скиллы.
8 959
Изучите HTML и CSS - бесплатно!
Попробуйте бесплатно — освоите базу HTML & CSS, создадите свою первую веб страницу и поймете, стоит ли погружаться в IT глубже.
Почему стоит попробовать?
- Никакой воды — только практика
- Проверь профессию до того, как вложить в обучение 150+ тыс.
- Убедитесь, что код — это не страшно, даже если раньше не получалось
А чтобы у вас все получилось, мы добавили бонусы:
✅ 8 пошаговых гайдов — от первого кода до первых заработков в IT.
✅ До 1500 монет за задания, которые можно обменять на дальнейшее обучение.
✅ Закрытый чат с наставником — получите ответы на все вопросы.
✅ Полезный IT-канал в Telegram — оставайтесь в теме после курса.
⚡ Главное — вы попробуете профессию разработчика!
Попробовать
#реклама 16+
learn.result-university.com
О рекламодателе
