Python | LeetCode

#Hard Задача: 149. Max Points on a Line Дан массив точек, где points[i] = [xi, yi] представляет точку на плоскости XY. Верните максимальное количество точек, которые лежат на одной прямой. Пример:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

👨‍💻 Алгоритм: 1️⃣Итерация по всем точкам: Проходим по всем точкам массива. Пусть текущая точка будет points[i]. Создаём хеш-таблицу cnt для подсчёта углов. 2️⃣Расчёт углов и подсчёт: Для каждой точки j, не равной i, рассчитываем арктангенс вектора points[j] - points[i] и добавляем это значение в хеш-таблицу . 3️⃣Обновление ответа: Пусть k будет максимальным количеством вхождений какого-либо значения угла в хеш-таблице. Обновляем ответ значением k + 1 (прибавляем 1, потому что точка points[i] также лежит на этой линии, и её нужно включить в ответ). 😎 Решение:

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n == 1:
            return 1
        result = 2
        for i in range(n):
            cnt = collections.defaultdict(int)
            for j in range(n):
                if j != i:
                    cnt[
                        math.atan2(
                            points[j][1] - points[i][1],
                            points[j][0] - points[i][0],
                        )
                    ] += 1
            result = max(result, max(cnt.values()) + 1)
        return result

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

Получи высшее образование в ведущем ВУЗе страны! Получи высшее образование в МосАП! Мечтаешь о престижном дипломе и успешной карьере? Московская Академия Предпринимательства открывает двери для тебя! У нас ты найдешь: - 38 актуальных программ обучения – выбери своё будущее направление! - Государственный диплом – залог стабильности и признания на рынке труда. - Гибкий график – совмещай учебу и работу без потери качества образования. - Поступление по программе «Два диплома» – сделай шаг к своей мечте! Не упусти возможность! Оставь заявку прямо сейчас и начни свой путь к успеху! Узнать больше #реклама mosap.ru О рекламодателе

#Medium Задача: 148. Sort List Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания. Пример:

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

👨‍💻 Алгоритм: 1️⃣Разделение списка (Фаза разделения): Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка. 2️⃣Сортировка подсписков и их объединение (Фаза слияния): Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков. 3️⃣Иллюстрация процесса сортировки: Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список. 😎 Решение:

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        mid = self.getMid(head)
        left = self.sortList(head)
        right = self.sortList(mid)
        return self.merge(left, right)

    def merge(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummyHead = ListNode(0)
        tail = dummyHead
        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        tail.next = list1 if list1 else list2
        return dummyHead.next

    def getMid(self, head: Optional[ListNode]) -> Optional[ListNode]:
        midPrev = None
        while head and head.next:
            midPrev = head if not midPrev else midPrev.next
            head = head.next.next
        mid = midPrev.next
        midPrev.next = None
        return mid

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

Программирование игр с 0. Бесплатно для 6-11 классов. Хотите, чтобы у ребёнка появилось перспективное увлечение? Запишите его на бесплатный урок по созданию игр на Python. ⚡Даже те дети, которые совсем не умеют программировать, за одно занятие создатут свою первую игру самостоятельно! Преподаватели из Университета Иннополис проводят мастер-класс в простой и понятной форме и настолько увлекательно, что дети "заболевают" программированием всерьёз и надолго! Попробуем? 🏃‍♂️Ждём школьников 6-11 классов 25 августа в 16:00 МСК на онлайн-занятии по программированию игр на Python от ИТ-школы из Университета Иннополис! Регистрируйтесь для участия, количество мест ограничено. Зарегистрироваться #реклама 16+ progmatica.innopolis.university О рекламодателе

#medium Задача: 147. Insertion Sort List Дана голова односвязного списка. Отсортируйте список, используя сортировку вставками, и верните голову отсортированного списка. Шаги алгоритма сортировки вставками: 1. Сортировка вставками итеративно работает, потребляя один входной элемент за каждую итерацию и формируя отсортированный выходной список. 2. На каждой итерации сортировка вставками удаляет один элемент из входных данных, находит место, куда он принадлежит в отсортированном списке, и вставляет его туда. 3. Процесс повторяется до тех пор, пока не закончатся входные элементы. Пример:

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

👨‍💻 Алгоритм: 1️⃣Создание вспомогательного узла (pseudo_head): В качестве первого шага создайте вспомогательный узел, который называется pseudo_head. Этот узел будет использоваться как указатель на начало результирующего списка. Этот узел облегчает доступ к результирующему списку, особенно когда необходимо вставить новый элемент в начало списка. Этот прием значительно упрощает логику работы с односвязным списком. 2️⃣Механизм вставки узла: В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A. 3️⃣Использование пары указателей для вставки: Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка. 😎 Решение:

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        dummy = ListNode()
        curr = head

        while curr:
            prev = dummy
            while prev.next and prev.next.val <= curr.val:
                prev = prev.next

            next = curr.next
            curr.next = prev.next
            prev.next = curr
            curr = next

        return dummy.next

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

🤬 Постоянные ошибки, как они надоели! 🤯 Планируя свои дела, мы забываем, что оборудование может подвести. Это может перекрыть все рабочие планы. Придется гуглить, смотреть видосы, звонить знакомым "Не встречалась ли тебе такая ошибка?" 🥵 Все это время и силы. Наша команда нашла этому решение - Битый код. Канал, который даст тебе базу в мире ошибок. 🍸 Стань тем человеком, к которому будут обращаться и про которого будут говорить "Он сможет помочь"

Стань 3D-визуализатором и зарабатывай от 100 000 руб/мес Твои 35 секунд в обмен на возможность попробовать себя в новой профессии и заработать 10,000 рублей. Время пошло! 35 Меня зовут Олег Кононыхин. Я визуализатор с 20-летним опытом работы в 3D Max. 31 Предлагаю попробовать профессию 3d-визуализатор и понять подходит ли она тебе. Участвуй в 14-дневном курсе «3D Max в интерьере: Первые шаги». 22 На нем ты: - Разберешься с интерфейсом и навигацией 3D Max - С нуля построишь геометрию помещения - Самостоятельно смоделируешь ТВ, тумбу, шторы, окна и ковер и др. - Научишься импортировать модели в сцену - Выставишь реалистичный свет и получишь свою первую 3d-визу комнаты - В конце курса мы выберем лучший проект и заплатим за него 10,000 рублей 4 Участие бесплатное. Все что нужно, зарегистрироваться на сайте! Узнать больше #реклама 16+ ok-visual-3dstart.ru О рекламодателе

#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 О рекламодателе