Python | LeetCode

Задача: 143. Reorder List Сложность: medium Вам дана голова односвязного списка. Список можно представить в следующем виде: 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

Ставь 👍 и забирай 📚 Базу знаний

Онлайн-магистратура Кибербезопасность от Яндекса и МИФИ День открытых дверей 23 апреля в 19:00 мск | Онлайн Эксперты Яндекса и НИЯУ МИФИ расскажут об очной онлайн-магистратуре для карьеры в IT. Всё о поступлении и обучении, выступления экспертов, ответы на вопросы. Выбирайте всё: работу и учёбу, навыки и диплом магистра. Узнать больше #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 135. Candy Сложность: hard В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings. Вы раздаете конфеты этим детям с соблюдением следующих требований: Каждый ребенок должен получить как минимум одну конфету. Дети с более высоким рейтингом должны получать больше конфет, чем их соседи. Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей. Пример:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

👨‍💻 Алгоритм: 1️⃣Инициализация и первичное заполнение массивов: Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете. 2️⃣Обход и обновление значений в массивах: Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа. Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа. 3️⃣Расчет минимального количества конфет: Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет. Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил. 😎 Решение:

class Solution:
    def candy(self, ratings: List[int]) -> int:
        sum = 0
        n = len(ratings)
        left2right = [1] * n
        right2left = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left2right[i] = left2right[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right2left[i] = right2left[i + 1] + 1
        for i in range(n):
            sum += max(left2right[i], right2left[i])
        return sum

Ставь 👍 и забирай 📚 Базу знаний

📅 Осталось 7 дней до конца краудфандинга Мы на финишной прямой! Если ты планировал присоединиться, но ещё не успел, сейчас идеальный момент. Вознаграждения за поддержку: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование 👉 Поддержать easyoffer 2.0 Не откладывай на последний момент 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Задача: 1402. Reducing Dishes Сложность: hard Шеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени. Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] * satisfaction[i]. Верните максимальную сумму коэффициентов удовольствия, которую шеф-повар может получить после приготовления некоторого количества блюд. Блюда можно готовить в любом порядке, и шеф может отказаться от некоторых блюд, чтобы достичь максимального значения. Пример:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

👨‍💻 Алгоритм: 1⃣Отсортируйте массив satisfaction в порядке возрастания. 2⃣Создайте таблицу мемоизации memo размером N x N и инициализируйте все значения -1, что будет означать, что ответ для всех состояний еще не рассчитан. 3⃣Реализуйте функцию, которая вызывается с параметрами index = 0 и time = 1, чтобы найти ответ: Если достигнут конец массива, т.е. index == satisfaction.length, верните 0, так как больше нет блюд для приготовления и нельзя получить дополнительное значение. Если значение в массиве memo для пары {index, time} не равно -1, верните это значение, так как это подразумевает, что данная подзадача уже была решена; поэтому рекурсивный вызов не требуется, и можно вернуть сохраненное значение из таблицы memo. Рассчитайте максимум из двух вариантов: - добавьте значение коэффициента для данного блюда satisfaction[index] * time к рекурсивному результату с index = index + 1 и time = time + 1. - пропустите текущее блюдо и сделайте рекурсивный вызов для index = index + 1 и time = time. 😎 Решение:

class Solution:
    def maxSatisfaction(self, satisfaction):
        satisfaction.sort()
        memo = [[-1] * (len(satisfaction) + 1) for _ in range(len(satisfaction) + 1)]
        
        def findMaxSatisfaction(satisfaction, memo, index, time):
            if index == len(satisfaction):
                return 0
            if memo[index][time] != -1:
                return memo[index][time]
            
            memo[index][time] = max(satisfaction[index] * time + findMaxSatisfaction(satisfaction, memo, index + 1, time + 1),
                                    findMaxSatisfaction(satisfaction, memo, index + 1, time))
            return memo[index][time]
        
        return findMaxSatisfaction(satisfaction, memo, 0, 1)

Ставь 👍 и забирай 📚 Базу знаний

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 387. First Unique Character in a String Сложность: easy Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1. Пример:

Input: s = "leetcode"
Output: 0

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

import random

class Solution:
    def __init__(self, nums: list[int]):
        self.original = nums[:]
        self.array = nums[:]

    def reset(self) -> list[int]:
        self.array = self.original[:]
        return self.original

    def shuffle(self) -> list[int]:
        n = len(self.array)
        for i in range(n):
            rand_index = random.randint(i, n - 1)
            self.array[i], self.array[rand_index] = self.array[rand_index], self.array[i]
        return self.array

Ставь 👍 и забирай 📚 Базу знаний

Искусственный интеллект помогает больше продавать Битрикс24 CRM + Ai упрощает работу менеджера. Расшифровывает записи звонков клиентам и сам заполняет карточку сделки. Менеджер в это время уже звонит следующему клиенту. Попробуйте умную CRM Попробовать #реклама 16+ bitrix24.ru О рекламодателе

Задача: 476. Number Complement Сложность: easy Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении. Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение. Пример:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

👨‍💻 Алгоритм: 1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1. 2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1. 3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask. 😎 Решение:

class Solution:
    def findComplement(self, num: int) -> int:
        bitmask = num
        bitmask |= (bitmask >> 1)
        bitmask |= (bitmask >> 2)
        bitmask |= (bitmask >> 4)
        bitmask |= (bitmask >> 8)
        bitmask |= (bitmask >> 16)
        return bitmask ^ num

Ставь 👍 и забирай 📚 Базу знаний

Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы пройдете стажировку и устроитесь на работу с зп от 150.000 рублей Образование, место жительства, трудовой стаж — не важны! Для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать, после обучения: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Осталось всего 47 бесплатных мест. Успейте пройти тест и оставить заявку: Узнать больше #реклама 16+ technolium.ru О рекламодателе

Задача: 350. Intersection of Two Arrays II Сложность: easy Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен появляться столько раз, сколько он встречается в обоих массивах. Вы можете вернуть результат в любом порядке. Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

👨‍💻 Алгоритм: 1⃣Подсчет частоты элементов: Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в nums1. 2⃣Нахождение пересечения: Пройдите по элементам nums2, и если элемент присутствует в хеш-таблице из шага 1 и его счетчик больше нуля, добавьте этот элемент в результат и уменьшите счетчик. 3⃣Возврат результата: Верните массив пересечения. 😎 Решение:

from collections import Counter

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        counts = Counter(nums1)
        result = []

        for num in nums2:
            if counts[num] > 0:
                result.append(num)
                counts[num] -= 1

        return result

Ставь 👍 и забирай 📚 Базу знаний

⚡ Когда говорят, что Python слишком простой язык, на сцену выходит канал Python Learning Здесь легко научиться: ▪️Превращать текст в голос ▪️Определять локацию по IP ▪️Писать телеграм-ботов ▪️Создавать 3D-игры Самый необычный канал про Python, подписывайся – @Python_per_month

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Даешь ИИ в каждый бизнес! ⚡Скидка 30% при покупке Битрикс24 на год + AI-помощник на сумму 100 000 ₽ — бонусом. ✨ИИ возьмет на себя рутину и поможет команде быть еще эффективнее. Узнать больше #реклама 16+ ai-sale.bitrix24.ru О рекламодателе

Задача: 228. Summary Ranges Сложность: easy Вам дан отсортированный массив уникальных целых чисел nums. Диапазон [a,b] - это множество всех целых чисел от a до b (включительно). Верните наименьший отсортированный список диапазонов, которые покрывают все числа в массиве точно. То есть, каждый элемент nums покрывается ровно одним из диапазонов, и не существует такого целого числа x, чтобы x находился в одном из диапазонов, но не находился в nums. Каждый диапазон [a,b] в списке должен быть представлен в формате: "a->b" если a != b "a" если a == b Пример:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

👨‍💻 Алгоритм: 1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i]. 2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики. 3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон. 😎 Решение:

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        ranges = []
        i = 0
        while i < len(nums):
            start = nums[i]
            while i + 1 < len(nums) and nums[i] + 1 == nums[i + 1]:
                i += 1
            if start != nums[i]:
                ranges.append(f"{start}->{nums[i]}")
            else:
                ranges.append(f"{start}")
            i += 1
        return ranges

Ставь 👍 и забирай 📚 Базу знаний

Крупнейший университет искусственного интеллекта Учим использовать ChatGPT в профессиональных целях, создавать нейро-сотрудников и зарабатывать на искусственном интеллекте. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 116. Populating Next Right Pointers in Each Node Сложность: medium Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение:

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 root

Ставь 👍 и забирай 📚 Базу знаний

Что такое PRO-подписка на easyoffer 2.0? easyoffer PRO — это не просто доступ к базе, а полноценный инструмент для получения оффера. 🧠 База вопросов с собеседований + Анализ на основе 4,000 собеседований + Вероятность встречи каждого вопроса + Фильтрация по грейдам, компаниям, типам интервью + Примеры ответов: текстовые и видео + Готовьтесь к собеседованию в конкретную компанию 🛠 Тренажер "Проработка вопросов" + Флеш-карточки + интервальные повторения + Персональная система показа карточек в зависимости от ваших ответов + Упор на наиболее частые вопросы + Фокус на слабые места и быстрый прогресс 🎭 Тренажер "Реальное собеседование" + Сценарии на основе реальных интервью + Подготовка к конкретным компаниям + Итоговая статистика: прошёл/не прошёл 🧩 База задач с собеседований + Live-coding и System Design задачи + Оценка вероятности встречи задачи + Подготовка к задачам по конкретным компаниям 📋 База тестовых заданий + Задания из реальных вакансий + Фильтрация по технологиям и грейдам + Лучшие решения в доступе 📈 Тренды технологий в вакансиях + Топ-100 навыков, которые требуют компании + Динамика популярности технологий + Фильтрация по грейдам 🎁 Специальная цена до релиза: 3200 руб. за целый год Сейчас PRO на 1 год стоит как будет стоить 1 месяц после релиза. Покупка также открывает доступ к закрытому бета-тестированию. + Вы можете активировать подписку в любой момент, например, когда начнете искать работу. Предзаказ здесь: https://planeta.ru/campaigns/easyoffer 📌 Цена поднимется сразу после запуска. Если вы хотите перестать угадывать, что спросят на собеседовании, и начать точечно готовиться на основе реальных данных — easyoffer PRO именно для вас. Экономьте время. Получайте оффер легко.

Задача: 1354. Construct Target Array With Multiple Sums Сложность: hard Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру: Пусть x будет суммой всех элементов, находящихся в вашем массиве. Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x. Вы можете повторять эту процедуру столько раз, сколько потребуется. Верните true, если возможно построить массив target из arr, в противном случае верните false. Пример:

Input: target = [8,5]
Output: true

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

import heapq

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        total = sum(target)
        target = [-x for x in target]
        heapq.heapify(target)
        
        while -target[0] > 1:
            maxVal = -heapq.heappop(target)
            total -= maxVal
            if maxVal < total or total == 0 or maxVal % total == 0:
                return False
            maxVal %= total
            total += maxVal
            heapq.heappush(target, -maxVal)
        return True

Ставь 👍 и забирай 📚 Базу знаний

26–27 апреля проводим Weekend Offer Frontend Устроиться в Яндекс за выходные — реально. Ищем крутых фронтендеров с опытом работы от 4 лет, готовых работать в офисном или гибридном режиме в России. Подавайте заявку до 23 апреля — и всего за два дня пройдите все технические собеседования. После сможете пообщаться с нанимающими менеджерами и выбрать из 10 команд ту, которая покажется самой интересной. Если всё сложится хорошо, сразу же пришлём вам офер. Зарегистрироваться #реклама yandex.ru О рекламодателе