Python | LeetCode

Выпусти трек без головной боли — мы всё сделаем за тебя! «От загрузки до первых прослушиваний» — поможем продвинуть музыку! Твой путь здесь! Начать #реклама sferoom.space О рекламодателе

Задача: 152. Maximum Product Subarray Сложность: Medium Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число. Пример:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

👨‍💻 Алгоритм: 1️⃣Инициализация: Если массив nums пуст, возвращаем 0, так как нет элементов для обработки. Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения. 2️⃣Перебор элементов: Используем вложенные циклы для обработки всех возможных подмассивов: Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива. Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив. 3️⃣Вычисление произведения и обновление результата: Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого. Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result. 😎 Решение:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        result = nums[0]

        for i in range(len(nums)):
            accu = 1
            for j in range(i, len(nums)):
                accu *= nums[j]
                result = max(result, accu)

        return result

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

Зарабатывайте на установках Яндекс Браузера Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей. Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках. Выплаты до 500₽ за каждую установку Яндекс Браузера. Подать заявку #реклама 0+ partner.browser.yandex.ru О рекламодателе

Задача: 215. Kth Largest Element in an Array Сложность: medium Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве. Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент. Пример:

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

👨‍💻 Алгоритм: 1️⃣ Отсортируйте массив в порядке убывания: Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее. 2️⃣ Найдите k-й по величине элемент: После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0). 3️⃣ Верните результат: Возвратите найденное значение как результат. 😎 Решение:

class Solution:
    def findKthLargest(self, nums, k):
        nums.sort(reverse=True)
        return nums[k - 1]

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

Откройте для себя Абу-Даби Абу-Даби оживает в самом сердце Москвы: пятидневное культурное путешествие: иммерсивные технологии, живая эмиратская музыка, традиционные ремёсла и наследие. Манежная площадь, 19-23 августа. Узнать больше #реклама 16+ visitabudhabi.ae О рекламодателе

Битрикс24 представил Коворк/Код Ключевое: • Помнит рабочий контекст месяцами благодаря технологии Радиант: связывает задачи, сделки, переписку и файлы в единую картину, замечает риски и подсказывает следующий шаг — не нужно каждый раз объяснять, о каком клиенте или проекте речь; • Выполняет несколько задач параллельно — помогает ускорить рабочий процесс в разы; • В режиме Коворк выполняет рабочие поручения, в режиме Код создает приложения под ваши задачи; • Работает только с тем, к чему вы сами дали доступ; • Стабильно доступен в России, без зарубежных карт и посредников при оплате; • В основе — модель BitrixGPT 5.6 Agent 1M (контекст на 1M токенов); • Доступно для macOS, Windows и Linux. Ранний доступ к Битрикс24 Коворк/Код уже открыт. Получить предложение #реклама 16+ cowork.bitrix24.ru О рекламодателе

Задача: 100. Same Tree Сложность: easy Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они. Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения. Пример:

Input: p = [1,2,3], q = [1,2,3]
Output: true

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

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not q or not p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) and self.isSameTree(
            p.left, q.left
        )

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

Бесплатный курс: веб-дизайн, графика, интерфейсы Научись создавать дизайн сайтов и приложений, инфографику для карточек на маркетплейсах и работать в Figma! Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰 Этот курс для тебя, если ты: ✅ мечтаешь о новой профессии, но не знаешь, с чего начать; ✅ чувствуешь, что хочешь большего — свободы, самореализации, творчества; ✅ полный новичок и хочешь систему, а не хаос; ✅ хочешь начать зарабатывать удалённо. Зарегистрироваться #реклама 16+ ydaev.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]

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

Устройтесь в Яндекс за неделю на Week Offer Security ⚡ Ищем инженеров по информационной безопасности с опытом от 2 лет: Application Security, Infrastructure Security и SOC L3. Формат простой: вы регистрируетесь, проходите две технические секции онлайн, затем знакомитесь с командами на финальных интервью. Если всё совпадёт, получите офер уже в рамках мероприятия. Как это устроено: ✅ До 4 сентября зарегистрируйтесь на Week Offer Security ✅ 12 и 13 сентября пройдите технические секции онлайн ✅ С 14 по 18 сентября познакомьтесь с командами на финальных интервью и получите офер в Яндекс Подходит специалистам, которые хотят пройти найм без длинных пауз между этапами и быстро получить обратную связь. Переходите по ссылке, чтобы узнать подробности и оставить заявку. Перейти на сайт #реклама 16+ yandex.ru О рекламодателе

Задача: 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

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

Переехать из мегаполиса проще, чем кажется А что, если после работы не нужно стоять в пробке, до школы — несколько минут, а природа - не только по выходным? Доброград — новый город во Владимирской области, в 2,5 часах от Москвы. Здесь всё важное на расстоянии 15 минут: 🎓 школы и детские сады 🏃‍♂️ бассейн, спорт, теннис, падел, вейк-парк и гольф-поле 😊 лес, озёра, парки и 25 км велодорожек ✨ рестораны и SPA ✅ медицина Дети могут сами добираться до школы. Спорт и любимые занятия становятся частью обычного дня. А вместо часов в дороге появляется время на семью, друзей и себя. И это не место, куда приезжают только на выходные. Здесь уже живут 3000 человек из 60+ регионов России. Выбирайте свой формат: готовые квартиры, таунхаусы или земельные участки. Узнать больше #реклама dobrograd.ru О рекламодателе

Задача: 737. Sentence Similarity II Сложность: medium Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи. Пример:

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

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

def areSentencesSimilar(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2):
        return False
    
    graph = {}
    for x, y in similarPairs:
        if x not in graph:
            graph[x] = []
        if y not in graph:
            graph[y] = []
        graph[x].append(y)
        graph[y].append(x)
    
    def dfs(word1, word2, visited):
        if word1 == word2:
            return True
        visited.add(word1)
        for neighbor in graph.get(word1, []):
            if neighbor not in visited and dfs(neighbor, word2, visited):
                return True
        return False
    
    for w1, w2 in zip(sentence1, sentence2):
        if w1 != w2 and not dfs(w1, w2, set()):
            return False
    
    return True

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

Задача: 423. Reconstruct Original Digits from English Сложность: medium Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания. Пример:

Input: s = "owoztneoer"
Output: "012"

👨‍💻 Алгоритм: 1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа. 2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры. 3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат. 😎 Решение:

class Solution:
    def originalDigits(self, s: str) -> str:
        count = collections.Counter(s)
        out = [0] * 10
        out[0] = count['z']
        out[2] = count['w']
        out[4] = count['u']
        out[6] = count['x']
        out[8] = count['g']
        out[3] = count['h'] - out[8]
        out[5] = count['f'] - out[4]
        out[7] = count['s'] - out[6]
        out[9] = count['i'] - out[5] - out[6] - out[8]
        out[1] = count['n'] - out[7] - 2 * out[9]
        output = ''.join(str(i) * out[i] for i in range(10))
        return output

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

Онлайн-магистратура для IT: ИТМО, МИФИ + Яндекс Программы онлайн-магистратуры ИТМО и МИФИ в партнёрстве с Яндексом. Актуальные знания, практическое обучение и гибкий график. Учитесь, совмещая с работой. Доступна господдержка оплаты, отсрочка от армии Перейти на сайт #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 971. Flip Binary Tree To Match Preorder Traversal Сложность: medium Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order. Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект: Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage. Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1]. Пример:

Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

👨‍💻 Алгоритм: 1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1]. 2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка. 3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage. 😎 Решение:

class Solution:
    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
        self.flipped = []
        self.index = 0
        self.voyage = voyage

        self.dfs(root)
        if self.flipped and self.flipped[0] == -1:
            return [-1]
        return self.flipped

    def dfs(self, node):
        if node:
            if node.val != self.voyage[self.index]:
                self.flipped = [-1]
                return
            self.index += 1

            if self.index < len(self.voyage) and node.left and node.left.val != self.voyage[self.index]:
                self.flipped.append(node.val)
                self.dfs(node.right)
                self.dfs(node.left)
            else:
                self.dfs(node.left)
                self.dfs(node.right)

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

Не знак свыше, а точный таргетинг Теперь всем, кто продвигается через CTV в Яндекс Директе, стало проще находить свою аудиторию. Таргетингов стало в 5 раз больше. Вот что нового: — Таргетинг по интересам. Например, можно выбрать не всех, кто интересуется спортом, а только любителей фитнеса или тенниса. — Таргетинг по привычкам. Находите аудиторию по поведению в онлайне и офлайне — например, тех, кто регулярно посещает торговые центры или часто покупает товары в интернете. — Более гибкие настройки. Можно сочетать интересы и социально-демографические характеристики с жанрами и тематиками контента. 👌 Используйте новые возможности, чтобы сделать рекламу на Connected TV еще эффективнее Узнать больше #реклама yandex.ru О рекламодателе

Python asyncio: разбираем gather, wait, TaskGroup! Хотите писать быстрый Python код? На уроке разберём asyncio: gather, wait, TaskGroup - регистрируйтесь! Зарегистрироваться #реклама 16+ otus.ru О рекламодателе

Задача: 987. Vertical Order Traversal of a Binary Tree Сложность: medium Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным. Верните пересечение этих двух списков интервалов. Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b. Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3]. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализация указателей: Создать словарь для хранения узлов по их координатам (col, row). Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)). 2⃣Поиск пересечений: Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row). Добавить левый потомок в очередь с координатами (row + 1, col - 1). Добавить правый потомок в очередь с координатами (row + 1, col + 1). 3⃣Возврат результата: Отсортировать ключи словаря по col и затем по row. Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список. 😎 Решение:

from collections import defaultdict, deque

class Solution:
    def verticalTraversal(self, root):
        col_table = defaultdict(list)
        queue = deque([(root, 0, 0)])
        
        while queue:
            node, row, col = queue.popleft()
            if node:
                col_table[col].append((row, node.val))
                queue.append((node.left, row + 1, col - 1))
                queue.append((node.right, row + 1, col + 1))
        
        result = []
        for col in sorted(col_table.keys()):
            col_table[col].sort()
            result.append([val for row, val in col_table[col]])
        
        return result

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

Подготовка к вступительным экзаменам в ШАД 120+ поступивших в ШАД. Преподаватели МГУ. Гарантия результата. Вы поступите в ШАД, магистратуру или мы зачислим Вас на следующий поток бесплатно Узнать больше #реклама 16+ shadhelper.com О рекламодателе