Python | LeetCode

Задача: 151. Reverse Words in a String Сложность: Medium Дана входная строка s, переверните порядок слов. Слово определяется как последовательность символов, не являющихся пробелами. Слова в строке s разделены как минимум одним пробелом. Верните строку, в которой слова расположены в обратном порядке, соединённые одним пробелом. Обратите внимание, что строка s может содержать пробелы в начале или в конце, или множественные пробелы между двумя словами. Возвращаемая строка должна содержать только один пробел, разделяющий слова. Не включайте лишние пробелы. Пример:

Input: s = "the sky is blue"
Output: "blue is sky the"

👨‍💻 Алгоритм: 1️⃣Удаление лишних пробелов: Удалите начальные и конечные пробелы из строки s. Это делается для того, чтобы убрать пробелы в начале и в конце строки, которые могут исказить конечный результат. В коде это реализовано с помощью методов erase и find_first_not_of/find_last_not_of, которые удаляют пробелы до первого и после последнего непробельного символа. 2️⃣Разделение строки на слова: Преобразуйте строку s в поток и используйте istringstream для чтения слов, разделенных пробелами. Каждое слово определяется как последовательность символов, не содержащая пробелов. Слова сохраняются в вектор words. Это делается с помощью copy, который копирует слова из потока в words с помощью istream_iterator. 3️⃣Реверсирование и соединение слов: Переверните вектор слов и соедините их обратно в одну строку, разделяя слова одним пробелом. Для реверсирования используется функция reverse, а для соединения слов — ostringstream вместе с ostream_iterator. Слова объединяются таким образом, что между ними находится только один пробел, исключая лишние пробелы между словами. 😎 Решение:

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.split()))

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

Google Meet перестал работать в России: что дальше? 📞🏃‍♂️ Сперва в Telegram и WhatsApp заблокировали звонки, а теперь и Google Meet сбоит. Видеозвонки не проходят ни с телефонов, ни с ПК. Для бизнеса это означает: - сорванные онлайн-совещания и встречи с клиентами; - срыв собеседований и переговоров с подрядчиками; - потерю времени и простои в коммуникациях команд; - срочный поиск альтернативы для видеозвонков и онлайн-летучек. Что делать бизнесу, когда зарубежные сервисы один за другим перестают работать в России? ✅ В МТС Линк: видеозвонки, чаты, онлайн-доски и совещания без сбоев и ограничений 40 минут; дата-центры в России, соответствие 152-ФЗ и 149-ФЗ; готовые интеграции; русскоязычная техподдержка 24/7. Проверьте, подходит ли МТС Линк вашей компании Узнать больше #реклама 16+ mts-link.ru О рекламодателе

Задача: 894. All Possible Full Binary Trees Сложность: medium Учитывая целое число n, верните список всех возможных полных бинарных деревьев с узлами. Каждый узел каждого дерева в ответе должен иметь Node.val == 0. Каждый элемент ответа является корневым узлом одного возможного дерева. Вы можете вернуть конечный список деревьев в любом порядке. Полное бинарное дерево - это бинарное дерево, в котором каждый узел имеет ровно 0 или 2 дочерних. Пример:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

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

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func allPossibleFBT(_ n: Int) -> [TreeNode?] {
    if n % 2 == 0 {
        return []
    }
    if n == 1 {
        return [TreeNode(0)]
    }
    
    var result = [TreeNode]()
    for i in stride(from: 1, to: n, by: 2) {
        let leftTrees = allPossibleFBT(i)
        let rightTrees = allPossibleFBT(n - 1 - i)
        for left in leftTrees {
            for right in rightTrees {
                result.append(TreeNode(0, left, right))
            }
        }
    }
    return result

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

Планы на пятницу в Нижнем — сходить на VK JT Meetup Привет, на связи VK! 3 октября мы собираем Java-разработчиков и ML-инженеров. Основная часть — доклады от наших лидов. Поговорим про Service Discovery в облаке, устройство единой платформы поиска VK, поделимся гайдом для выпуска готового RAG в прод. А дальше два потока на выбор: нетворкинг и командные решения кейсов на реальной архитектуре VK. Приходите задавать вопросы лидам, выигрывать призы и оставайтесь на ламповое афтепати! Нижний Новгород, только офлайн 📅 3 октября Участие по регистрации Подать заявку #реклама 16+ team.vk.company О рекламодателе

Задача: 898. Bitwise ORs of Subarrays Сложность: medium Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве. Пример:

Input: arr = [0]
Output: 1

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

def subarrayBitwiseORs(arr):
    result = set()
    current = set()
    for num in arr:
        current = {num | x for x in current} | {num}
        result.update(current)
    return len(result)

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

Приглашаем на Yandex Neuro Scale В этом году главная конференция Yandex Cloud объединит разработчиков, архитекторов, инженеров и IT-руководителей, чтобы обменяться опытом и увидеть, как работают технологии, которые меняют индустрии. 7 тематических треков, 50+ докладов, реальные бизнес-кейсы и нетворкинг! ✨Участие бесплатное, нужно только зарегистрироваться!✨ Зарегистрироваться #реклама 16+ scale.yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 1056. Confusing Number Сложность: easy Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно. При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае. Пример:

Input: n = 6
Output: true

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

def isConfusingNumber(n):
    rotation_map = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
    n_str = str(n)
    rotated_str = ""

    for char in n_str:
        if char not in rotation_map:
            return False
        rotated_str = rotation_map[char] + rotated_str

    return rotated_str != n_str

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

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)

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