Python | LeetCode

#medium Задача: 146. LRU Cache Реализуйте класс LRUCache: LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity. int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1. void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ. Функции get и put должны выполняться за среднее время O(1). Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

👨‍💻 Алгоритм: 1️⃣Метод добавления узла в конец связного списка (add): Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd. Вставьте node после previousEnd, установив previousEnd.next = node. Настройте указатели узла: node.prev = previousEnd и node.next = tail. Обновите tail.prev = node, делая node новым "реальным" хвостом списка. 2️⃣Метод удаления узла из связного списка (remove): Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev. Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка. Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C. 3️⃣Методы get и put: get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val. put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты. 😎 Решение:

class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dic = {}
        self.head = ListNode(-1, -1)
        self.tail = ListNode(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1

        node = self.dic[key]
        self.remove(node)
        self.add(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            old_node = self.dic[key]
            self.remove(old_node)

        node = ListNode(key, value)
        self.dic[key] = node
        self.add(node)

        if len(self.dic) > self.capacity:
            node_to_delete = self.head.next
            self.remove(node_to_delete)
            del self.dic[node_to_delete.key]

    def add(self, node):
        previous_end = self.tail.prev
        previous_end.next = node
        node.prev = previous_end
        node.next = self.tail
        self.tail.prev = node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

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

Онлайн-магистратура "Разработка IT-продукта" от МФТИ Карьера в IT-разработке. Освойте Python, Java или GO. Научитесь работать с библиотеками и фреймворками для backend-разработки, анализа данных и машинного обучения! Узнать больше #реклама 16+ mipt.online О рекламодателе

#easy Задача: 145. Binary Tree Postorder Traversal Дан корень бинарного дерева, верните обход значений узлов в постпорядке. Пример:

Input: root = [1,null,2,3]
Output: [3,2,1]

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

class Solution(object):
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        stack, output = [
            root,
        ], []
        while stack:
            root = stack.pop()
            output.append(root.val)
            if root.left is not None:
                stack.append(root.left)
            if root.right is not None:
                stack.append(root.right)

        return output[::-1]

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

Такси для бизнеса. Яндекс Go Оптимизируйте свои расходы и повысьте эффективность бизнеса с Яндекс Go Узнать больше #реклама business.go.yandex О рекламодателе

#easy Задача: 144. Binary Tree Preorder Traversal Дан корень бинарного дерева, верните предварительный обход значений его узлов. Пример:

Input: root = [1,null,2,3]
Output: [1,2,3]

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

class Solution(object):
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        stack, output = [
            root,
        ], []

        while stack:
            root = stack.pop()
            if root is not None:
                output.append(root.val)
                if root.right is not None:
                    stack.append(root.right)
                if root.left is not None:
                    stack.append(root.left)

        return output

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

ТОП-4 Курса по Data Science Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. 🎓Освойте продвинутую математику с самых азов 💻Научитесь создавать ML-модели и работать с нейронными сетями ✅Получите реальный опыт на практических проектах 🏠Начните работать удаленно 💰Подарок в конце подборки! Выбрать #реклама 16+ tutortop.ru О рекламодателе

#medium Задача: 143. Reorder List Вам дана голова односвязного списка. Список можно представить в следующем виде: L0 → L1 → … → Ln - 1 → Ln Переупорядочите список так, чтобы он принял следующую форму: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы. Пример:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

👨‍💻 Алгоритм: 1️⃣Нахождение середины списка и разделение его на две части: Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине. Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка. 2️⃣Реверс второй половины списка: Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка. Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка. 3️⃣Слияние двух частей списка в заданном порядке: Начните с головы первой части списка (first) и головы реверсированной второй части (second). Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки. Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся. 😎 Решение:

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        first, second = head, prev
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next

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

Коммутатор ЦОД 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 О рекламодателе

#medium Задача: 142. Linked List Cycle II Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null. Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра. Не модифицируйте связный список. Пример:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

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

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        nodes_seen = set()
        node = head
        while node is not None:
            if node in nodes_seen:
                return node
            else:
                nodes_seen.add(node)
                node = node.next
        return None

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

👨‍💻 Джун: Слушай, вот стажировку я прошел, где теперь можно чекнуть вакансии на работу? 🍷 Мидл: Ооо, тебе помогут ребята с канала Джун работает 💯 Карьеру нужно начинать с хорошими работодателями. Твое резюме будет ликовать, ведь контент выходит каждый день, работа ждет тебя, мой друг! 😏 Не упускай возможность и подписывайся, чтобы не потерять

#easy Задача: 141. Linked List Cycle Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл. Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра. Верните true, если в связном списке есть цикл. В противном случае верните false. Пример:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

👨‍💻 Алгоритм: 1️⃣Инициализация структуры данных: Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы. 2️⃣Обход списка: Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди. 3️⃣Проверка на цикл: Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false. Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true. Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка. 😎 Решение:

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        nodes_seen = set()
        current = head
        while current is not None:
            if current in nodes_seen:
                return True
            nodes_seen.add(current)
            current = current.next
        return False

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

📕 Прогер, как ты расширяешь свой кругозор в сфере IT? Не достаточно знать что-то одно, мысля глобально и изучая смежные отрасли, ты не только становишься умнее, но и увеличиваешь свою востребованность и свой заработок. 🗿 Не обязательно читать заумные книги и смотреть подкасты - это долго. У нас есть решение: 🔥 Полезные статьи - концентрат знаний. 🔥 Советы - короткие сообщения, которые будут увеличивать твою эффективность. 🔥 Инструменты - tool-сайты в разы упростят и ускорят твою работу. 🧑‍💻 Время, силы, желание - ресурсы, которые нужно использовать с умом. Подпишись на канал Заметки прогера, IT ниша скажет "спасибо" за такого специалиста.

С кем устраивать пикники и встречать рассветы? Найди свою идеальную пару на Мамбе! Погружайся в новые знакомства и наслаждайся яркими моментами ❤️ Попробовать #реклама 18+ click.mamba.ru О рекламодателе

#hard Задача: 140. Word Break II Дана строка s и словарь строк wordDict. Добавьте пробелы в строку s, чтобы построить предложение, в котором каждое слово является допустимым словом из словаря. Верните все такие возможные предложения в любом порядке. Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении. Пример:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

👨‍💻 Алгоритм: 1️⃣Инициализация и начальный вызов: Преобразуйте массив wordDict в множество wordSet для эффективного поиска. Инициализируйте пустой массив results для хранения допустимых предложений. Инициализируйте пустую строку currentSentence для отслеживания конструируемого предложения. Вызовите функцию backtrack с исходной строкой s, множеством wordSet, текущим предложением currentSentence, массивом результатов results и начальным индексом, установленным в 0 — начало входной строки. Верните results после завершения работы backtrack. 2️⃣Функция backtrack: Базовый случай: Если startIndex равен длине строки, добавьте currentSentence в results и вернитесь, так как это означает, что currentSentence представляет собой допустимое предложение. Итерация по возможным значениям endIndex от startIndex + 1 до конца строки. 3️⃣Обработка и рекурсия: Извлеките подстроку word от startIndex до endIndex - 1. Если word найдено в wordSet: Сохраните текущее значение currentSentence в originalSentence. Добавьте word к currentSentence (с пробелом, если это необходимо). Рекурсивно вызовите backtrack с обновленным currentSentence и endIndex. Сбросьте currentSentence к его исходному значению (originalSentence) для отката и попробуйте следующий endIndex. Вернитесь из функции backtrack. 😎 Решение:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_set = set(wordDict)
        results = []
        self._backtrack(s, word_set, [], results, 0)
        return results

    def _backtrack(self, s: str, word_set: set, current_sentence: List[str], results: List[str], start_index: int):
        if start_index == len(s):
            results.append(" ".join(current_sentence))
            return

        for end_index in range(start_index + 1, len(s) + 1):
            word = s[start_index:end_index]
            if word in word_set:
                current_sentence.append(word)
                self._backtrack(s, word_set, current_sentence, results, end_index)
                current_sentence.pop()

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

😭 Джун: Как мне найти работу в IT, если опыта нет? 🧑‍💻 Мидл: Просто зайди на канал Джун стажер и подбери стажировку по душе. 📕 Админы отбирают самые сочные вакансии от ведущих компаний, к тому же контент выходит каждый день. 🔥 Не упускай возможность и подписывайся, чтобы не потерять

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

#medium Задача: 139. Word Break Дана строка s и словарь строк wordDict. Верните true, если строку s можно разделить на последовательность одного или нескольких слов из словаря, разделённых пробелами. Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении. Пример:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

👨‍💻 Алгоритм: 1️⃣Инициализация структур данных: Преобразуйте wordDict в множество words для быстрой проверки вхождения. Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов. 2️⃣Обход в ширину (BFS): Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start. Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря. Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже. 3️⃣Проверка подстроки и обновление структур: Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый. Если BFS завершается и конечный узел не достигнут, возвращайте false. 😎 Решение:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        queue = deque([0])
        seen = set()

        while queue:
            start = queue.popleft()
            if start == len(s):
                return True

            for end in range(start + 1, len(s) + 1):
                if end in seen:
                    continue

                if s[start:end] in words:
                    queue.append(end)
                    seen.add(end)

        return False

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

👨‍💻 Будущий специалист, ты знаешь, какая самая частая ошибка новичка в сфере IT? Отсутствие практики убивает в тебе потенциал ✈️ Как с этим бороться, мой друг? Найди работу и прокачивай свои скилы на конкретных задачах 🔥 У нас ты будешь находить большое количество вакансий каждый день. Понятие работы перестанет быть для тебя размытым. Подпишись на канал и не откладывай свой прогресс в долгий ящик.

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

#medium Задача: 138. Copy List with Random Pointer Дан связный список длиной n, в котором каждый узел содержит дополнительный случайный указатель (random pointer), который может указывать на любой узел в списке или быть равным null. Создайте глубокую копию списка. Глубокая копия должна состоять из ровно n совершенно новых узлов, где каждый новый узел имеет значение, равное значению соответствующего оригинального узла. Указатели next и random новых узлов должны указывать на новые узлы в скопированном списке таким образом, чтобы указатели в оригинальном и скопированном списке представляли одно и то же состояние списка. Ни один из указателей в новом списке не должен указывать на узлы в оригинальном списке. Например, если в оригинальном списке есть два узла X и Y, где X.random --> Y, то для соответствующих узлов x и y в скопированном списке, x.random должен указывать на y. Верните голову скопированного связного списка. Связный список представлен во входных/выходных данных как список из n узлов. Каждый узел представлен парой [val, random_index], где: val: целое число, представляющее Node.val random_index: индекс узла (в диапазоне от 0 до n-1), на который указывает случайный указатель, или null, если он не указывает ни на какой узел. Вашему коду будет дана только голова оригинального связного списка. Пример:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

👨‍💻 Алгоритм: 1️⃣Инициализация и начало обхода: Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов. 2️⃣Проверка и клонирование узлов: Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary. Если клонированная копия существует, используйте ссылку на этот клонированный узел. Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон. 3️⃣Рекурсивные вызовы для обработки связей: Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next. Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next. 😎 Решение:

class Solution:
    def __init__(self):
        self.visitedHash = {}

    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if head == None:
            return None

        if head in self.visitedHash:
            return self.visitedHash[head]

        node = Node(head.val, None, None)
        self.visitedHash[head] = node
        node.next = self.copyRandomList(head.next)
        node.random = self.copyRandomList(head.random)

        return node

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