Python | LeetCode

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

Бакалавриат медиа с практикой и проектами Освойте SMM, дизайн, видео и медиаменеджмент Узнать больше #реклама 16+ netology.ru О рекламодателе

Яндекс Музыка до 360 дней бесплатно Яндекс Музыка для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в мультиподписке Плюс. Попробуйте бесплатно❤️ Слушать #реклама 18+ music.yandex.ru О рекламодателе

Задача: 827. Making A Large Island Сложность: hard Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1. Верните размер самого большого острова в grid после выполнения этой операции. Остров — это группа 1, соединенных в 4 направлениях. Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def dfs(r, c, index):
            ans = 1
            grid[r][c] = index
            for nr, nc in neighbors(r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = index
                    ans += dfs(nr, nc, index)
            return ans

        def neighbors(r, c):
            for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < N:
                    yield nr, nc

        N = len(grid)
        index = 2
        area = [0] * (N * N + 2)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    area[index] = dfs(r, c, index)
                    index += 1

        ans = max(area)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
                    ans = max(a

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

Получи грант до 1,35 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! — 4 офлайн программы по востребованным направлениям ИТ — 2 онлайн-программы: машинное обучение и продуктовый менеджмент — 550 грантов до 75% — Вечерние занятия и учеба по выходным — удобно совмещать с работой — Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса — Возможность стажировок и трудоустройства в ведущих компаниях — Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Зарегистрироваться #реклама 16+ cu.ru О рекламодателе

Задача: 1209. Remove All Adjacent Duplicates in String II Сложность: medium Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе. Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать. Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален. Пример:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

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

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        counts = []
        sa = list(s)
        j = 0
        
        for i in range(len(sa)):
            sa[j] = sa[i]
            if j == 0 or sa[j] != sa[j - 1]:
                counts.append(1)
            else:
                incremented = counts.pop() + 1
                if incremented == k:
                    j -= k
                else:
                    counts.append(incremented)
            j += 1
        
        return "".join(sa[:j])

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

Услуги коммерческого дата-центра в Москве Размещение серверного оборудования в дата-центре. ✅ Услуги предоставляются в 4 дата-центрах в Москве. ✅ Географическое резервирование. ✅ Высокая отказоустойчивость. ✅ Гибкость при выборе площадки для размещения оборудования. Узнать цену #реклама itsoft.ru О рекламодателе

Задача: 300. Longest Increasing Subsequence Сложность: medium Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности. Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i. 2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1). 3⃣Верните максимальное значение из dp. 😎 Решение:

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        if not nums:
            return 0

        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

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

FastAPI: осваиваем SQLAlchemy и Alembic Хотите уверенно работать с БД в FastAPI? Осваивайте SQLAlchemy и Alembic! Зарегистрироваться #реклама 16+ otus.ru О рекламодателе

Yandex Ecom Open Air — летнее событие про онлайн-продажи Yandex Ecom Open Air 2026 объединяет деловую программу, живое общение и атмосферу фестиваля в одном потоке. Здесь обсуждают технологии, которые становятся частью среды. Исследуют силы, которые влияют на весь рынок. Находят новые связи, идеи и точки роста. В течение дня пространство фестиваля наполняют выступления, дискуссии, встречи, специальные форматы, музыка и активности партнёров. Присоединиться к происходящему можно из любой точки — на площадке фестиваля или через онлайн-трансляцию. Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

Задача: 968. Binary Tree Cameras Сложность: hard Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми. Верните минимальное количество камер, необходимых для наблюдения за всеми узлами дерева. Пример:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

👨‍💻 Алгоритм: 1⃣Рекурсивное решение (solve): Для каждого узла определите три состояния: - [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел. - [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры. - [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера. Рассчитайте эти состояния для левого и правого поддеревьев. 2⃣Рассчёт состояний: Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1. Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2. Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии. 3⃣Минимальное количество камер: Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2. 😎 Решение:

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        def solve(node):
            if not node:
                return 0, 0, float('inf')

            L = solve(node.left)
            R = solve(node.right)
            mL12 = min(L[1], L[2])
            mR12 = min(R[1], R[2])

            d0 = L[1] + R[1]
            d1 = min(L[2] + mR12, R[2] + mL12)
            d2 = 1 + min(L[0], mL12) + min(R[0], mR12)
            return d0, d1, d2

        return min(solve(root)[1:])

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

Увлажнение и восстановление кожи лица на каждый день Ежедневный уход для поддержания увлажнённой и комфортной кожи. Средства GELTEK помогают сохранить мягкость, гладкость и ухоженный внешний вид в любых условиях. Лёгкие текстуры быстро впитываются, подходят для регулярного применения и не перегружают кожу. Подходит для тех, кто хочет стабильное увлажнение без сложных схем. Соберите свой уход под тип кожи и сезон. Узнать больше #реклама ozon.ru О рекламодателе

Spring Framework: проверь уровень знаний и начни учиться Spring курс ждёт тебя - сначала пройди тест и проверь свой уровень знаний! Узнать больше #реклама 16+ otus.ru О рекламодателе

Основные шаблоны проектирования в системном дизайне Знать CQRS, Event Sourcing и Saga недостаточно, чтобы правильно применять эти шаблоны в реальной системе. Каждый из них решает архитектурную проблему, но одновременно увеличивает сложность разработки, эксплуатации и поддержки. Если выбирать паттерн только потому, что он популярен или используется в высоконагруженных проектах, можно получить архитектуру, сложнее самой задачи. На открытом уроке 24 августа в 20:00 в OTUS разберём ключевые шаблоны системного дизайна: CQRS, Event Sourcing и Saga Pattern. Рассмотрим, какие проблемы они решают, в каких системах действительно нужны и какие новые ограничения создают. На практических примерах посмотрим, как эти подходы применяются в высоконагруженных сервисах, событийных системах и процессах с распределёнными транзакциями. Узнать больше #реклама 16+ otus.ru О рекламодателе