Python | LeetCode

VK проводит Weekend Offer для бэкенд-разработчиков и ML-инженеров. Это отличная возможность получить офер за 2 дня и не проходить много этапов. Ищут бэкендеров со знанием Java, Go, Python или C++. И MLщиков, с навыками в Classic ML, RecSys, NLP/LLM, CV, Speech. Важный момент: ищут коллег с опытом коммерческой разработки от трех лет. Совпадает? Тогда у вас есть все шансы получить приглашение на работу за 2 дня: технические собеседования 4 октября, а финалы, знакомство с командами и офер 5 октября. Отправляйте заявку до 2 октября и станьте частью VK! Подробнее — на сайте.

Задача: 592. Fraction Addition and Subtraction Сложность: medium Дана строка, представляющая выражение сложения и вычитания дробей, верните результат вычисления в строковом формате. Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1. Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

class Solution:
    def fractionAddition(self, expression: str) -> str:
        sign = []
        if expression[0] != '-':
            sign.append('+')
        for char in expression:
            if char in '+-':
                sign.append(char)
        
        fractions = expression.replace('-', '+-').split('+')
        prev_num, prev_den = 0, 1
        i = 0
        
        for sub in fractions:
            if not sub:
                continue
            num, den = map(int, sub.split('/'))
            g = gcd(prev_den, den)
            if sign[i] == '+':
                prev_num = prev_num * den // g + num * prev_den // g
            else:
                prev_num = prev_num * den // g - num * prev_den // g
            prev_den = prev_den * den // g
            g = abs(gcd(prev_num, prev_den))
            prev_num //= g
            prev_den //= g
            i += 1
        
        return f"{prev_num}/{prev_den}"

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

Тариф, с которым хватит на всё 50 ГБ и безлимитные минуты за 390 ₽ в месяц, если перенесете номер в Т-Мобайл до 30 сентября Узнать больше #реклама tbank.ru О рекламодателе

Задача: 1344. Angle Between Hands of a Clock Сложность: medium Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками. Ответы с точностью до 10^-5 от фактического значения будут считаться правильными. Пример:

Input: hour = 12, minutes = 30
Output: 165

👨‍💻 Алгоритм: 1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30. 2⃣Найти разницу: diff = abs(hour_angle - minutes_angle). 3⃣Вернуть меньший угол: min(diff, 360 - diff). 😎 Решение:

class Solution:
    def angleClock(self, hour: int, minutes: int) -> float:
        one_min_angle = 6
        one_hour_angle = 30

        minutes_angle = one_min_angle * minutes
        hour_angle = (hour % 12 + minutes / 60.0) * one_hour_angle

        diff = abs(hour_angle - minutes_angle)
        return min(diff, 360 - diff)

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

Задача: 933. Number of Recent Calls Сложность: easy У вас есть класс RecentCounter, который подсчитывает количество последних запросов за определенный промежуток времени. Реализуйте класс RecentCounter: RecentCounter() Инициализирует счетчик нулем последних запросов. int ping(int t) Добавляет новый запрос в момент времени t, где t представляет собой некоторое время в миллисекундах, и возвращает количество запросов, произошедших за последние 3000 миллисекунд (включая новый запрос). Точнее, возвращается количество запросов, произошедших в диапазоне [t - 3000, t]. Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов. Пример:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

👨‍💻 Алгоритм: 1⃣Создать класс RecentCounter с конструктором для инициализации пустой очереди. 2⃣Реализовать метод ping, который принимает время запроса t: Добавить t в очередь. Удалить из очереди все запросы, которые не попадают в диапазон [t - 3000, t]. 3⃣Вернуть размер очереди. 😎 Решение:

from collections import deque

class RecentCounter:
    def __init__(self):
        self.q = deque()
    
    def ping(self, t: int) -> int:
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)

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

Задача: 136. Single Number Сложность: easy Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент. Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство. Пример:

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

👨‍💻 Алгоритм: 1️⃣Переберите все элементы в массиве nums. 2️⃣Если какое-то число в nums новое для массива, добавьте его. 3️⃣Если какое-то число уже есть в массиве, удалите его. 😎 Решение:

class Solution(object):
    def singleNumber(self, nums: List[int]) -> int:
        no_duplicate_list = []
        for i in nums:
            if i not in no_duplicate_list:
                no_duplicate_list.append(i)
            else:
                no_duplicate_list.remove(i)
        return no_duplicate_list.pop()

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

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

Задача: 938. Range Sum of BST Сложность: easy Учитывая корневой узел двоичного дерева поиска и два целых числа low и high, верните сумму значений всех узлов со значением в диапазоне [low, high]. Пример:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

👨‍💻 Алгоритм: 1⃣Если дерево пустое, вернуть 0. 2⃣Если значение текущего узла меньше low, рекурсивно искать в правом поддереве. Если значение текущего узла больше high, рекурсивно искать в левом поддереве. 3⃣Если значение текущего узла в диапазоне [low, high], включить значение узла в сумму и рекурсивно искать в обоих поддеревьях. 😎 Решение:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rangeSumBST(root, low, high):
    if not root:
        return 0
    if root.val < low:
        return rangeSumBST(root.right, low, high)
    if root.val > high:
        return rangeSumBST(root.left, low, high)
    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)

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

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

Задача: 99. Recover Binary Search Tree Сложность: medium Вам дан корень бинарного дерева поиска (BST), в котором значения ровно двух узлов дерева были поменяны местами по ошибке. Восстановите дерево, не изменяя его структуру. Пример:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

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

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        def inorder(r: TreeNode) -> List[int]:
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []

        def find_two_swapped(nums: List[int]) -> (int, int):
            n = len(nums)
            x = y = (
                None  
            )

            for i in range(n - 1):
                if nums[i + 1] < nums[i]:
                    y = nums[i + 1]
                    if x is None:
                        x = nums[i]
                    else:
                        break
            return x, y

        def recover(r: TreeNode, count: int) -> None:
            if r:
                if r.val == x or r.val == y:
                    r.val = y if r.val == x else x
                    count -= 1
                    if count == 0:
                        return
                recover(r.left, count)
                recover(r.right, count)

        nums = inorder(root)
        x, y = find_two_swapped(nums)
        recover(root, 2)

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

Почему джуны и миддлы не могут найти работу в 2025? 😭 Знакомая картина? Отправил 500 откликов за неделю — ни одного ответа. Наконец позвонил HR, назначили собес, а ты уже трясёшься от страха: "Сейчас поймут, что я ничего не знаю". Расслабься. Дело не в том, что ты плохой разработчик. Просто правила игры изменились в 2025 году, а большинство об этом не знает 🤑 Этими инсайтами поделился Сергей — основатель Академии Python, ментор, который за 2 года помог 200+ человек получить необходимые навыки и офферы на рынке. Сам прошёл путь от нуля до потолка по зарплате, провёл сотни собеседований с обеих сторон. Его ученики находят работу в среднем за 1,5 месяца после выпуска со средним окладом 200к+ 😘 Вот что реально происходит в 2025: на одну вакансию приходят сотни откликов И первым их смотрит не живой человек, а робот или HR, который просто "жмет 2 кнопки" и фильтрует ваши резюме. Да, вот так обычная программа решает и нежелание HR работать решают, дойдёт ли твоё резюме до тимлида. Написал в резюме "Postgres" вместо "PostgreSQL"? Пролетел. Сделал красивый дизайн в две колонки? Робот не смог распарсить — в корзину. HR не захотел потратить хотя бы 1 минуту на твое резюме — исход тот же Что делать прямо сейчас: Открой хотя бы 10-20 вакансий, на которые хочешь откликнуться. Выпиши все технологии, которые повторяются. Docker, CI/CD, Git, REST API — всё это должно быть в твоём резюме точь-в-точь как в вакансии. И забудь про креативные шаблоны. Простая структура = робот поймёт = HR увидит. Переупакуй свой опыт Вместо "Пет-проект: парсер новостей" напиши "Разработал сервис агрегации новостей с асинхронным сбором данных". Уже звучит как коммерческий опыт, правда? Делал мелкий фриланс? Это "опыт коммерческой разработки". Участвовал в хакатоне? "48-часовой спринт по разработке MVP" 🤔 Перестань бояться собеседований 80% кандидатов сливаются не на технических вопросах, а от собственного страха. Вместо "я на экзамене" думай "я пришёл поговорить о работе или потренироваться". Не знаешь ответ на вопрос? Проговори ход мысли: "С этой технологией не работал, но решал похожую задачу вот так..." Главное — не паникуй и не замыкайся. Работай системно, а не хаотично 30 минут в день — это имитация учёбы. Чтобы реально прогрессировать, нужно 2-4 часа сфокусированной работы. Веди простую табличку: дата отклика, компания, результат. И обязательно записывай, на каких вопросах "поплыл" — это покажет слабые места. Хватит полировать пет-проекты до идеала. Работает по README? Достаточно. Лучше потрать время на подготовку к собесам. Но это лишь верхушка айсберга. Реальность такова: большинство кандидатов сливаются на одних и тех же вопросах, которые HR и техлиды задают из раза в раз. Первый шаг — изучить те самые вопросы, на которых сыплется 80% middle Python разработчиков. Зная их заранее, ты перестанешь бояться собесов и начнёшь их уверенно проходить. 👉 Напиши Сергею "Хочу вопросы" — и получи эту базу. ⏰ Бонус для быстрых: те, кто напишут в течение 24 часов после этого поста, получат еще и пошаговый алгоритм трудоустройства до получения оффера — систему, позволяющую найти работу за 1,5 месяца вместо полугода попыток 💪

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 956. Tallest Billboard Сложность: hard Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0. Пример:

Input: rods = [1,2,3,6]
Output: 6

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

def minDeletionSize(strs):
    n = len(strs)
    m = len(strs[0])
    delete_count = [False] * m
    
    def is_sorted():
        for i in range(n - 1):
            for j in range(m):
                if delete_count[j]:
                    continue
                if strs[i][j] > strs[i + 1][j]:
                    return False
                if strs[i][j] < strs[i + 1][j]:
                    break
        return True
    
    while not is_sorted():
        for j in range(m):
            if delete_count[j]:
                continue
            for i in range(n - 1):
                if strs[i][j] > strs[i + 1][j]:
                    delete_count[j] = True
                    break
            if delete_count[j]:
                break
    
    return sum(delete_count)

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

Где вести задачи и проекты? Конечно, в Битрикс24 Бесплатный онлайн-сервис для бизнеса и совместной работы. Полный комплект для эффективности вашей команды. Ставьте первую задачу прямо сейчас Начать #реклама 16+ task-24.bitrix24.ru О рекламодателе

Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One Сложность: medium Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам: Если текущее число четное, его нужно разделить на 2. Если текущее число нечетное, нужно прибавить к нему 1. Гарантируется, что для всех тестовых случаев всегда можно достичь единицы. Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

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

class Solution:
    def numSteps(self, s: str) -> int:
        operations = 0
        s = list(s)
        
        while len(s) > 1:
            if s[-1] == '0':
                s.pop()
            else:
                i = len(s) - 1
                while i >= 0 and s[i] == '1':
                    s[i] = '0'
                    i -= 1
                if i < 0:
                    s.insert(0, '1')
                else:
                    s[i] = '1'
            operations += 1
        
        return operations

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

Бесплатный 14-дневный онлайн-курс по дизайну интерьеров Давно хочешь работать в творческой сфере и иметь доход от 100 тыс/мес? Тебе не нужно уметь рисовать или прямо сейчас принимать решение. Просто приходи и попробуй! Вдруг понравится создавать уютные интерьеры и ты найдешь в этом себя. Регистрируйся на практический курс по дизайну интерьера с личным наставником. Осталось 7 мест! Зарегистрироваться #реклама 16+ diskill.ru О рекламодателе

Задача: 1287. Element Appearing More Than 25% In Sorted Array Сложность: easy Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число. Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num. 2⃣Установите target = arr.length / 4. 3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение. 😎 Решение:

from collections import defaultdict

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        counts = defaultdict(int)
        target = len(arr) / 4
        for num in arr:
            counts[num] += 1
            if counts[num] > target:
                return num
        return -1

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 1252. Cells with Odd Values in a Matrix Сложность: easy Имеется матрица m x n, которая инициализирована всеми 0. Имеется двумерный массив indices, в котором каждый indices[i] = [ri, ci] представляет собой местоположение с индексом 0 для выполнения некоторых операций инкремента над матрицей. Для каждого местоположения indices[i] выполните оба следующих действия: увеличьте все ячейки в строке ri. Увеличьте все ячейки в столбце ci. Учитывая m, n и indices, верните количество нечетных ячеек в матрице после применения инкремента ко всем местоположениям в indices. Пример:

Input: nums = [12,5,7,23]
Output: true

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

def oddCells(m, n, indices):
    row_count = [0] * m
    col_count = [0] * n

    for r, c in indices:
        row_count[r] += 1
        col_count[c] += 1

    odd_count = 0
    for i in range(m):
        for j in range(n):
            if (row_count[i] + col_count[j]) % 2 == 1:
                odd_count += 1

    return odd_count

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

Задача: 287. Find the Duplicate Number Сложность: medium Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно. В массиве есть только одно повторяющееся число, верните это повторяющееся число. Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство. Пример:

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

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

class Solution:
    def findDuplicate(self, nums):
        duplicate = -1
        for i in range(len(nums)):
            cur = abs(nums[i])
            if nums[cur] < 0:
                duplicate = cur
                break
            nums[cur] *= -1
        for i in range(len(nums)):
            nums[i] = abs(nums[i])
        return duplicate

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