Python | LeetCode

Зарабатывайте на установках Яндекс Браузера Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей. Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках. Выплаты до 500₽ за каждую установку Яндекс Браузера. Подать заявку #реклама 0+ partner.browser.yandex.ru О рекламодателе

Задача: 1218. Longest Arithmetic Subsequence of Given Difference Сложность: medium Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference. Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов. Пример:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1. 2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]: Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference: - если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference]. - в противном случае, установите before_a = 0. Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]). 3⃣Верните answer после завершения итерации. 😎 Решение:

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        answer = 1
        
        for a in arr:
            before_a = dp.get(a - difference, 0)
            dp[a] = before_a + 1
            answer = max(answer, dp[a])
        
        return answer

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

Нейросеть проверит 100% закупок на стройке за минуты! 👍Контроль закупок за 15 минут в день. Нейросеть "Тринити" экономит ваше время и миллионы рублей Вы - генеральный директор строительной компании, и у вас катастрофически не хватает времени? Работаете 12+ часов в день и не можете контролировать каждую закупку? 💰Тратите миллионы на закупки, но не уверены, что получаете лучшие цены и качество? Хотите спать спокойно, зная, что ваши деньги под защитой? Просто загрузите счет или тендерный протокол в Telegram-бот Получите детальный анализ по 18 параметрам за 1 минуту Экономьте до 10% на каждой закупке без дополнительных усилий В 3-5 раз дешевле, чем содержать штат контролеров! Работает 24/7 без выходных и отпусков. 👌Узнайте про наш телеграм-бот и тестируйте бесплатно 15 дней! Экономия в первый же день. Перейти на сайт #реклама 16+ trinitysafe.ru О рекламодателе

Задача: 921. Minimum Add to Make Parentheses Valid Сложность: medium Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой. Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

def minAddToMakeValid(s: str) -> int:
    open_needed = close_needed = 0
    for char in s:
        if char == '(':
            open_needed += 1
        elif char == ')':
            if open_needed > 0:
                open_needed -= 1
            else:
                close_needed += 1
    return open_needed + close_needed

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

Айтишники, это вам — в телеграм есть комьюнити по каждому направлению в IT Там есть буквально всё: чаты для общения, тонны материала(книги, курсы, ресурсы и гайды), свежие новости и конечно же мемы Выбирайте своё направление: 💩 Frontend 🐍 Python 🐧 Linux 👩‍💻 С/С++ 👩‍💻 C# 🤔 Хакинг & ИБ 📱 GitHub 🖥 SQL 👩‍💻 Сисадмин 🤟 DevOps ⚙️ Backend 🖥 Data Science 🧑‍💻 Java 🐞 Тестирование 🖥 PM / PdM 👩‍💻 GameDev 🧑‍💻 Golang 👣 Rust 🧑‍💻 PHP 💻 WebDev 🖥 Моб. Dev 🖥Анали.(SA&BA) 👩‍💻 Дизайн 🖥 Нейросети 💛 1C 🤓 Книги IT ➡️ Сохраняйте в закладки

Высшее образование онлайн — поменяйте жизнь в 2025 году! ✅Набор в июне: от 6700 ₽/мес.* Московский технологический институт предлагает: — Высшее образование в московском вузе без выезда на сессии — Полностью дистанционный онлайн-формат — Возможность обучаться дома, на работе, в путешествии — Диплом государственного образца — Более 60 направлений на выбор (IT, инженерные, экономические, педагогические, управленческие и другие) — 5 способов оплаты обучения — Поддержка персонального куратора: от поступления до получения диплома Узнать больше #реклама 16+ mti-vuz.ru О рекламодателе

Задача: №19. Remove Nth Node From End of List Сложность: medium Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок. Пример:

Input: head = [1,2,3,4,5], n = 2  
Output: [1,2,3,5]  

👨‍💻 Алгоритм: 1️⃣Определяем размер списка, проходя по нему один раз. 2️⃣Если n равен размеру списка, удаляем первый узел, возвращая head.next. 3️⃣Идем по списку до узла перед удаляемым, меняем ссылки, исключая n-й узел. 😎 Решение:

# class ListNode:  
#     def __init__(self, x):  
#         self.val = x  
#         self.next = None  

class Solution:  
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:  
        if head.next is None:  
            return None  

        tmp = head  
        size = 0  

        while tmp:  
            size += 1  
            tmp = tmp.next  
        tmp = head  

        if n == size:  
            return head.next  

        for i in range(size - n - 1):  
            tmp = tmp.next  
        tmp.next = tmp.next.next  
        return head

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

Пройди практику в Wildberries&Russ и получи диплом ТГУ Хочешь развивать карьеру в аналитике и не тратить на это 10 лет? Магистратура «Дата-аналитика для бизнеса» ускорит! В ней ты: ⚡Прокачаешь навыки работы с Big Data и искусственным интеллектом в бизнесе с экспертами Wildberries & Russ, других топ-компаний и преподавателями ТГУ. ⚡3 специализации на выбор: продуктовая аналитика, маркетинговая аналитика и BI/бизнес-аналитика — выбирай то, что ближе к твоим целям. ⚡Получишь возможность пройти стажировку в Wildberries & Russ. Учёба онлайн — с гибким графиком из любой точки мира. Оставляй заявку, а мы проконсультируем, как :) Узнать больше #реклама 16+ ai.tsu.ru О рекламодателе

Задача: 724. Find Pivot Index Сложность: easy Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1. Пример:

Input: nums = [1,7,3,6,5,6]
Output: 3

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

def pivotIndex(nums):
    total_sum = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        if left_sum == (total_sum - left_sum - num):
            return i
        left_sum += num
    return -1

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

Задача: 408. Valid Word Abbreviation Сложность: easy Строку можно сократить, заменив любое количество не смежных, непустых подстрок их длинами. Длины не должны содержать ведущих нулей. Например, строка "замена" может быть сокращена следующим образом (но не ограничивается этим): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("замена") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замены подстрок) Следующие сокращения не являются допустимыми: "s55n" ("s ubsti tutio n", заменяемые подстроки смежные) "s010n" (содержит ведущие нули) "s0ubstitution" (заменяет пустую подстроку) Если задано строковое слово и аббревиатура abbr, верните, соответствует ли строка заданной аббревиатуре. Подстрока - это непрерывная непустая последовательность символов в строке. Пример:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true

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

def validWordAbbreviation(word, abbr):
    i = j = 0
    while i < len(word) and j < len(abbr):
        if abbr[j].isdigit():
            if abbr[j] == '0':
                return False
            num = 0
            while j < len(abbr) and abbr[j].isdigit():
                num = num * 10 + int(abbr[j])
                j += 1
            i += num
        else:
            if word[i] != abbr[j]:
                return False
            i += 1
            j += 1
    return i == len(word) and j == len(abbr)

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

Гайд для маркетологов по эффективным онлайн-встречам Как CMO, PR и digital-маркетологам повысить результативность брейнштормов, совещаний и планерок с командой с помощью онлайн-встреч? Гайд МТС Линк: 37 страниц полезных материалов, чек-листов и кейсов для эффективных видеовстреч и совещаний. ✅ В гайде: - Как создать постоянную ссылку на регулярные встречи с подрядчиками, командой или агентствами и подключаться в 2 клика; - Как управлять встречей и завершить ее четкими договоренностями с ИИ-расшифровкой голоса в текст; - Как проводить кастдевы, брейнштормы и формулировать гипотезы с помощью 15+ шаблонов в онлайн-досках МТС Линк; - Как разом пригласить всех участников на синк таким образом, чтобы все пришли. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 1066. Campus Bikes II Сложность: medium На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке. Мы назначаем каждому рабочему уникальный велосипед таким образом, чтобы сумма Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом была минимальной. Верните минимально возможную сумму Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом. Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|. Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

👨‍💻 Алгоритм: 1⃣Для каждого рабочего, начиная с рабочего с индексом 0, пройдите по всем велосипедам и назначьте велосипед рабочему, если он доступен (visited[bikeIndex] = false). После назначения велосипеда отметьте его как недоступный (visited[bikeIndex] = true). Добавьте Манхэттенское расстояние от этого назначения к общей текущей сумме расстояний, представленной currDistanceSum, и выполните рекурсивный вызов для следующего рабочего. 2⃣Когда рекурсивный вызов завершится, сделайте велосипед снова доступным, установив visited[bikeIndex] в false. Если мы назначили велосипеды всем рабочим, сравните currDistanceSum с smallestDistanceSum и обновите smallestDistanceSum соответственно. 3⃣Перед назначением любого велосипеда рабочему, проверьте, если currDistanceSum уже больше или равен smallestDistanceSum. Если это так, пропустите остальных рабочих и вернитесь. Это связано с тем, что currDistanceSum может только увеличиваться, и таким образом мы не найдем лучший результат, чем smallestDistanceSum, используя текущую комбинацию рабочих и велосипедов. 😎 Решение:

class Solution:
    def __init__(self):
        self.smallestDistanceSum = float('inf')
        self.visited = [False] * 10
    
    def findDistance(self, worker, bike):
        return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
    
    def minimumDistanceSum(self, workers, workerIndex, bikes, currDistanceSum):
        if workerIndex >= len(workers):
            self.smallestDistanceSum = min(self.smallestDistanceSum, currDistanceSum)
            return
        
        if currDistanceSum >= self.smallestDistanceSum:
            return
        
        for bikeIndex in range(len(bikes)):
            if not self.visited[bikeIndex]:
                self.visited[bikeIndex] = True
                self.minimumDistanceSum(workers, workerIndex + 1, bikes, 
                    currDistanceSum + self.findDistance(workers[workerIndex], bikes[bikeIndex]))
                self.visited[bikeIndex] = False
    
    def assignBikes(self, workers, bikes):
        self.minimumDistanceSum(workers, 0, bikes, 0)
        return self.smallestDistanceSum

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

🤖 Знаете, чем настоящий AI отличается от чат-бота? Чат-бот просит перезагрузить роутер, а настоящий AI уже умеет читать ваши эмоции в чате, включать музыку под ваше настроение, контролировать погрузку руды с точностью Терминатора и даже находить на КТ-снимках то, чего не заметит человеческий глаз. Современные компании для таких задач всё чаще используют Deep Learning — алгоритмы на основе нейросетей. Но чтобы попасть в эту лигу, нужен фундамент. И имя ему — Machine Learning. Наш новый курс по ML — это не волшебная таблетка. Это честный и структурированный путь в мир Data Science. Мы дадим вам базу, с которой вы: ✅ разберётесь, как мыслят машины (спойлер: матрицами!); ✅ научитесь строить работающие модели, а не карточные домики; ✅ получите трамплин для прыжка в Deep Learning. Хватит смотреть, как другие запускают ракеты. Пора строить свой собственный космодром. Начните с фундамента на нашем курсе по Machine Learning

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

Задача: 651. 4 Keys Keyboard Сложность: medium Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш. Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

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

def maxA(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + 1
        for j in range(2, i):
            dp[i] = max(dp[i], dp[j - 2] * (i - j + 1))
    return dp[n]

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

⚡️Готовиться к собеседованиям стало проще! Женя Янченко, backend-dev и руководитель разработки, cделала конспекты самой популярной книги по архитектуре систем — «Высоконагруженные приложения» Мартина Клеппмана (книга с кабанчиком). Подробные разборы репликации, шардирования, транзакций: ▶️ ЧИТАТЬ КОНСПЕКТ КАБАНЧИКА В канале Женя разбирает и другие технические темы, особенно те, которые могут пригодиться на собесе по system design: 🟡 CAP-теорема простыми словами 🟡 Сравнение Kafka и RabbitMQ 🟡 API Gateway 🟡 Load Balancer А как же алгоритмы? Они тоже есть! В феврале Женя объявила челлендж — решить 300 задач за год 😱 и недавно стала делать разборы популярных задач: 🟡Разбор паттерна "Два указателя" Истории из опыта, рекомендации и ответы на вопросы: 🟡«Ты не оправдываешь ожиданий» и что с этим делать 🟡Про манипуляции менеджеров 🟡Как я боролась с неуверенностью в себе 🟡«Просто нажми кнопку» или история одного релиза 📝 и ещё 100+ полезных технических и жизненных постов. Подписывайтесь, чтобы не потерять полезный канал @jane_yanchenko

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 600. Non-negative Integers without Consecutive Ones Сложность: hard Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц. Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

👨‍💻 Алгоритм: 1⃣Простой метод заключается в переборе всех чисел от 1 до num. Для каждого текущего выбранного числа проверяем все соседние позиции, чтобы выяснить, содержит ли число две последовательные единицы. Если не содержит, увеличиваем количество чисел без последовательных единиц. 2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x. 3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц. 😎 Решение:

class Solution:
    def findIntegers(self, num: int) -> int:
        def check(n):
            i = 31
            while i > 0:
                if (n & (1 << i)) != 0 and (n & (1 << (i - 1))) != 0:
                    return False
                i -= 1
            return True

        count = 0
        for i in range(num + 1):
            if check(i):
                count += 1
        return count

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

Регистрируйтесь на Yandex Ecom Open Air 8 августа Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

Задача: 1122. Relative Sort Array Сложность: easy Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1. Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания. Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

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

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        countMap = {value: 0 for value in arr2}
        remaining = []
        result = []

        for value in arr1:
            if value in countMap:
                countMap[value] += 1
            else:
                remaining.append(value)

        remaining.sort()

        for value in arr2:
            result.extend([value] * countMap[value])

        result.extend(remaining)
        return result

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