Python | LeetCode

#medium Задача: 109. Convert Sorted List to Binary Search Tree Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска. Пример:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

👨‍💻 Алгоритм: 1️⃣Поскольку нам дан односвязный список, а не массив, у нас нет прямого доступа к элементам списка по индексам. Нам нужно определить средний элемент односвязного списка. Мы можем использовать подход с двумя указателями для нахождения среднего элемента списка. В основном, у нас есть два указателя: slow_ptr и fast_ptr. slow_ptr перемещается на один узел за раз, тогда как fast_ptr перемещается на два узла за раз. К тому времени, как fast_ptr достигнет конца списка, slow_ptr окажется в середине списка. Для списка с четным количеством элементов любой из двух средних элементов может стать корнем BST. 2️⃣Как только мы находим средний элемент списка, мы отсоединяем часть списка слева от среднего элемента. Мы делаем это, сохраняя prev_ptr, который указывает на узел перед slow_ptr, т.е. prev_ptr.next = slow_ptr. Для отсоединения левой части мы просто делаем prev_ptr.next = None. 3️⃣Для создания сбалансированного по высоте BST нам нужно передать только голову связанного списка в функцию, которая преобразует его в BST. Таким образом, мы рекурсивно работаем с левой половиной списка, передавая оригинальную голову списка, и с правой половиной, передавая slow_ptr.next в качестве головы. 😎 Решение:

class Solution:

    def findMiddle(self, head: ListNode) -> ListNode:
        prevPtr = None
        slowPtr = head
        fastPtr = head
        while fastPtr and fastPtr.next:
            prevPtr = slowPtr
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next
        if prevPtr:
            prevPtr.next = None
        return slowPtr

    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        mid = self.findMiddle(head)
        node = TreeNode(mid.val)
        if head == mid:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(mid.next)
        return node

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Нормально стартанули: STENOY запустили свой ЖК ARTEL Не прошло и года, как говорится! Про хорошее место в 6 мин. от «Преображенской площади» и отложенный спрос с локации говорили уже не раз. Продукт до получения РНС тоже прилично проработали. ✅ В квартирографии нет раздутых площадей: от 24,9 до 90 м2. Это плюс, потому что покупателю не придется переплачивать тупо за хотелки девелопера заработать побольше. ✅ Во дворе будет атриум, зоны для общего чила со столиками и шезлонгами, места для работы со встроенными беспроводными зарядками, детские интерактивные зоны. И в целом концепт приватного двора. ✅Один из корпусов (всего 2 дома по 12-этажей на 164 квартиры) будет продаваться полностью с отделкой. Два варианта на выбор: парижские мотивы и japandi от BALCON. ⚡ Больше вводных — на официальном сайте от застроя: Перейти на сайт Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ ЭЛЕКТРОЗАВОДСКАЯ #реклама domartel.ru О рекламодателе

#easy Задача: 108. Convert Sorted Array to Binary Search Tree Дан массив целых чисел nums, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте двоичное дерево поиска. Пример:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

👨‍💻 Алгоритм: 1️⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right. Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None. 2️⃣Выбор корня и разделение массива: Выберите элемент в середине для корня: p = (left + right) // 2. Инициализируйте корень: root = TreeNode(nums[p]). 3️⃣Рекурсивное построение поддеревьев: Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1). Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right). В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева. 😎 Решение:

class Solution:
    def sortedArrayToBST(self, nums):
        def helper(left, right):
            if left > right:
                return None

            p = (left + right) // 2
            root = TreeNode(nums[p])
            root.left = helper(left, p - 1)
            root.right = helper(p + 1, right)
            return root

        return helper(0, len(nums) - 1)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Jobski - твой помощник при поиске работы в IT Сервис индивидуально подбирает вакансии, учитывая ваш опыт, навыки, стек технологий. Узнать больше #реклама jobski.ru О рекламодателе

#medium Задача: 107. Binary Tree Level Order Traversal II Дан корень бинарного дерева. Верните обход значений узлов снизу вверх по уровням (то есть слева направо, уровень за уровнем, от листа к корню). Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

👨‍💻 Алгоритм: 1️⃣Инициализируйте список вывода levels. Длина этого списка определяет, какой уровень в данный момент обновляется. Вам следует сравнить этот уровень len(levels) с уровнем узла level, чтобы убедиться, что вы добавляете узел на правильный уровень. Если вы все еще находитесь на предыдущем уровне, добавьте новый уровень, вставив новый список в levels. 2️⃣Добавьте значение узла в последний уровень в levels. 3️⃣Рекурсивно обработайте дочерние узлы, если они не равны None, используя функцию helper(node.left / node.right, level + 1). 😎 Решение:

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        levels = []
        if not root:
            return levels

        def helper(node: Optional[TreeNode], level: int) -> None:
            if len(levels) == level:
                levels.append([])

            levels[level].append(node.val)

            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)

        helper(root, 0)
        return levels[::-1]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

🔥Тесты для подготовки к собеседованию🔥 Выбери своё направление: 1. Frontend 2. Python 3. Java 4. Тестировщик QA 5. Data Science 6. DevOps 7. C# 8. С/C++ 9. Golang 10. PHP 11. Kotlin 12. Swift

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

10$ за техническое собеседование на английском языке: 1. Отправьте запись технического собеседования на английском языке файлом на этот аккаунт 2. Добавьте ссылку на вакансию или пришлите название компании и должность 3. Напишите номер кошелка USDT (Tether) на который отправить 10$ 🛡 Важно: – Запись будет использована только для сбора данных о вопросах – Вы останетесь анонимны – Запись нигде не будет опубликована 🤝 Условия: – Внятный звук, различимая речь – Допустимые профессии: • Любые программисты • DevOps • Тестировщики • Дата сайнтисты • Бизнес/Системные аналитики • Прожекты/Продукты • UX/UI и продукт дизайнеры

📚 Здесь собраны все вопросы, которые могут спросить на собеседовании. Теперь можно легко получить оффер, подготовившись к самым популярным вопросам. Просто выбери своё направление: 1. Python 2. JavaScrtipt / Frontend 3. Java 4. Тестировщик 5. Data Science 6. DevOps 7. C# 8. С/C++ 9. Golang 10. PHP 11. Kotlin 12. Swift

#medium Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево. Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

👨‍💻 Алгоритм: 1️⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder. 2️⃣Определите вспомогательную функцию helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None. 3️⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень. 😎 Решение:

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def helper(in_left: int, in_right: int) -> TreeNode:
            if in_left > in_right:
                return None

            val = postorder.pop()
            root = TreeNode(val)

            index = idx_map[val]

            root.right = helper(index + 1, in_right)
            root.left = helper(in_left, index - 1)
            return root

        idx_map = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(inorder) - 1)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Ламповый канал анонимного айтишника, который работает на двух работах, пишет свой проект и при этом не сошел с ума, почти... @blogach

#medium Задача: 105. Construct Binary Tree from Preorder and Inorder Traversal Даны два массива целых чисел: preorder и inorder, где preorder — это результат преордер обхода бинарного дерева, а inorder — результат инордер обхода того же дерева. Постройте и верните бинарное дерево. Пример:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

👨‍💻 Алгоритм: 1️⃣Создайте хеш-таблицу для записи соотношения значений и их индексов в массиве inorder, чтобы можно было быстро найти позицию корня. 2️⃣Инициализируйте переменную целочисленного типа preorderIndex для отслеживания элемента, который будет использоваться для создания корня. Реализуйте рекурсивную функцию arrayToTree, которая принимает диапазон массива inorder и возвращает построенное бинарное дерево: Если диапазон пуст, возвращается null; Инициализируйте корень элементом preorder[preorderIndex], затем увеличьте preorderIndex; Рекурсивно используйте левую и правую части массива inorder для построения левого и правого поддеревьев. 3️⃣Просто вызовите функцию рекурсии с полным диапазоном массива inorder. 😎 Решение:

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        def array_to_tree(left, right):
            nonlocal preorder_index
            if left > right:
                return None

            root_value = preorder[preorder_index]
            root = TreeNode(root_value)

            preorder_index += 1

            root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
            root.right = array_to_tree(inorder_index_map[root_value] + 1, right)

            return root

        preorder_index = 0
        inorder_index_map = {}
        for index, value in enumerate(inorder):
            inorder_index_map[value] = index

        return array_to_tree(0, len(preorder) - 1)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Коммутатор ЦОД MES5500-32 Eltex за 1 минуту - 32x40G/100G (QSFP+ / QSFP28) - 2x10G (SFP+) - RS-232 (RJ-45) - OOB - USB 2.0 Пропускная способность - 6,4 Тбит/с 2 модуля питания с горячей заменой: PM600-220/12 — 220В AC PM600-48/12 — 48В DC Настройка: - CLI через Telnet, SSH (Cisco-like) - веб-интерфейс - SNMP Комплектация: - Сертификат - Паспорт устройства - Комплект крепления в 19"стойку - Пылезащитные заглушки для портов Узнать цену #реклама eltexcm.ru О рекламодателе

#easy Задача: 104. Maximum Depth of Binary Tree Дан корень бинарного дерева, верните его максимальную глубину. Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 3

👨‍💻 Алгоритм: 1️⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS). 2️⃣Для данной задачи подойдет несколько способов. 3️⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии. 😎 Решение:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height) + 1

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 103. Binary Tree Zigzag Level Order Traversal Дан корень бинарного дерева. Верните обход узлов дерева по уровням в виде зигзага (то есть слева направо, затем справа налево для следующего уровня и чередуйте далее). Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

👨‍💻 Алгоритм: 1️⃣Мы также можем реализовать поиск в ширину (BFS) с использованием одного цикла. Трюк заключается в том, что мы добавляем узлы для посещения в очередь, а узлы разных уровней разделяем с помощью какого-то разделителя (например, пустого узла). Разделитель отмечает конец уровня, а также начало нового уровня. 2️⃣Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди). 3️⃣Для каждого уровня мы начинаем с пустого контейнера deque, который будет содержать все значения данного уровня. В зависимости от порядка каждого уровня, т.е. либо слева направо, либо справа налево, мы решаем, с какого конца deque добавлять новый элемент. 😎 Решение:

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        ret = []
        level_list = deque()
        if root is None:
            return []
        node_queue = deque([root, None])
        is_order_left = True

        while len(node_queue) > 0:
            curr_node = node_queue.popleft()

            if curr_node:
                if is_order_left:
                    level_list.append(curr_node.val)
                else:
                    level_list.appendleft(curr_node.val)

                if curr_node.left:
                    node_queue.append(curr_node.left)
                if curr_node.right:
                    node_queue.append(curr_node.right)
            else:
                ret.append(level_list)
                if len(node_queue) > 0:
                    node_queue.append(None)

                level_list = deque()
                is_order_left = not is_order_left

        return ret

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Как повысить эффективность вебинаров? Организация продающего вебинара - не простая задача, ведь необходимо предусмотреть множество деталей: удобную дату, вовлекающий контент, методы продвижения и взаимодействия с участниками. Вебинары от МТС Линк помогают привлекать новых клиентов и увеличивать конверсию из участника в лид. В сервисе доступен анализ поведения пользователей во время вебинара, синхронный перевод, автовебинары и интерактивные инструменты для вовлечения участников. Делимся методичкой с кейсами, чек-листами и инструкциями для маркетологов, PR и event-менеджеров, чтобы сделать вебинары эффективным инструментом для лидогенерации. Получите методичку бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

#medium Задача: 102. Binary Tree Level Order Traversal Дан корень бинарного дерева. Верните обход узлов дерева по уровням (то есть слева направо, уровень за уровнем). Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

👨‍💻 Алгоритм: 1️⃣Самый простой способ решения задачи — использование рекурсии. Сначала убедимся, что дерево не пустое, а затем рекурсивно вызовем функцию helper(node, level), которая принимает текущий узел и его уровень в качестве аргументов. 2️⃣Эта функция выполняет следующее: Выходной список здесь называется levels, и, таким образом, текущий уровень — это просто длина этого списка len(levels). Сравниваем номер текущего уровня len(levels) с уровнем узла level. Если вы все еще на предыдущем уровне, добавьте новый, добавив новый список в levels. 3️⃣Добавьте значение узла в последний список в levels. Рекурсивно обработайте дочерние узлы, если они не равны None: helper(node.left / node.right, level + 1). 😎 Решение:

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = []
        if not root:
            return levels

        def helper(node: TreeNode, level: int) -> None:
            if len(levels) == level:
                levels.append([])

            levels[level].append(node.val)

            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)

        helper(root, 0)
        return levels

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#easy Задача: 101. Symmetric Tree Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра). Пример:

Input: root = [1,2,2,3,4,4,3]
Output: true

👨‍💻 Алгоритм: 1️⃣Дерево симметрично, если левое поддерево является зеркальным отражением правого поддерева. 2️⃣Следовательно, вопрос заключается в том, когда два дерева являются зеркальным отражением друг друга? Два дерева являются зеркальным отражением друг друга, если: - Их корни имеют одинаковое значение. - Правое поддерево каждого дерева является зеркальным отражением левого поддерева другого дерева. 3️⃣Это похоже на человека, смотрящего в зеркало. Отражение в зеркале имеет ту же голову, но правая рука отражения соответствует левой руке настоящего человека и наоборот. Вышеописанное объяснение естественным образом превращается в рекурсивную функцию. 😎 Решение:

class Solution:
    def isSymmetric(self, root):
        return self.isMirror(root, root)

    def isMirror(self, t1, t2):
        if t1 is None and t2 is None:
            return True
        if t1 is None or t2 is None:
            return False
        return (
            (t1.val == t2.val)
            and self.isMirror(t1.right, t2.left)
            and self.isMirror(t1.left, t2.right)
        )

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Digital menu board для кафе и ресторанов. От 150.000 р Внедрение цифровых меню бордов "под ключ" от ведущего интегратора Дарим скидку 15% на дизайн для меню бордов. Получите полный расчет, ответив всего на 5 вопросов Перейти на сайт #реклама quiz.in-gr.ru О рекламодателе

#easy Задача: 100. Same Tree Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они. Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения. Пример:

Input: p = [1,2,3], q = [1,2,3]
Output: true

👨‍💻 Алгоритм: Самая простая стратегия здесь — использовать рекурсию. Проверьте, не равны ли узлы p и q значению None, и равны ли их значения. Если все проверки пройдены успешно, проделайте то же самое для дочерних узлов рекурсивно. 😎 Решение:

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not q or not p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) and self.isSameTree(
            p.left, q.left
        )

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых