Python | LeetCode

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

#Medium Задача: 151. Reverse Words in a String Дана входная строка s, переверните порядок слов. Слово определяется как последовательность символов, не являющихся пробелами. Слова в строке s разделены как минимум одним пробелом. Верните строку, в которой слова расположены в обратном порядке, соединённые одним пробелом. Обратите внимание, что строка s может содержать пробелы в начале или в конце, или множественные пробелы между двумя словами. Возвращаемая строка должна содержать только один пробел, разделяющий слова. Не включайте лишние пробелы. Пример:

Input: s = "the sky is blue"
Output: "blue is sky the"

👨‍💻 Алгоритм: 1️⃣Удаление лишних пробелов: Удалите начальные и конечные пробелы из строки s. Это делается для того, чтобы убрать пробелы в начале и в конце строки, которые могут исказить конечный результат. В коде это реализовано с помощью методов erase и find_first_not_of/find_last_not_of, которые удаляют пробелы до первого и после последнего непробельного символа. 2️⃣Разделение строки на слова: Преобразуйте строку s в поток и используйте istringstream для чтения слов, разделенных пробелами. Каждое слово определяется как последовательность символов, не содержащая пробелов. Слова сохраняются в вектор words. Это делается с помощью copy, который копирует слова из потока в words с помощью istream_iterator. . 3️⃣Реверсирование и соединение слов: Переверните вектор слов и соедините их обратно в одну строку, разделяя слова одним пробелом. Для реверсирования используется функция reverse, а для соединения слов — ostringstream вместе с ostream_iterator. Слова объединяются таким образом, что между ними находится только один пробел, исключая лишние пробелы между словами. 😎 Решение:

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.split()))

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

🧑‍💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом. 🫤 Ты в курсе, что ... - говорят по-английски — 20% из всех людей. - Большое кол-во IT документации написано на английском. Хочешь понимать код лучше? Изучи язык, который используется в его основе. 📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут: - Тесты для изучения английского: проверьте свои знания на практике. - Английский через мемы: учите язык весело и с интересом. - Шпаргалки для повторения: закрепите знания быстро и эффективно. - Английский сленг программиста: станьте настоящим профи в коммуникации. 🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп. 🌸 Подпишись, do it!

Ну все! Теперь не нужно тратить деньги на топовые курсы и книги по программированию — их выложили в Telegram бесплатно Все найденные курсы собирают тут — t.me/+Rg23ozD8yGdkYmJi По этим курсам выучить любой язык за 7 дней вообще не проблема, находка для начинающих программистов Подписаться #реклама 16+ О рекламодателе

#Medium Задача: 150. Evaluate Reverse Polish Notation Вам дан массив строк под названием tokens, который представляет арифметическое выражение в обратной польской нотации. Вычислите это выражение. Верните целое число, которое представляет значение этого выражения. Обратите внимание на следующие моменты: Допустимые операторы: '+', '-', '*' и '/'. Каждый операнд может быть целым числом или другим выражением. Деление двух целых чисел всегда округляется к нулю. Деление на ноль в выражении отсутствует. Входные данные представляют собой действительное арифметическое выражение в обратной польской нотации. Ответ и все промежуточные вычисления можно представить 32-битным целым числом. Пример:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

👨‍💻 Алгоритм: 1️⃣Обработка входных массивов: Для языков, таких как Java, где входные данные представлены фиксированным массивом, необходимо определить собственные методы для манипулирования массивом (например, удаление элементов). Это может включать сдвиг элементов для заполнения пробелов после удаления элемента. В качестве альтернативы, копирование массива в ArrayList могло бы упростить удаление, но за счет увеличения сложности по памяти с O(1) до O(n). 2️⃣Обработка типов и деление в Python: Необходимо быть внимательным при обработке типов в Python во время обработки списка, поскольку числа могут быть представлены как строки или целые числа. Кроме того, стандартное деление в Python не округляет к нулю. Вместо этого использование int(a / b) достигает желаемого результата округления, что отличается от деления нацело int(a // b), которое является другим распространенным подходом. . 3️⃣Использование лямбда-функций: Лямбда-функции могут упростить реализацию арифметических операций (таких как +, -, *, /). Если вы знакомы с лямбда-функциями, они предлагают элегантное решение для динамической обработки операций. Если лямбда-функции новы или не поддерживаются в используемом языке программирования, можно использовать другие методы, а изучение лямбда-функций можно отложить на потом. 😎 Решение:

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operations = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "/": lambda a, b: int(a / b),
            "*": lambda a, b: a * b,
        }

        current_position = 0

        while len(tokens) > 1:
            while tokens[current_position] not in "+-*/":
                current_position += 1

            operator = tokens[current_position]
            number_1 = int(tokens[current_position - 2])
            number_2 = int(tokens[current_position - 1])

            operation = operations[operator]
            tokens[current_position] = operation(number_1, number_2)

            tokens.pop(current_position - 2)
            tokens.pop(current_position - 2)
            current_position -= 1

        return int(tokens[0])

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

👩‍💻 Есть опыт в проге, но не растет зп? Может нужно найти крутой оффер? 🗿 Большинство IT специалистов работает за копейки и даже не осознает этого. Лучший способ понять рынок вакансий - стать его частью и начать анализировать. 👍 Предела совершенству нет, что нельзя сказать про зп в рамках одной компании. Подпишись на Мидл работает и повышай свой капитал.

Партнёрская программа рекрутинга в Яндекс Еду Станьте партнёром Яндекс Еды по привлечению курьеров и получите кучу преимуществ: 💰Платим до 25 000 ₽ за успешного кандидата 📞Поддержка на всех этапах 📅Свободное расписание 📊Удобные инструменты для работы Приводите новых курьеров и получайте до 187 000 ₽ в месяц! Зарегистрироваться #реклама eda.yandex.ru О рекламодателе

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