Вже доступно! Дослідження Telegram за 2025 — головні інсайти року 
Python | LeetCode
Відкрити в Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+20tRfhrwPpM4NDQy Вопросы собесов t.me/+cnJC0_ZeZ_I0OGY6 Вакансии t.me/+cXGKkrOY2-w3ZTky
Показати більше9 394
Підписники
-524 години
-147 днів
-5930 день
Архів дописів
9 394
#medium
Задача: 261. Graph Valid Tree
У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.
Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.
Пример:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true👨💻 Алгоритм: 1️⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false. 2️⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0. 3️⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false. 😎 Решение:
import collections
from typing import List
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
adj_list = [[] for _ in range(n)]
for A, B in edges:
adj_list[A].append(B)
adj_list[B].append(A)
parent = {0: -1}
queue = collections.deque([0])
while queue:
node = queue.popleft()
for neighbour in adj_list[node]:
if neighbour == parent[node]:
continue
if neighbour in parent:
return False
parent[neighbour] = node
queue.append(neighbour)
return len(parent) == n9 394
#medium
Задача: 260. Single Number III
Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает за линейное время и использует только постоянное дополнительное пространство..
Пример:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.👨💻 Алгоритм: 1️⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел. 2️⃣Найдите бит, который отличается в этих двух числах, чтобы разделить все числа в массиве на две группы. 3️⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа. 😎 Решение:
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for num in nums:
xor ^= num
diff = xor & -xor
res = [0, 0]
for num in nums:
if num & diff == 0:
res[0] ^= num
else:
res[1] ^= num
return res9 394
9 394
#medium
Задача: 259. 3Sum Smaller
Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.
Пример:
Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3]👨💻 Алгоритм: 1️⃣Отсортируйте массив nums. 2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения. 3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар. 😎 Решение:
class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
nums.sort()
sum_count = 0
for i in range(len(nums) - 2):
sum_count += self.twoSumSmaller(nums, i + 1, target - nums[i])
return sum_count
def twoSumSmaller(self, nums: List[int], startIndex: int, target: int) -> int:
sum_count = 0
for i in range(startIndex, len(nums) - 1):
j = self.binarySearch(nums, i, target - nums[i])
sum_count += j - i
return sum_count
def binarySearch(self, nums: List[int], startIndex: int, target: int) -> int:
left, right = startIndex, len(nums) - 1
while left < right:
mid = (left + right + 1) // 2
if nums[mid] < target:
left = mid
else:
right = mid - 1
return left9 394
#easy
Задача: 258. Add Digits
Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.
Пример:
Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it.👨💻 Алгоритм: 1️⃣Инициализируйте переменную digital_root значением 0. 2️⃣В цикле, пока num больше 0: Добавьте к digital_root последнюю цифру num. Уменьшите num, удалив последнюю цифру. Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0. 3️⃣Верните значение digital_root. 😎 Решение:
class Solution:
def addDigits(self, num: int) -> int:
digital_root = 0
while num > 0:
digital_root += num % 10
num //= 10
if num == 0 and digital_root > 9:
num = digital_root
digital_root = 0
return digital_root9 394
Форум Управление данными 2024, 26 сентября
Стратегия, инструменты, опыт.
Центральное событие года. Все о данных. Перенастройка в новой реальности
Зарегистрироваться
#реклама
osp.ru
О рекламодателе
9 394
#easy
Задача: 257. Binary Tree Paths
Дано корневое дерево, верните все пути от корня до листа в любом порядке.
Лист — это узел без детей.
Пример:
Input: root = [1,2,3,null,5] Output: ["1->2->5","1->3"]👨💻 Алгоритм: 1️⃣Если текущий узел не является null, добавьте его значение к текущему пути. Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей. Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов. 2️⃣Начните с корневого узла, пустого пути и пустого списка путей. 3️⃣Верните список всех путей от корня до листа. 😎 Решение:
class Solution:
def construct_paths(self, root: TreeNode, path: str, paths: List[str]):
if root:
path += str(root.val)
if not root.left and not root.right:
paths.append(path)
else:
path += "->"
self.construct_paths(root.left, path, paths)
self.construct_paths(root.right, path, paths)
def binaryTreePaths(self, root: TreeNode) -> List[str]:
paths = []
self.construct_paths(root, "", paths)
return paths9 394
#medium
Задача: 256. Paint House
Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет.
Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3.
Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее...
Верните минимальную стоимость покраски всех домов.
Пример:
Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.👨💻 Алгоритм: 1️⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2]. 2️⃣Для каждого дома i от 1 до n-1 обновите значения массива dp: dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) 3️⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]). 😎 Решение:
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
n = len(costs)
dp = [[0] * 3 for _ in range(n)]
dp[0] = costs[0]
for i in range(1, n):
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])
return min(dp[n-1][0], dp[n-1][1], dp[n-1][2])9 394
Яндекс Заправки для бизнеса. Скидка до 3%. Без комиссий
Управляйте заправками сотрудников с экономией на топливе.
Возмещайте до 20% от стоимости топлива через возврат НДС.
Получайте закрывающие документы в электронном виде.
Еще удобнее с мобильным приложением.
Узнать больше
#реклама 16+
business.go.yandex
О рекламодателе
9 394
#medium
Задача: 213. House Robber II
Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятано определенное количество денег. Все дома в этом месте расположены по кругу, что означает, что первый дом является соседом последнего. Между тем, в соседних домах установлена охранная система, которая автоматически свяжется с полицией, если два соседних дома будут взломаны в одну ночь.
Дан массив целых чисел nums, представляющий количество денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не вызвав полицию.
Пример:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.👨💻 Алгоритм: 1️⃣ Обработка базовых случаев: Если массив nums пуст, возвращаем 0. Если в массиве nums только один дом, возвращаем значение этого дома. 2️⃣ Разделение задачи на две подзадачи: Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию rob_simple с параметрами 0 и len(nums) - 2. Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и len(nums) - 1. 3️⃣ Сравнение результатов и возврат максимального значения: Возвращаем максимальное значение из двух полученных результатов. 😎 Решение:
class Solution:
def rob(self, nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
max1 = self.rob_simple(nums, 0, len(nums) - 2)
max2 = self.rob_simple(nums, 1, len(nums) - 1)
return max(max1, max2)
def rob_simple(self, nums, start, end):
t1, t2 = 0, 0
for i in range(start, end + 1):
temp = t1
current = nums[i]
t1 = max(current + t2, t1)
t2 = temp
return t19 394
Налоговый мониторинг: что изменилось в 2024 году
Налоговая приняла поправки, обязательные для всех участников мониторинга.
Подключение к информационной системе «Налог 3» и новые формы документов - далеко не полный список изменений, с которыми предстоит столкнуться бизнесу.
Рассказываем обо всех нововведениях этого года. Читайте статью, чтобы узнать:
✅ Какие компании могут подключиться к мониторингу по льготным условиям.
✅ Какие новые формы для подключения доступны с 2024 года.
✅ Как соблюсти все новые требования и ничего не упустить.
Узнать больше
#реклама
tech.vk.com
О рекламодателе
9 394
#hard
Задача: 212. Word Search II
Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.
Каждое слово должно быть составлено из букв последовательных смежных ячеек, где смежные ячейки находятся по горизонтали или вертикали рядом. Одна и та же ячейка с буквой не может использоваться более одного раза в слове.
Пример:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat","oath"]👨💻 Алгоритм: 1️⃣ Построение Trie: Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже. 2️⃣ Запуск обхода в глубину (Backtracking) с каждой ячейки: Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell). 3️⃣ Обход соседних ячеек: В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell). На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале. 😎 Решение:
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
WORD_KEY = "$"
trie = {}
for word in words:
node = trie
for letter in word:
node = node.setdefault(letter, {})
node[WORD_KEY] = word
rowNum = len(board)
colNum = len(board[0])
matchedWords = []
def backtracking(row, col, parent):
letter = board[row][col]
currNode = parent[letter]
word_match = currNode.pop(WORD_KEY, False)
if word_match:
matchedWords.append(word_match)
board[row][col] = "#"
for rowOffset, colOffset in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
newRow, newCol = row + rowOffset, col + colOffset
if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
continue
if board[newRow][newCol] not in currNode:
continue
backtracking(newRow, newCol, currNode)
board[row][col] = letter
if not currNode:
parent.pop(letter)
for row in range(rowNum):
for col in range(colNum):
if board[row][col] in trie:
backtracking(row, col, trie)
return matchedWords9 394
Обучаем Java-разработчиков оплата после выхода на работу
В Kata Academy можно выучиться на Java-разработчика бесплатно, а заплатить уже после трудоустройства по специальности из фактической зарплаты.
Если задуматься, то все в выигрыше:
— ты получаешь работу в Москве или Санкт-Петербурге с хорошей зарплатой, мы получаем процент за инвестиции в тебя;
— в наших интересах научить тебя так, чтобы твоя зарплата была как можно выше;
— мы прокачиваем твои навыки еще 2 года после курса: проводим выездные мероприятия и мастер-классы — и доходы наших выпускников растут;
— мы не зависим от банков и их рассрочек — кризис не повлиял на доступность курсов.
Чтобы попасть на курс, нужно выполнить небольшое тестовое задание. Переходи по ссылке и оставляй заявку!
Узнать больше
#реклама 16+
kata.academy
О рекламодателе
9 394
#medium
Задача: 211. Design Add and Search Words Data Structure
Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову.
Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.
Пример:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
👨💻 Алгоритм:
1️⃣ Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.
2️⃣ Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.
3️⃣ Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.
😎 Решение:
class WordDictionary:
def __init__(self):
self.trie = {}
def addWord(self, word: str) -> None:
node = self.trie
for ch in word:
if ch not in node:
node[ch] = {}
node = node[ch]
node["$"] = True
def search(self, word: str) -> bool:
def search_in_node(word, node) -> bool:
for i, ch in enumerate(word):
if ch not in node:
if ch == ".":
for x in node:
if x != "$" and search_in_node(word[i + 1:], node[x]):
return True
return False
else:
node = node[ch]
return "$" in node
return search_in_node(word, self.trie)9 394
Запустите рекламу в телеграм-каналах с Яндекс Директом
Перфоманс-реклама теперь в телеграм-каналах ⚡
Яндекс Директ знает, как привлечь целевую аудиторию 💰👌
Попробовать
#реклама
yandex.ru
О рекламодателе
9 394
#medium
Задача: 255. Verify Preorder Sequence in Binary Search Tree
Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.
Пример:
Input: preorder = [5,2,1,3,6] Output: true👨💻 Алгоритм: 1️⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек. 2️⃣Итерируйте по массиву preorder. Для каждого num: Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit. Если num <= minLimit, верните false. Добавьте num в стек. 3️⃣Верните true, если удалось пройти весь массив. 😎 Решение:
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
minLimit = float('-inf')
stack = []
for num in preorder:
while stack and stack[-1] < num:
minLimit = stack.pop()
if num <= minLimit:
return False
stack.append(num)
return True9 394
+9
Помощь в трудоустройстве в IT-сфере!
По всей России объявили бесплатную программу на шестимесячное обучение по IT-cпециальностям.
Запись на участие в программе продлится до конца июля, но чтобы туда попасть, нужно пройти специальный профтест.
По результату тестирования сразу узнаете, какая профессия вам подойдет, и проходите ли вы на бесплатное обучение.
Перейти на сайт
#реклама 16+
urban-university.ru
О рекламодателе
9 394
#medium
Задача: 253. Meeting Rooms II
Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.
Пример:
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2👨💻 Алгоритм: 1️⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи. 2️⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче): Если свободна, обновите время окончания этой комнаты. Если не свободна, добавьте новое время окончания в кучу. 3️⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат. 😎 Решение:
import heapq
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[0])
heap = [intervals[0][1]]
for i in range(1, len(intervals)):
if intervals[i][0] >= heap[0]:
heapq.heapreplace(heap, intervals[i][1])
else:
heapq.heappush(heap, intervals[i][1])
return len(heap)9 394
ТОП-4 Курса по Data Science
Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов.
🎓Освойте продвинутую математику с самых азов
💻Научитесь создавать ML-модели и работать с нейронными сетями
✅Получите реальный опыт на практических проектах
🏠Начните работать удаленно
💰Подарок в конце подборки!
Выбрать
#реклама 16+
tutortop.ru
О рекламодателе
9 394
#easy
Задача: 252. Meeting Rooms
Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи.
Пример:
Input: intervals = [[0,30],[5,10],[15,20]] Output: false👨💻 Алгоритм: 1️⃣Создайте функцию для проверки перекрытия двух интервалов: Возвращайте true, если начало одного интервала находится внутри другого интервала. 2️⃣Проверьте каждый интервал с каждым другим интервалом: Если найдено перекрытие, верните false. 3️⃣Если все интервалы проверены и перекрытий не найдено, верните true. 😎 Решение:
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
def overlap(interval1: List[int], interval2: List[int]) -> bool:
return (interval1[0] >= interval2[0] and interval1[0] < interval2[1]
or interval2[0] >= interval1[0] and interval2[0] < interval1[1])
for i in range(len(intervals)):
for j in range(i + 1, len(intervals)):
if overlap(intervals[i], intervals[j]):
return False
return True