Python | LeetCode

Как навести порядок в работе? ✅ Вместо личных чатов — мессенджер только для коллег. ✅ Вместо ссылки на созвон и долгих поисков слотов — планерка в один клик. ✅ Вместо задачи на почте — задачка в трекере с четким чек-листом. ✅ Вместо страха белого листа — смелый креатив и рекомендации от ИИ-помощника. Вместо десятка программ — один Битрикс24. Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 952. Largest Component Size by Common Factor Сложность: hard Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае. Пример:

Input: nums = [4,6,15,35]
Output: 4

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

from collections import defaultdict
from math import gcd

def find(x, parent):
    if parent[x] != x:
        parent[x] = find(parent[x], parent)
    return parent[x]

def union(x, y, parent, rank):
    rootX = find(x, parent)
    rootY = find(y, parent)
    if rootX != rootY:
        if rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        elif rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

def largestComponentSize(nums):
    parent = {num: num for num in nums}
    rank = {num: 0 for num in nums}
    
    def prime_factors(n):
        factors = set()
        d = 2
        while d * d <= n:
            while (n % d) == 0:
                factors.add(d)
                n //= d
            d += 1
        if n > 1:
            factors.add(n)
        return factors

    prime_to_index = defaultdict(list)
    for num in nums:
        primes = prime_factors(num)
        for prime in primes:
            prime_to_index[prime].append(num)
    
    for primes in prime_to_index.values():
        for i in range(1, len(primes)):
            union(primes[0], primes[i], parent, rank)
    
    size = defaultdict(int)
    for num in nums:
        root = find(num, parent)
        size[root] += 1
    
    return max(size.values())

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

Задача: 1353. Maximum Number of Events That Can Be Attended Сложность: medium Дан массив событий, где events[i] = [startDayi, endDayi]. Каждое событие i начинается в startDayi и заканчивается в endDayi. Вы можете посетить событие i в любой день d, где startDayi <= d <= endDayi. Вы можете посещать только одно событие в любой момент времени d. Верните максимальное количество событий, которые вы можете посетить. Пример:

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

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

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort(key=lambda x: x[1])
        visited_days = set()
        count = 0
        
        for start, end in events:
            for day in range(start, end + 1):
                if day not in visited_days:
                    visited_days.add(day)
                    count += 1
                    break
        
        return count

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

REKONFA Live 6 ноября приглашаем всех, кто имеет отношение к маркетингу и рекламным технологиям, обсудить рынок, тренды, вызовы и их решения. С докладами на актуальные темы выступят лидеры индустрии и медийные спикеры. Принять участие можно офлайн и онлайн. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 18+ ya.rekonfa.ru О рекламодателе

Задача: 920. Number of Music Playlists Сложность: hard В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

👨‍💻 Алгоритм: 1⃣Создать двумерный массив dp, где dp[i][j] представляет количество возможных плейлистов длины i, содержащих j различных песен. 2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями. Заполнить массив dp, используя два случая: Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1) Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0) 3⃣Ответ находится в dp[goal][n]. 😎 Решение:

def numMusicPlaylists(n, goal, k):
    MOD = 10**9 + 7
    dp = [[0] * (n + 1) for _ in range(goal + 1)]
    dp[0][0] = 1

    for i in range(1, goal + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD
            if j > k:
                dp[i][j] += dp[i-1][j] * (j - k) % MOD
            dp[i][j] %= MOD

    return dp[goal][n]

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

Задача: 169. Majority Element Сложность: easy Дан массив nums размера n, верните элемент большинства. Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве. Пример:

Input: nums = [3,2,3]
Output: 3

👨‍💻 Алгоритм: 1️⃣Использование HashMap для подсчета: Создайте HashMap для отслеживания количества каждого элемента в массиве. 2️⃣Подсчет вхождений элементов: Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента. 3️⃣Поиск элемента большинства: Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋ 😎 Решение:

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

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

Ищу желающих выполнять задачи с помощью ИИ! Работа полностью на удаленке с зп до 150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ ganstaagency.com О рекламодателе

Задача: 735. Asteroid Collision Сложность: medium Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

def asteroidCollision(asteroids):
    stack = []
    
    for asteroid in asteroids:
        while stack and asteroid < 0 < stack[-1]:
            if stack[-1] < -asteroid:
                stack.pop()
                continue
            elif stack[-1] == -asteroid:
                stack.pop()
            break
        else:
            stack.append(asteroid)
    
    return stack

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

Задача: 414. Third Maximum Number Сложность: easy Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число. Пример:

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

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

def thirdMax(nums):
    first = second = third = None
    
    for num in nums:
        if num in (first, second, third):
            continue
        if first is None or num > first:
            third = second
            second = first
            first = num
        elif second is None or num > second:
            third = second
            second = num
        elif third is None or num > third:
            third = num
    
    return third if third is not None else first

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

Получите IT профессию с официальным ДОКУМЕНТОМ! Не просто курсы – а полноценное образование с дипломом о профессиональной переподготовке или удостоверением о повышении квалификации, внесенным в Росреестр! Выбирайте направление: -Web-разработчик -Инженер MikroTik -Специалист по AI и машинному обучению -Сетевой инженер -Linux-администратор -Python-программист -DevOps-инженер -Администратор Windows Server -Специалист по слаботочным сетям (СКС) Ваши гарантии: ✅Законный документ о квалификации ✅Право на ведение профдеятельности ✅Весомое преимущество при трудоустройстве ✅Поддержка ментора ✅Дистанционное обучение Инвестируйте в будущее – получите не только знания, но и официальную профессию! Перейти на сайт #реклама 16+ dms-it.ru О рекламодателе

Задача: 23. Merge k Sorted Lists Сложность: medium  Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его.  Пример:

Input: lists = [[1,4,5],[1,3,4],[2,6]]  
Output: [1,1,2,3,4,4,5,6]  

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

from typing import List, Optional  

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

class Solution:  
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:  
        n = len(lists)  

        newList = ListNode()  
        new = newList  

        while n:  
            # Find list with smallest value  
            smallestNode = ListNode(float('inf'))  
            smallestIndex = -1  
            for i in range(n):  
                listNode = lists[i]  
                if listNode and listNode.val < smallestNode.val:  
                    smallestNode = listNode  
                    smallestIndex = i  

            if smallestIndex == -1:  
                break  

            new.next = ListNode(smallestNode.val)  
            new = new.next  

            if smallestNode.next:  
                lists[smallestIndex] = smallestNode.next  
            else:  
                lists.pop(smallestIndex)  
                n -= 1  

        return newList.next

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

Задача: 1339. Maximum Product of Splitted Binary Tree Сложность: medium Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным. Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7. Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после. Пример:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

👨‍💻 Алгоритм: 1⃣Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке. 2⃣Перебрать все сохраненные суммы поддеревьев и для каждой вычислить произведение суммы поддерева и разности между общей суммой дерева и данной суммой поддерева. 3⃣Найти максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7. 😎 Решение:

class Solution:
    def __init__(self):
        self.all_sums = []

    def maxProduct(self, root):
        total_sum = self.treeSum(root)
        best = 0
        for s in self.all_sums:
            best = max(best, s * (total_sum - s))
        return best % 1000000007

    def treeSum(self, subroot):
        if not subroot:
            return 0
        left_sum = self.treeSum(subroot.left)
        right_sum = self.treeSum(subroot.right)
        total_sum = left_sum + right_sum + subroot.val
        self.all_sums.append(total_sum)
        return total_sum

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

Курс: Договорное право 2.0 – Обновлен в 2025 году ⚡Перестаньте бояться сделок! Освойте договорное право с юристами Ozon, Denuo, BGP Litigation, Verba Legal и НИУ ВШЭ ✨ На курсе «Договорное право» от MDS вы: » Систематизируете знания по всем ключевым типам договоров » Научитесь видеть и минимизировать риски в контрактах » Получите практический навык на разборе реальных документов из практики » Получите неограниченный доступ к материалам и чат с экспертами для консультаций 🎓Что в программе: » Базовые принципы и «подводные камни» договорного права » Глубокий разбор специфики отдельных договоров » Построение эффективной договорной работы в компании Промокод «MDS10» дарит дополнительную скидку 10% до конца августа. Начните составлять безупречные договоры. Оставьте заявку и получите востребованный навык! Узнать больше #реклама 16+ mosdigitals.ru О рекламодателе

Задача: 943. Find the Shortest Superstring Сложность: hard Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words. Пример:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

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

def shortestSuperstring(words):
    def overlap(a, b):
        max_overlap = 0
        for i in range(1, min(len(a), len(b)) + 1):
            if a[-i:] == b[:i]:
                max_overlap = i
        return max_overlap

    def merge(a, b, overlap_len):
        return a + b[overlap_len:]
    
    while len(words) > 1:
        max_overlap = -1
        l, r = 0, 0
        for i in range(len(words)):
            for j in range(len(words)):
                if i != j:
                    ovlp = overlap(words[i], words[j])
                    if ovlp > max_overlap:
                        max_overlap = ovlp
                        l, r = i, j
        words.append(merge(words[l], words[r], max_overlap))
        words.pop(r)
        words.pop(l)
    
    return words[0]

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

Задача: 110. Balanced Binary Tree Сложность: easy Дано бинарное дерево, определите, является ли оно сбалансированным по высоте. Пример:

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

👨‍💻 Алгоритм: 1️⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает: -1, если p является пустым поддеревом, т.е. null; 1 + max(height(p.left), height(p.right)) в противном случае. 2️⃣Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. Дерево T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы. 3️⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них: Если root == NULL, возвращаем true. Если abs(height(root.left) - height(root.right)) > 1, возвращаем false. В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right). 😎 Решение:

class Solution:
    def height(self, root: TreeNode) -> int:
        if not root:
            return -1
        return 1 + max(self.height(root.left), self.height(root.right))

    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        return (
            abs(self.height(root.left) - self.height(root.right)) < 2
            and self.isBalanced(root.left)
            and self.isBalanced(root.right)
        )

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

Гайд для маркетологов по эффективным онлайн-встречам Как CMO, PR и digital-маркетологам повысить результативность брейнштормов, совещаний и планерок с командой с помощью онлайн-встреч? Гайд МТС Линк: 37 страниц полезных материалов, чек-листов и кейсов для эффективных видеовстреч и совещаний. ✅ В гайде: - Как создать постоянную ссылку на регулярные встречи с подрядчиками, командой или агентствами и подключаться в 2 клика; - Как управлять встречей и завершить ее четкими договоренностями с ИИ-расшифровкой голоса в текст; - Как проводить кастдевы, брейнштормы и формулировать гипотезы с помощью 15+ шаблонов в онлайн-досках МТС Линк; - Как разом пригласить всех участников на синк таким образом, чтобы все пришли. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 273. Integer to English Words Сложность: hard Преобразуйте неотрицательное целое число num в его словесное представление на английском языке. Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

👨‍💻 Алгоритм: 1️⃣Обработка чисел до 20 и кратных 10 до 90: Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90. Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление. 2️⃣Обработка сотен, тысяч, миллионов и миллиардов: Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды). Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999. 3️⃣Формирование окончательного результата: Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды). Соединить все части в одну строку, удалив лишние пробелы. 😎 Решение:

class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        
        def helper(n):
            if n == 0:
                return ""
            elif n < 20:
                return below_twenty[n] + " "
            elif n < 100:
                return tens[n // 10] + " " + helper(n % 10)
            else:
                return below_twenty[n // 100] + " Hundred " + helper(n % 100)
        
        below_twenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        thousands = ["", "Thousand", "Million", "Billion"]
        
        result = ""
        i = 0
        
        while num > 0:
            if num % 1000 != 0:
                result = helper(num % 1000) + thousands[i] + " " + result
            num //= 1000
            i += 1
        
        return result.strip()

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

Задача: 665. Non-decreasing Array Сложность: medium Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента. Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1]. Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Завести переменную count для подсчета числа изменений. Проверить последовательность чисел в массиве nums. 2⃣Проверка условий: Если nums[i] > nums[i + 1], то увеличиваем count. Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо. Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false. 3⃣Возврат результата: Если количество изменений не превышает 1, вернуть true. 😎 Решение:

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        count = 0
        
        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:
                if count > 0:
                    return False
                count += 1
                if i == 1 or nums[i] >= nums[i - 2]:
                    nums[i - 1] = nums[i]
                else:
                    nums[i] = nums[i - 1]
        
        return True

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

⚡️ Айтишник из «VISION» скупил топовые айти-курсы и выложил гигабайты материалов к себе Каждый найдет что-то по душе: 903 ГБ — Python 812 ГБ — Frontend 978 ГБ — C, C++ 804 ГБ — Java 432 ГБ — C#, GameDev 411 ГБ — SQL & БД 309 ГБ — DevOps 998 ГБ — ИБ & Хакинг 773 ГБ — Kotlin, Swift 189 ГБ — PHP 201 ГБ — GoLang 170 ГБ — Rust 167 ГБ — QA-Тестирование 310 ГБ — 1C + Лицензии 495 ГБ — Машинное обучение 704 ГБ — Аналитика Данных 991 ГБ — Дизайн Материалы в закрепе, постоянно пополняются👆🏻

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