Python | LeetCode

Такого ещё не было - Битрикс24 со скидкой 30% на год - Плюс бонус 100 000 рублей на ИИ-помощника ✨Автоматизируйте задачи, не теряйте клиентов и экономьте деньги. Выгодно? — Да. Надо брать? — Однозначно. 🏃‍♂️Успей Акция действует до 30 апреля при покупке лицензии Битрикс24 на 12 месяцев, AI-помощник предоставляется за 1 ₽. Правила акции на сайте по ссылке: Узнать больше #реклама 16+ ai-sale.bitrix24.ru О рекламодателе

Задача: 1431. Kids With the Greatest Number of Candies Сложность: easy Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть. Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае. Обратите внимание, что несколько детей могут иметь наибольшее количество конфет. Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

👨‍💻 Алгоритм: 1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies. 2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false. 3⃣Верните список answer. 😎 Решение:

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        maxCandies = max(candies)
        return [candy + extraCandies >= maxCandies for candy in candies]

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

Заработайте 3000Р за рекомендацию счёта для бизнеса Участвуйте в реферальной программе СберБизнеса и получите промокод на 3000 ₽ в Купер. Как это работает: ✅ Вы делитесь ссылкой на открытие счёта для бизнеса; ✅ Друг открывает счёт и пользуется им; ✅ Через 2 месяца вы получаете промокод на 3000 ₽ в Купер, а друг – 3000 ₽ на открытый счёт. Присоединяйтесь к реферальной программе СберБизнеса и зарабатывайте. Участвовать можно неограниченное количество раз. Узнать больше Финансовые услуги оказывает: ПАО Сбербанк. #реклама sberbank.com О рекламодателе

Задача: 1250. Check If It Is a Good Array Сложность: hard Дан массив nums из целых положительных чисел. Ваша задача - выбрать некоторое подмножество nums, умножить каждый элемент на целое число и сложить все эти числа.Массив считается хорошим, если из него можно получить сумму, равную 1, при любом возможном подмножестве и множителе. Верните True, если массив хороший, иначе верните False. Пример:

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

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

import math
from functools import reduce

def isGoodArray(nums):
    return reduce(math.gcd, nums) == 1

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

Задача: 1062. Longest Repeating Substring Сложность: medium Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0. Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

class Solution:
    def search(self, L, n, S):
        seen = set()
        for start in range(n - L + 1):
            tmp = S[start:start + L]
            if tmp in seen:
                return start
            seen.add(tmp)
        return -1

    def longestRepeatingSubstring(self, S):
        n = len(S)
        left, right = 1, n
        while left <= right:
            L = left + (right - left) // 2
            if self.search(L, n, S) != -1:
                left = L + 1
            else:
                right = L - 1
        return left - 1

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

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

Задача: 815. Bus Routes Сложность: hard Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно. Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно. Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах. Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно. Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

👨‍💻 Алгоритм: 1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis. 2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными. 3⃣Верните -1 после завершения обхода в ширину (BFS). 😎 Решение:

class Solution:
    def numBusesToDestination(self, routes, source, target):
        if source == target:
            return 0
        
        from collections import defaultdict, deque
        
        adjList = defaultdict(list)
        for route, stops in enumerate(routes):
            for stop in stops:
                adjList[stop].append(route)
        
        q = deque()
        vis = set()
        for route in adjList[source]:
            q.append(route)
            vis.add(route)
        
        busCount = 1
        while q:
            for _ in range(len(q)):
                route = q.popleft()
                for stop in routes[route]:
                    if stop == target:
                        return busCount
                    for nextRoute in adjList[stop]:
                        if nextRoute not in vis:
                            vis.add(nextRoute)
                            q.append(nextRoute)
            busCount += 1
        return -1

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

Получайте больше продаж из поиска Яндекса Анализируйте метрики и получайте рекомендации для роста продаж в Яндекс Товарах ⚡ Попробовать #реклама merchants.yandex.ru О рекламодателе

Задача: 1058. Minimize Rounding Error to Meet Target Сложность: medium Учитывая массив цен [p1,p2...,pn] и цель, округлите каждую цену pi до Roundi(pi) так, чтобы округленный массив [Round1(p1),Round2(p2)...,Roundn(pn)] в сумме достиг заданной цели. Каждая операция Roundi(pi) может быть либо Floor(pi), либо Ceil(pi). Верните строку "-1", если округленный массив невозможно привести к целевому значению. В противном случае возвращается наименьшая ошибка округления, которая определяется как Σ |Roundi(pi) - (pi)| для i от 1 до n, в виде строки с тремя местами после десятичной дроби. Пример:

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

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

import math

def minimizeRoundingError(prices, target):
    floors = [math.floor(float(p)) for p in prices]
    ceils = [math.ceil(float(p)) for p in prices]
    total_floor = sum(floors)
    
    difference = target - total_floor
    if difference < 0 or difference > len(prices):
        return "-1"
    
    rounding_errors = [(ceil - floor, float(p) - floor) for p, floor, ceil in zip(prices, floors, ceils)]
    rounding_errors.sort(key=lambda x: x[1])
    
    rounding_error_sum = sum(floor - float(p) for floor, p in zip(floors, prices))
    
    for i in range(difference):
        rounding_error_sum += 1
    
    for i in range(difference):
        rounding_error_sum += rounding_errors[i][1]
    
    return "{:.3f}".format(rounding_error_sum)

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

Получи грант на обучение в Центральном университете Центральный университет выдает гранты на 4 года обучения в бакалавриате. Грант покрывает до 100% стоимости обучения. Участвуй в отборе, чтобы получить грант. Получи доступ к уникальным активностям для абитуриентов. Для выпускников 10-х, 11-х классов и колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 1087. Brace Expansion Сложность: medium Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента. Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания. Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления. Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

👨‍💻 Алгоритм: 1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку. 2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString. 3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords. 😎 Решение:

class Solution:
    def storeFirstOptions(self, s: str, startPos: int, firstOptions: List[str]) -> int:
        if s[startPos] != '{':
            firstOptions.append(s[startPos])
        else:
            startPos += 1
            while s[startPos] != '}':
                if s[startPos].islower():
                    firstOptions.append(s[startPos])
                startPos += 1
            firstOptions.sort()
        return startPos + 1

    def findAllWords(self, s: str, startPos: int) -> List[str]:
        if startPos == len(s):
            return [""]
        
        firstOptions = []
        remStringStartPos = self.storeFirstOptions(s, startPos, firstOptions)
        wordsWithRemString = self.findAllWords(s, remStringStartPos)
        
        expandedWords = []
        for c in firstOptions:
            for word in wordsWithRemString:
                expandedWords.append(c + word)
        return expandedWords

    def expand(self, s: str) -> List[str]:
        return self.findAllWords(s, 0)

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

Привет ребята, мне на easyoffer.ru нужен: 🐍 Middle/Senior Python Developer Стек: DRF, PostgreSQL, Redis, Celery, Docker, Sentry Задачи: 🟠Разработка и поддержка REST API для новых фичей 🟠Интеграция с веб-сервисами и внешними API 🟠Подключение и поддержка платежных систем 🟠Написание юнит- и интеграционных тестов 🟠Оптимизация производительности и масштабирование 🟠Взаимодействие с ML-моделями — будет плюсом Ожидания: 🟠2+ лет опыта DRF 🟠Опыт интеграций платежных систем 🟠Опыт работы с PostgreSQL, Celery, Redis, Docker 🟠Умение проектировать архитектуру REST-API 🟠Ответственный подход к качеству кода и тестированию Опыт в стартапах и небольших командах будет плюсом Условия: – Частичная занятость (2-3 часа в день) – Удаленная работа – Свободный график – Почасовая оплата ✈ Если вас заинтересовала вакансия, напишите мне @kivaiko 1. Резюме 2. Ссылку на github 3. Комфортную ставку за час

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по 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

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