Python | LeetCode

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 1242. Web Crawler Multithreaded Сложность: medium Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Пример:

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

👨‍💻 Алгоритм: 1⃣Извлечь имя хоста из startUrl. Использовать многопоточность для обработки URL-адресов. 2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения. 3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц. 😎 Решение:

from concurrent.futures import ThreadPoolExecutor
from urllib.parse import urlparse
import threading

class HtmlParser:
    def getUrls(self, url: str) -> [str]:
        pass

def extract_hostname(url):
    parsed_url = urlparse(url)
    return parsed_url.netloc

def crawl(startUrl, htmlParser):
    hostname = extract_hostname(startUrl)
    visited = set()
    lock = threading.Lock()

    def visit(url):
        if extract_hostname(url) == hostname:
            with lock:
                if url not in visited:
                    visited.add(url)
                    for next_url in htmlParser.getUrls(url):
                        executor.submit(visit, next_url)

    with ThreadPoolExecutor(max_workers=10) as executor:
        executor.submit(visit, startUrl)

    return list(visited)

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

Устроиться фронтендером в Яндекс за выходные 26–27 апреля устраиваем Weekend Offer Frontend. До 23 апреля оставьте заявку на участие, 26 апреля пройдите технические собеседования, а 27 апреля познакомьтесь с командами и получите офер. В мероприятии участвует 10 команд. Это команды Поиска: Еком-сценарии, Архитектура, Международный Поиск, Красота, Финансы, Видеопоиск. И команды Вертикалей: Путешествия, Недвижимость, Аренда, Авто.ру. Вы сможете пообщаться с менеджерами и выбрать проект, который покажется самым интересным. Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 1213. Intersection of Three Sorted Arrays Сложность: easy Даны три целочисленных массива arr1, arr2 и arr3, отсортированных в строго возрастающем порядке. Верните отсортированный массив, содержащий только те целые числа, которые присутствуют во всех трех массивах. Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

class Solution:
    def arraysIntersection(self, arr1, arr2, arr3):
        from collections import Counter

        counter = Counter(arr1) + Counter(arr2) + Counter(arr3)
        return [num for num, freq in counter.items() if freq == 3]

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

Качаем скиллы PostgreSQL на PG BootCamp Russia 2025! Регистрируйся на бесплатную конференцию по PostgreSQL — 10.04.2025.📅 ✅ Бесплатное участие ✅ Опытные спикеры ✅ Тематические доклады ✅ Рабочие кейсы Каждый участник получает именной Сертификат участника мероприятия. Одни из немногих спикеров конференции: — Андрей Бородин PostgreSQL contributor, руководитель подразделения разработки РСУБД с открытым исходным кодом Yandex Cloud — Александр Никитин Ведущий администратор БД DBA.Team — Максим Милютин PostgreSQL Contributor, openGauss Contributor ... и многие другие. Регистрируйся, будет интересно! И бесплатно! Зарегистрироваться #реклама pgbootcamp.ru О рекламодателе

Задача: 996. Number of Squareful Arrays Сложность: hard Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i]. Пример:

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

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

from itertools import permutations
import math

class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        def isPerfectSquare(x):
            return int(math.isqrt(x)) ** 2 == x
        
        def isSquareful(perm):
            for i in range(len(perm) - 1):
                if not isPerfectSquare(perm[i] + perm[i + 1]):
                    return False
            return True
        
        perms = set(permutations(nums))
        count = sum(1 for perm in perms if isSquareful(perm))
        return count

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

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

Задача: 1102. Path With Maximum Minimum Value Сложность: medium Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях. Значение пути определяется минимальным числом на этом пути. Пример:

Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow. 

👨‍💻 Алгоритм: 1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы. 2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore: Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore. Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди. Если успешно достигли правой нижней ячейки, значит путь существует. Если очередь опустела до достижения правой нижней ячейки, пути не существует. 3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2. В противном случае, верните curScore как ответ. 😎 Решение:

from collections import deque

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        def pathExists(curScore):
            R, C = len(grid), len(grid[0])
            visited = [[False] * C for _ in range(R)]
            dq = deque([(0, 0)])
            visited[0][0] = True

            def push(row, col):
                if 0 <= row < R and 0 <= col < C and not visited[row][col] and grid[row][col] >= curScore:
                    dq.append((row, col))
                    visited[row][col] = True

            while dq:
                curRow, curCol = dq.popleft()
                if curRow == R - 1 and curCol == C - 1:
                    return True

                for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    push(curRow + dr, curCol + dc)

            return False

        curScore = min(grid[0][0], grid[-1][-1])
        while curScore >= 0:
            if pathExists(curScore):
                return curScore
            curScore -= 1
        return -1

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

Ищешь высокооплачиваемые проекты? Попробуй 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]

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