Python | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
إظهار المزيد
8 922
المشتركون
-524 ساعات
-477 أيام
-12930 أيام
أرشيف المشاركات
8 922
#medium
Задача: 117. Populating Next Right Pointers in Each Node II
Вам дано бинарное дерево:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.
Изначально все указатели next установлены в NULL.
Пример:
Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.👨💻 Алгоритм: 1️⃣Инициализируйте очередь Q, которая будет использоваться во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда дело доходит до определения уровня конкретного узла. Можно добавить в очередь пару (узел, уровень), и каждый раз, когда мы добавляем детей узла, мы добавляем (node.left, parent_level+1) и (node.right, parent_level+1). Этот подход может оказаться неэффективным для нашего алгоритма, так как нам нужны все узлы на одном уровне, и потребуется дополнительная структура данных. 2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня - использовать разграничение между уровнями. Обычно мы вставляем в очередь элемент NULL, который обозначает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого объема памяти, пропорционального количеству уровней в дереве. 3️⃣Подход, который мы будем использовать, предполагает структуру вложенных циклов, чтобы обойти необходимость NULL указателя. По сути, на каждом шаге мы фиксируем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и больше ничего. К тому времени, как мы закончим обработку заданного количества элементов, в очереди окажутся все узлы следующего уровня. Вот псевдокод для этого:
while (!Q.empty())
{
size = Q.size()
for i in range 0..size
{
node = Q.pop()
Q.push(node.left)
Q.push(node.right)
}
}
Мы начинаем с добавления корня дерева в очередь. Так как на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.
😎 Решение:
class Solution:
def connect(self, root: Optional["Node"]) -> Optional["Node"]:
if not root:
return root
Q = collections.deque([root])
while Q:
size = len(Q)
for i in range(size):
node = Q.popleft()
if i < size - 1:
node.next = Q[0]
if node.left:
Q.append(node.left)
if node.right:
Q.append(node.right)
return root8 922
Как запустить собственный пет-проект и зарабатывать на нём зарплату senior-разработчика?
На этом канале мы решаем сложные задачи, которые часто попадаются на собеседованиях. Но что, если перевернуть игру и вместо работы на кого-то запустить собственный пет-проект, который будет приносить деньги?
Александр Рогачев запустил телеграм-канал Indie Hackers, где рассказывает про пет-проекты, которые приносят стабильный доход своим создателям. Без венчурных инвестиций, без бизнес-планов и команды. Разве такое возможно? Да!
Несколько примеров:
Агрегатор вакансий c доходом в 4000$ / месяц
Плагин для Chrome с доходом 20000₽ / месяц
Если вы в поиске свежих идей, которые могут обеспечить стабильный пассивных доход, подписывайтесь на канал Indie Hackers. Уверен, что там вы найдёте то самое, что зажгёт огонь в вашем сердце.
8 922
ТОП-4 Курса по Программированию
⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов.
✅Хотите стать программистом, но не знаете с какого языка начать?
Помогаем разобраться в самых популярных и востребованных языках программирования.
Подарок в конце подборки!
Выбрать
#реклама 16+
tutortop.ru
О рекламодателе
8 922
#medium
Задача: 116. Populating Next Right Pointers in Each Node
Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}next так, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.
Изначально все указатели next установлены в NULL.
Пример:
Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.👨💻 Алгоритм: 1️⃣Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных. 2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня заключается в использовании некоторой разграничительной метки между уровнями. Обычно мы вставляем в очередь элемент NULL, который отмечает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого количества памяти, пропорционально количеству уровней в дереве. 3️⃣Подход, который мы будем использовать здесь, будет иметь структуру вложенных циклов, чтобы обойти необходимость указателя NULL. По сути, на каждом шаге мы записываем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и не более. К моменту, когда мы закончим обработку заданного количества элементов, в очереди будут все узлы следующего уровня. Вот псевдокод для этого:
while (!Q.empty())
{
size = Q.size()
for i in range 0..size
{
node = Q.pop()
Q.push(node.left)
Q.push(node.right)
}
}
Мы начинаем с добавления корня дерева в очередь. Поскольку на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.
😎 Решение:
import collections
class Solution:
def connect(self, root: "Node") -> "Node":
if not root:
return root
Q = collections.deque([root])
while Q:
size = len(Q)
for i in range(size):
node = Q.popleft()
if i < size - 1:
node.next = Q[0]
if node.left:
Q.append(node.left)
if node.right:
Q.append(node.right)
return root8 922
👩💻 Программирование теперь в телеграм!
Вот обширная база материалов, которая ежедневно обновляется, выбирай своё направление:
Обучение JavaScript с нуля
Обучение Python с нуля
Обучение Java с нуля
Обучение HTML/CSS с нуля
Обучение C/С++ с нуля
Обучение С# с нуля
Обучение SQL/GO/PHP с нуля
Обучение Kotlin/Swift с нуля
⛓ Архив на 3489ГБ: Курсы, книги, шпаргалки, статьи, видео, ресурсы — всё собрано в одном месте: @roadmap_ready
8 922
Чем полезно ИТ-обучение, кроме программмирования?
Только люди, прожившие 5 лет в глухом лесу, не слышали о том, что детей полезно учить цифровым навыкам еще с начальной школы.
Но в чём же она, эта несомненная, по мнению педагогов, польза?
Так ли уж необходимы все эти курсы?
Да и в чем практический смысл таких знаний для повседневной жизни?
😊Вот это не ясно!
Давайте разберёмся!
8 августа в 19:00 по МСК на бесплатной встрече педагоги из ИТ-школы Университета Иннополис готовы рассказать
💻где дети могут применять ИТ-навыки ежедневно,
🏃♂️какое преимущество появляется в будущем у детей, умеющих программировать,
📚зачем IT гуманитариям,
🎓как попробовать бесплатное обучение, чтоб понять, что ребенку это интересно и что занятия не будут заброшены через неделю.
Регистрируйтесь, тобы помочь своим детям стать успешными
Зарегистрироваться
#реклама
progmatica.innopolis.university
О рекламодателе
8 922
#hard
Задача: 115. Distinct Subsequences
"Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t.
Тестовые примеры сгенерированы таким образом, что ответ укладывается в 32-битное целое число со знаком."
Пример:
Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from s. rabbbit rabbbit rabbbit👨💻 Алгоритм: 1️⃣Определите функцию с названием recurse, которая принимает два целочисленных значения i и j. Первое значение представляет текущий обрабатываемый символ в строке S, а второе - текущий символ в строке T. Инициализируйте словарь под названием memo, который будет кэшировать результаты различных вызовов рекурсии.** 2️⃣Проверьте базовый случай. Если одна из строк закончилась, возвращается 0 или 1 в зависимости от того, удалось ли обработать всю строку T или нет. Есть ещё один базовый случай, который следует рассмотреть. Если оставшаяся длина строки S меньше, чем у строки T, то совпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и возвращается 0.** 3️⃣Затем проверяем, существует ли текущая пара индексов в нашем словаре. Если да, то просто возвращаем сохранённое/кэшированное значение. Если нет, то продолжаем обычную обработку. Сравниваем символы s[i] и t[j]. Сохраняем результат вызова recurse(i + 1, j) в переменную. Как упоминалось ранее, результат этой рекурсии необходим, независимо от совпадения символов. Если символы совпадают, добавляем к переменной результат вызова recurse(i + 1, j + 1). Наконец, сохраняем значение этой переменной в словаре с ключом (i, j) и возвращаем это значение в качестве ответа. 😎 Решение:
class Solution:
def numDistinct(self, s: str, t: str) -> int:
memo = {}
def uniqueSubsequences(i: int, j: int) -> int:
M, N = len(s), len(t)
if i == M or j == N or M - i < N - j:
return int(j == len(t))
if (i, j) in memo:
return memo[i, j]
ans = uniqueSubsequences(i + 1, j)
if s[i] == t[j]:
ans += uniqueSubsequences(i + 1, j + 1)
memo[i, j] = ans
return ans
return uniqueSubsequences(0, 0)8 922
Обучаем Java-разработчиков оплата после выхода на работу
В Kata Academy можно выучиться на Java-разработчика бесплатно, а заплатить уже после трудоустройства по специальности из фактической зарплаты.
Если задуматься, то все в выигрыше:
— ты получаешь работу в Москве или Санкт-Петербурге с хорошей зарплатой, мы получаем процент за инвестиции в тебя;
— в наших интересах научить тебя так, чтобы твоя зарплата была как можно выше;
— мы прокачиваем твои навыки еще 2 года после курса: проводим выездные мероприятия и мастер-классы — и доходы наших выпускников растут;
— мы не зависим от банков и их рассрочек — кризис не повлиял на доступность курсов.
Чтобы попасть на курс, нужно выполнить небольшое тестовое задание. Переходи по ссылке и оставляй заявку!
Узнать больше
#реклама 16+
kata.academy
О рекламодателе
8 922
#Medium
Задача: 114. Flatten Binary Tree to Linked List
"Связный список" должен использовать тот же класс TreeNode, где указатель на правого ребенка указывает на следующий узел в списке, а указатель на левого ребенка всегда равен null.
"Связный список" должен быть в том же порядке, что и обход бинарного дерева в прямом порядке.
Пример:
Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]👨💻 Алгоритм: 1️⃣Плоское преобразование дерева: Рекурсивно преобразуем левое и правое поддеревья заданного узла, сохраняя соответствующие конечные узлы в leftTail и rightTail. 2️⃣Установка соединений: Если у текущего узла есть левый ребенок, выполняем следующие соединения: leftTail.right = node.right node.right = node.left node.left = None 3️⃣Возврат конечного узла: Возвращаем rightTail, если у узла есть правый ребенок, иначе возвращаем leftTail. 😎 Решение:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def flattenTree(self, node: TreeNode) -> TreeNode:
if not node:
return None
if not node.left and not node.right:
return node
leftTail = self.flattenTree(node.left)
rightTail = self.flattenTree(node.right)
if leftTail:
leftTail.right = node.right
node.right = node.left
node.left = None
return rightTail if rightTail else leftTail
def flatten(self, root: TreeNode) -> None:
self.flattenTree(root)8 922
🌊 Водоворот знаний в Кодовороте
🤿 Погружайся в мир лучших видео уроков по программированию. Каждый день на канале выходит полезный контент. Кодируй своё будущее вместе с нами!
⛓ Подпишись
8 922
Дизайн в FIGMA с нуля. Бесплатный курс + портфолио
Онлайн-программа с наставником и чатом. Дизайн от профессионалов. Доступ 0 руб.
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
8 922
#Medium
Задача: 113. Path Sum II
Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листа, где сумма значений узлов в пути равна targetSum. Каждый путь должен быть возвращён как список значений узлов, а не ссылок на узлы.
Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.
Пример:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]] Explanation: There are two paths whose sum equals targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22👨💻 Алгоритм: 1️⃣Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке. 2️⃣Проверка условий: На каждом шаге проверяется, равна ли оставшаяся сумма значению текущего узла. Если это так и текущий узел является листом, текущий путь (pathNodes) добавляется в итоговый список путей, который должен быть возвращен. 3️⃣Обработка всех ветвей: Учитывая, что значения узлов могут быть отрицательными, необходимо исследовать все ветви дерева до самых листьев, независимо от текущей суммы по пути. 😎 Решение:
class TreeNode:
def __init__(self, x: int) -> None:
self.val = x
self.left = None
self.right = None
class Solution:
def recurseTree(
self,
node: TreeNode,
remainingSum: int,
pathNodes: List[int],
pathsList: List[List[int]],
) -> None:
if not node:
return
pathNodes.append(node.val)
if remainingSum == node.val and not node.left and not node.right:
pathsList.append(list(pathNodes))
else:
self.recurseTree(
node.left, remainingSum - node.val, pathNodes, pathsList
)
self.recurseTree(
node.right, remainingSum - node.val, pathNodes, pathsList
)
pathNodes.pop()
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
pathsList = []
self.recurseTree(root, sum, [], pathsList)
return pathsList
8 922
Развивайте GameDev-индустрию в России
Университет Иннополис x Skillfactory запустили онлайн-магистратуру «Управление разработкой компьютерных игр».
Для вас:
📚 только те знания, навыки и задачи, с которыми вы столкнетесь в реальности
🏃♂️ тренажеры, тесты, домашние задания, проекты и хакатоны
🎓 все студенческие льготы и диплом магистра государственного образца
На первом году обучения узнаете, какие методы и инструменты используют для продюсирования. Погрузитесь в технические, юридические и финансовые аспекты разработки.
Второй год будете активно набираться опыта — разработаете игру в команде.
Все это — в формате онлайн, без переезда и паузы в карьере.
А с господдержкой стоимость обучения будет комфортной — от 390 рублей в месяц.
Подать заявку
#реклама 16+
new.skillfactory.ru
О рекламодателе
8 922
#easy
Задача: 112. Path Sum
Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum.
Лист — это узел без детей.
Пример:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown.👨💻 Алгоритм: 1️⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val. 2️⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом. 3️⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами. 😎 Решение:
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
de = [
(root, sum - root.val),
]
while de:
node, curr_sum = de.pop()
if not node.left and not node.right and curr_sum == 0:
return True
if node.right:
de.append((node.right, curr_sum - node.right.val))
if node.left:
de.append((node.left, curr_sum - node.left.val))
return False8 922
👨💻 Чтобы стать более востребованным перцем в IT индустрии неплохо бы знать английский.
Канал Hello Word в игровом стиле поможет улучшить твой English skill.
🤓У нас ты найдешь:
🟡 Тесты с пропуском слов
🟡 Мемы на английском
🟡 Полезные шпаргалки для изучения
😎 Расширяй свои навыки и покоряй начинай покорять западную индустрию.
Испытай свои знания и попробуй пройти тест.
8 922
#easy
Задача: 111. Minimum Depth of Binary Tree
Дано бинарное дерево, найдите его минимальную глубину.
Минимальная глубина - это количество узлов вдоль самого короткого пути от корневого узла до ближайшего листового узла.
Пример:
Input: root = [3,9,20,null,null,15,7] Output: 2👨💻 Алгоритм: 1️⃣Мы будем использовать метод обхода в глубину (dfs) с корнем в качестве аргумента. Базовое условие рекурсии: это для узла NULL, в этом случае мы должны вернуть 0. 2️⃣Если левый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для правого ребенка корневого узла, что равно 1 + dfs(root.right). 3️⃣Если правый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для левого ребенка корневого узла, что равно 1 + dfs(root.left). Если оба ребенка не являются NULL, тогда вернуть 1 + min(dfs(root.left), dfs(root.right)). 😎 Решение:
class Solution:
def minDepth(self, root):
def dfs(root):
if root is None:
return 0
if root.left is None:
return 1 + dfs(root.right)
elif root.right is None:
return 1 + dfs(root.left)
return 1 + min(dfs(root.left), dfs(root.right))
return dfs(root)8 922
ИИ для Расшифровки и Автопротоколирования переговоров
В один клик включайте запись совещаний в онлайне или переговорке и получайте результаты обсуждений в формате расшифровки и протокола с задачами с помощью искусственного интеллекта.
1. Получение качественной расшифровки, разбитой по спикерам.
2. Выделение краткого содержания совещания, основных решений и задач в виде резюме для составления протокола.
3. Хранение информации о прошедших собраниях и их результатах в архиве с возможностью удобного поиска.
Протестируйте бесплатно на своем совещании!
Попробовать
#реклама
timelist.ru
О рекламодателе
8 922
#easy
Задача: 110. Balanced Binary Tree
Дано бинарное дерево, определите, является ли оно
сбалансированным по высоте.
Пример:
Input: root = [3,9,20,null,null,15,7] Output: true👨💻 Алгоритм: 1️⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает: -1, если p является пустым поддеревом, т.е. null; 1 + max(height(p.left), height(p.right)) в противном случае. 2️⃣Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. Дерево T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы. 3️⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них: Если root == NULL, возвращаем true. Если abs(height(root.left) - height(root.right)) > 1, возвращаем false. В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right). 😎 Решение:
class Solution:
def height(self, root: TreeNode) -> int:
if not root:
return -1
return 1 + max(self.height(root.left), self.height(root.right))
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
return (
abs(self.height(root.left) - self.height(root.right)) < 2
and self.isBalanced(root.left)
and self.isBalanced(root.right)
)8 922
8 922
Такси для бизнеса. Яндекс Go
Оптимизируйте свои расходы и повысьте эффективность бизнеса с Яндекс Go
Узнать больше
#реклама
business.go.yandex
О рекламодателе
