Python | LeetCode

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 67. Add Binary Сложность: easy Даны две двоичные строки a и b. Верните их сумму в виде двоичной строки. Пример:

Input: a = "11", b = "1"
Output: "100"

👨‍💻 Алгоритм: 1️⃣Начните с переноса carry = 0. Если в числе a наименьший бит равен 1, добавьте 1 к carry. То же самое относится к числу b: если в числе b наименьший бит равен 1, добавьте 1 к carry. В этот момент carry для наименьшего бита может быть равен 0 (00), 1 (01) или 2 (10). 2️⃣Теперь добавьте наименьший бит carry к ответу и перенесите старший бит carry на следующий порядковый бит. 3️⃣Повторяйте те же шаги снова и снова, пока не будут использованы все биты в a и b. Если остаётся ненулевой carry, добавьте его. Теперь переверните строку ответа, и задача выполнена. 😎 Решение:

class Solution:
    def addBinary(self, a, b) -> str:
        n = max(len(a), len(b))
        a, b = a.zfill(n), b.zfill(n)

        carry = 0
        answer = []
        for i in range(n - 1, -1, -1):
            if a[i] == "1":
                carry += 1
            if b[i] == "1":
                carry += 1

            if carry % 2 == 1:
                answer.append("1")
            else:
                answer.append("0")

            carry //= 2

        if carry == 1:
            answer.append("1")
        answer.reverse()

        return "".join(answer)

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Открытые школы — это возможность за месяц прокачать свои навыки и получить оффер в ИТ-холдинг Т1. С тебя — год опыта работы в ИТ, с нас — бесплатный онлайн-интенсив и топовые преподаватели. Что ты получишь? ✅ Уникальный рыночный опыт. Наши проекты ежегодно получают награды на ИТ-конкурсах: Global CIO, Национальной банковской премии и др. ✅ Быстрый рост в ИТ при экспертной поддержке. ✅ Материалы от HR, которые помогут прокачать резюме и подготовиться к интервью в Т1. ✅ Поддержка опытных преподавателей и уникальный карьерный фаст-трек до мидла в Т1 для выпускников интенсива. ✅ Реальный шанс получить оффер в Т1. Подавай заявку до 11 апреля и приходи учиться! Старт ИТ-интенсива уже 14 апреля. Подать заявку #реклама 16+ t1.ru О рекламодателе

Задача: 1436. Destination City Сложность: easy Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi. Вернуть конечный город, то есть город, из которого нет пути в другой город. Гарантируется, что граф путей образует линию без циклов, поэтому будет ровно один конечный город. Пример:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

👨‍💻 Алгоритм: 1⃣Для каждого города cityBi в paths проверьте, является ли он кандидатом на конечный город. 2⃣Для каждого кандидата проверьте, нет ли пути, ведущего из него (cityAi == candidate). 3⃣Верните город, который не имеет исходящих путей. 😎 Решение:

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        for path in paths:
            candidate = path[1]
            good = True
            for p in paths:
                if p[0] == candidate:
                    good = False
                    break
            if good:
                return candidate
        return ""

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

Я поставил целью сбора скромные 300 тыс. рублей, но ребята, вы накидали больше млн. всего за 1 день. Это просто невероятно! Благодаря вашей поддержке, я смогу привлечь еще больше людей для разработки сайта и обработки собеседований. Ваш вклад сделает проект качественнее и ускорит его выход! Огромное вам спасибо! Краудфандинг будет продолжаться еще 31 день и все кто поддержать проект сейчас, до его выхода, смогут получить: 🚀 PRO-тариф на 1 год, по цене месячной подписки на релизе. ➕ Доступ к закрытому бета-тесту easyoffer 2.0 (середина–конец мая) Поддержать проект можно здесь: https://planeta.ru/campaigns/easyoffer Огромное спасибо за вашу поддержку! 🤝

Большая онлайн-конференция UserGate OpenConf ⚡ ИТ-конференция про защиту в открытую. Диалог между заказчиками, партнерами, экспертами и специалистами в сфере продуктов, технологий и услуг информационной безопасности. Зарегистрироваться #реклама 16+ openconf.usergate.com О рекламодателе

🎉 Краудфандинг easyoffer 2.0 стартовал! Друзья, с этого момента вы можете поддержать проект и получить существенный бонус: 🚀 PRO-тариф на 1 год, по цене месячной подписки на релизе. ➕ Доступ к закрытому бета-тесту easyoffer 2.0 (середина–конец мая) Поддержать проект можно здесь: https://planeta.ru/campaigns/easyoffer 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Задача: 913. Cat and Mouse Сложность: hard В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья. Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

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

from collections import deque

def catMouseGame(graph):
    n = len(graph)
    DRAW, MOUSE, CAT = 0, 1, 2
    dp = [[[DRAW] * 2 for _ in range(n)] for _ in range(n)]
    
    queue = deque()
    
    for i in range(1, n):
        dp[0][i][0] = MOUSE
        dp[0][i][1] = MOUSE
        dp[i][i][0] = CAT
        dp[i][i][1] = CAT
        queue.append((0, i, 0, MOUSE))
        queue.append((0, i, 1, MOUSE))
        queue.append((i, i, 0, CAT))
        queue.append((i, i, 1, CAT))
    
    def parents(mouse, cat, turn):
        if turn == 1:
            for m in graph[mouse]:
                yield (m, cat, 0)
        else:
            for c in graph[cat]:
                if c > 0:
                    yield (mouse, c, 1)
    
    while queue:
        mouse, cat, turn, winner = queue.popleft()
        for m, c, t in parents(mouse, cat, turn):
            if dp[m][c][t] == DRAW:
                if t == 0 and winner == MOUSE or t == 1 and winner == CAT:
                    dp[m][c][t] = winner
                    queue.append((m, c, t, winner))
                else:
                    degrees = sum(1 for p in parents(m, c, t))
                    if degrees == 0:
                        dp[m][c][t] = winner
                        queue.append((m, c, t, winner))
    
    return dp[1][2][0]

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

Открыт доступ к курсу «Создание и развитие продукта» Пройдете путь от генерации идей до создания и непрерывного улучшения востребованного на рынке продукта или сервиса. Вы научитесь: ✅ Разрабатывать и запускать MVP — тестировать идеи с минимальными затратами и превращать их в работающие продукты. ✅ Готовить продукт к первым продажам — используя метод CRL, сможете говорить с инвестором на одном языке и оценивать коммерческие риски. ✅ Управлять развитием продукта — находить точки роста, считать ключевые метрики и улучшать продукт на основе данных. Курс ведут лучшие эксперты из ведущих компаний: OZON, Сбер, «Лебер Групп», Huntflow и других. Попробуйте бесплатно — откроем полный доступ к курсу на 2 дня. За это время вы сможете познакомиться с платформой, посмотреть лекции и выполнить задания. Попробовать #реклама 16+ product.school.gd.ru О рекламодателе

Задача: 922. Sort Array By Parity II Сложность: medium Дан массив целых чисел nums, половина целых чисел в нем нечетные, а другая половина - четные. Отсортируйте массив так, чтобы во всех случаях, когда nums[i] нечетный, i был нечетным, а во всех случаях, когда nums[i] четный, i был четным. Верните любой массив ответов, удовлетворяющий этому условию. Пример:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

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

def sortArrayByParityII(nums):
    result = [0] * len(nums)
    even_idx, odd_idx = 0, 1
    for num in nums:
        if num % 2 == 0:
            result[even_idx] = num
            even_idx += 2
        else:
            result[odd_idx] = num
            odd_idx += 2
    return result

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

Нанимаете аутсорс, подрядчиков, фрилансеров? Попробуйте Битрикс24 Коллабы – платформа для эффективной работы с подрядчиками. Тут обсуждения превращаются в задачи, а видео созвон можно собрать одной кнопкой. Любой проект можно разложить по полочкам с понятным ТЗ и обозначенными сроками. Работайте в Битрикс24 и создавайте Коллабы с подрядчиками. Начать #реклама 16+ collabs.bitrix24.ru О рекламодателе

Задача: 1197. Minimum Knight Moves Сложность: medium На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0]. У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении. Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует. Пример:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

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

from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        offsets = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
        
        origin_queue = deque([(0, 0, 0)])
        origin_distance = {"0,0": 0}
        
        target_queue = deque([(x, y, 0)])
        target_distance = {f"{x},{y}": 0}
        
        while True:
            ox, oy, od = origin_queue.popleft()
            origin_key = f"{ox},{oy}"
            if origin_key in target_distance:
                return od + target_distance[origin_key]
            
            tx, ty, td = target_queue.popleft()
            target_key = f"{tx},{ty}"
            if target_key in origin_distance:
                return td + origin_distance[target_key]
            
            for dx, dy in offsets:
                next_origin = (ox + dx, oy + dy, od + 1)
                next_origin_key = f"{next_origin[0]},{next_origin[1]}"
                if next_origin_key not in origin_distance:
                    origin_queue.append(next_origin)
                    origin_distance[next_origin_key] = next_origin[2]
                
                next_target = (tx + dx, ty + dy, td + 1)
                next_target_key = f"{next_target[0]},{next_target[1]}"
                if next_target_key not in target_distance:
                    target_queue.append(next_target)
                    target_distance[next_target_key] = next_target[2]

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

Почему вы не используете Битрикс24 CRM с AI-помощником? 1- не знал 2- забыл Рассказываем и напоминаем! ✅Битрикс24 CRM с AI помогает увеличивать продажи, работать с постоянными клиентами и сохранять все важные данные. AI-помощник CoPilot внутри сервиса расшифрует телефонные разговоры и автоматически заполнит карточки клиента в CRM. Битрикс24 можно использовать бесплатно для всех команд, независимо от их размера. ⚡Не тратьте время на рутину. Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

Задача: 1266. Minimum Time Visiting All Points Сложность: easy На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение. Пример:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7

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

def minTimeToVisitAllPoints(points):
    def distance(p1, p2):
        return max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))

    time = 0
    for i in range(len(points) - 1):
        time += distance(points[i], points[i + 1])
    return time

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

На easyoffer 2.0 появится: База тестовых заданий 🟠Тестовые задания для разных грейдов 🟠Фильтрация тестовых заданий по технологиям и компаниям Когда я только начинал учиться на программиста, я постоянно выдумывал себе задачи для практики и тратил на это много времени. Но только в момент поиска работы я столкнулся с тестовыми заданиями, и понял насколько круто они прокачивают навыки. Нужно было еще на этапе обучения пробовать их делать. Все компании стараются составить тестовое задание "под себя", это дает большой выбор в тематике задач и технологий. На easyoffer 2.0 вы сможете отфильтровать тестовые задания по навыкам/грейдам и найти те, что подходят лично вам для практики. В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус. 🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 935. Knight Dialer Сложность: medium Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке). Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7. Пример:

Input: n = 1
Output: 10

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

MOD = 10**9 + 7

def knightDialer(n):
    moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [0, 3, 9],
        5: [],
        6: [0, 1, 7],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4]
    }
    
    dp = [1] * 10
    
    for _ in range(n - 1):
        new_dp = [0] * 10
        for i in range(10):
            for move in moves[i]:
                new_dp[move] = (new_dp[move] + dp[i]) % MOD
        dp = new_dp
    
    return sum(dp) % MOD

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

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

Задача: 1103. Distribute Candies to People Сложность: easy Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом: Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку. Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку. Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз). Верните массив (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет. Пример:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

👨‍💻 Алгоритм: 1⃣Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты: p = floor(sqrt(2C+0.25)-0.5) remainig = C - p(p+1)/2 2⃣Вычислите количество полных циклов и распределите конфеты: rows = p // n d[i]= i*rows + n*rows*(rows-1)/2 3⃣Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты: d[i]+=i+n⋅rows для первых p%n людей d[p%n]+=remaining Верните распределение конфет d 😎 Решение:

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        n = num_people
        p = int((2 * candies + 0.25)**0.5 - 0.5)
        remaining = int(candies - (p + 1) * p * 0.5)
        rows, cols = p // n, p % n
        
        d = [0] * n
        for i in range(n):
            d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n
            if i < cols:
                d[i] += i + 1 + rows * n
        d[cols] += remaining
        return d

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

Битрикс24 💻Один онлайн-сервис для совместной работы. 📱10+ инструментов. ✅0 денег. Счастливые сотрудники. Прибыльный бизнес. Регистрируйтесь и забирайте себе Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе