Python | LeetCode

Задача: 40. Combination Sum II Сложность: medium Дана коллекция кандидатов (candidates) и целевое число (target). Найдите все уникальные комбинации в candidates, где числа кандидатов в сумме дают target. Каждое число в candidates может быть использовано только один раз в комбинации. Примечание: Набор решений не должен содержать повторяющихся комбинаций. Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

👨‍💻 Алгоритм: 1️⃣Во-первых, мы создаём таблицу счётчиков из предоставленного списка чисел. Затем мы используем эту таблицу счётчиков в процессе обратного поиска, который мы определяем как функцию backtrack(comb, remain, curr, candidate_groups, results). Для сохранения состояния на каждом этапе обратного поиска мы используем несколько параметров в функции: comb: комбинация, которую мы построили на данный момент. remain: оставшаяся сумма, которую нам нужно заполнить, чтобы достичь целевой суммы. curr: курсор, который указывает на текущую группу чисел, используемую из таблицы счётчиков. counter: текущая таблица счётчиков. results: окончательные комбинации, которые достигают целевой суммы. 2️⃣При каждом вызове функции обратного поиска мы сначала проверяем, достигли ли мы целевой суммы (то есть sum(comb) = target), и нужно ли прекратить исследование, потому что сумма текущей комбинации превышает желаемую целевую сумму. 3️⃣Если осталась сумма для заполнения, мы затем перебираем текущую таблицу счётчиков, чтобы выбрать следующего кандидата. После выбора кандидата мы продолжаем исследование, вызывая функцию backtrack() с обновлёнными состояниями. Более важно, что в конце каждого исследования нам нужно вернуть состояние, которое мы обновили ранее, чтобы начать с чистого листа для следующего исследования. Именно из-за этой операции обратного поиска алгоритм получил своё название. 😎 Решение:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        def backtrack(comb, remain, curr, counter, results):
            if remain == 0:
                results.append(list(comb))
                return
            elif remain < 0:
                return

            for next_curr in range(curr, len(counter)):
                candidate, freq = counter[next_curr]

                if freq <= 0:
                    continue

                comb.append(candidate)
                counter[next_curr] = (candidate, freq - 1)
                backtrack(comb, remain - candidate, next_curr, counter, results)
                counter[next_curr] = (candidate, freq)
                comb.pop()

        results = []
        counter = Counter(candidates)
        counter = [(c, counter[c]) for c in counter]

        backtrack(
            comb=[], remain=target, curr=0, counter=counter, results=results
        )

        return results

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

⏳ Осталось 3 дня! Финальный отсчёт пошёл — осталось всего 3 дня до окончания краудфандинга easyoffer 2.0 Сейчас можно получить максимум пользы за минимальные деньги. После окончания кампании цены вырастут и вознаграждения станут недоступны. 👉 Поддержи easyoffer 2.0 и получи: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование Поддержи проект сейчас, чтобы не забыть! 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Теперь AI сам создает сайты ИИшка в Битрикс24 берёт на себя весь процесс: структура, дизайн, контент — всё создаётся автоматически. Сделайте один запрос AI-помощнику, и через 30 секунд он создаст свой вариант полностью работающего сайта. Узнать больше #реклама sites-24.bitrix24.ru О рекламодателе

Задача: 918. Maximum Sum Circular Subarray Сложность: medium Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n. Пример:

Input: nums = [1,-2,3,-2]
Output: 3

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

def maxSubarraySumCircular(nums):
    def kadane(arr):
        current_sum = max_sum = arr[0]
        for num in arr[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)
        return max_sum

    max_kadane = kadane(nums)
    total_sum = sum(nums)
    min_kadane = kadane([-num for num in nums])

    return max(max_kadane, total_sum + min_kadane if total_sum + min_kadane != 0 else max_kadane)

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

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

Задача: 462. Minimum Moves to Equal Array Elements II Сложность: medium Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными. В одном ходе вы можете увеличить или уменьшить элемент массива на 1. Тестовые случаи составлены так, что ответ поместится в 32-битное целое число. Пример:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

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

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        ans = float('inf')
        minval = min(nums)
        maxval = max(nums)
        for i in range(minval, maxval + 1):
            sum_moves = 0
            for num in nums:
                sum_moves += abs(num - i)
            ans = min(ans, sum_moves)
        return int(ans)

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

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Офигеть, вот это поддержка! 🔥 Скажу честно: когда я планировал запуск краудфандинговой кампании, в голове были разные варианты развития событий. Думал — ну, наверное, получится собрать 300 тысяч. В самом идеальном сценарии — может быть, миллион. Но больше всего я боялся, что запущу кампанию, и не получится собрать даже 300 т. Это был бы провал. Так много усилий, времени и денег вложено в проект… и если бы всё закончилось ничем — это бы сильно демотивировало. Но, ребята, мы превысили изначальную цель в 10 раз — 3 031 040 рублей! 🤯 Вся эта кампания — это одна большая проверка бизнес-модели на прочность. И я супер рад, что запустил всё публично. Люди видят, что EasyOffer реально нужен. Теперь нет сомнений — проект актуален, он будет прибыльным и будет развиваться. Мне приходит огромное количество сообщений в личку: кто-то когда-то давно пользовался сайтом, он помог с трудоустройством, и сейчас они уже не ищут работу — но всё равно поддержали. Это прям очень круто и трогательно. Никак не могу отделаться от мысли, что easyoffer — это ведь мой первый сайт. Учебный, пет-проект, просто для портфолио. И вот что из него вышло. Просто офигеть. Я не зря ушёл с работы, чтобы заниматься только им. Я поверил в этот проект — и сейчас вижу, что вы тоже в него верите. Для меня это очень многое значит. Огромное спасибо за вашу поддержку! ❤️

Задача: 383. Ransom Note Сложность: easy Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае. Каждая буква из magazine может быть использована в ransomNote только один раз. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

def canConstruct(ransomNote: str, magazine: str) -> bool:
    for char in ransomNote:
        index = magazine.find(char)
        if index == -1:
            return false
        magazine = magazine[:index] + magazine[index + 1:]
    return True

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

Бесплатный эфир: сделай рывок в Frontend за 3 месяца! Не понимаете как правильно учиться, много знаний, но нет четкой структуры в голове? Не можете запомнить разницу между merge и rebase? Вроде бы все знаете в теории, но не можете написать простую программу/приложение и не знаете куда применить полученные знания? Приходите на эфир и узнайте: Как структурировать знания и избавиться от хаотичного потребления информации, составим четкий план вашего развития. Затронем тему выгорания на длинной дистанции и как преодолеть страх пробелов в знаниях и почему вы забрасываете учёбу на полпути. И на последок узнаете как получить заветный оффер и при этом иметь практический опыт коммерческой разработки с сильным проектом, который не обойдет ни один HR. Записаться #реклама 16+ salebot.site О рекламодателе

Задача: 1047. Remove All Adjacent Duplicates In String Сложность: easy Вам дана строка s, состоящая из строчных английских букв. Удаление дубликатов заключается в выборе двух соседних и одинаковых букв и их удалении. Мы многократно производим удаление дубликатов в s, пока не перестанем это делать. Верните конечную строку после того, как все такие удаления дубликатов будут произведены. Можно доказать, что ответ уникален. Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

def removeDuplicates(s: str) -> str:
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return ''.join(stack)

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

Конференция Корпоративные Сети 2025 - Беплатное участие! Предварительная регистрация на Корпоративные Сети 2025 (КС-2025) - конференцию по сетевым технологиям Участие бесплатно! ✨ Дата - 23 апреля ✨ Место - Москва, Экспоцентр, Краснопресненская наб., 14 Своим опытом эксплуатации оборудования поделятся специалисты по сетевым технологиям различных компаний. Конференция пройдет в рамках выставки Связь-2025, в которой можно будет посетить выставку и конференцию одновременно. Зарегистрироваться #реклама 16+ cnets.eltexcm.ru О рекламодателе

Задача: 111. Minimum Depth of Binary Tree Сложность: easy Дано бинарное дерево, найдите его минимальную глубину. Минимальная глубина - это количество узлов вдоль самого короткого пути от корневого узла до ближайшего листового узла. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 2

👨‍💻 Алгоритм: 1️⃣Мы будем использовать метод обхода в глубину (dfs) с корнем в качестве аргумента. Базовое условие рекурсии: это для узла NULL, в этом случае мы должны вернуть 0. 2️⃣Если левый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для правого ребенка корневого узла, что равно 1 + dfs(root.right). 3️⃣Если правый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для левого ребенка корневого узла, что равно 1 + dfs(root.left). Если оба ребенка не являются NULL, тогда вернуть 1 + min(dfs(root.left), dfs(root.right)). 😎 Решение:

class Solution:
    def minDepth(self, root):
        def dfs(root):
            if root is None:
                return 0
            if root.left is None:
                return 1 + dfs(root.right)
            elif root.right is None:
                return 1 + dfs(root.left)
            return 1 + min(dfs(root.left), dfs(root.right))

        return dfs(root)

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

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

Задача: 61. Rotate List Сложность: medium Дан указатель на начало связного списка, поверните список вправо на k позиций. Пример:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

👨‍💻 Алгоритм: 1️⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n. 2️⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n). 3️⃣Разорвите кольцо (new_tail.next = None) и верните new_head. 😎 Решение:

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return None
        if not head.next:
            return head

        old_tail = head
        n = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head

        new_tail = head
        for i in range(n - k % n - 1):
            new_tail = new_tail.next
        new_head = new_tail.next

        new_tail.next = None

        return new_head

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

Architecture as a Code + визуальное проектирование? Узнайте, как совместить эти два подхода, на вебинаре «Проектируем архитектуру по-новому с Platform V Works::Architect». Участники познакомятся с инструментом для управления архитектурой от СберТеха и узнают, как он помогает учесть потребности бизнеса и возможности проектирования. Поговорим о том, как реализовать версионность архитектур, адаптивность метамодели и параллельную работу. А в качестве бонуса – заглянем за горизонт архитектурных потребностей. Мероприятие пройдет 22 апреля Зарегистрироваться #реклама 16+ platformv.sbertech.ru О рекламодателе

Задача: 143. Reorder List Сложность: medium Вам дана голова односвязного списка. Список можно представить в следующем виде: L0 → L1 → … → Ln - 1 → Ln Переупорядочите список так, чтобы он принял следующую форму: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы. Пример:

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

👨‍💻 Алгоритм: 1️⃣Нахождение середины списка и разделение его на две части: Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине. Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка. 2️⃣Реверс второй половины списка: Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка. Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка. 3️⃣Слияние двух частей списка в заданном порядке: Начните с головы первой части списка (first) и головы реверсированной второй части (second). Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки. Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся. 😎 Решение:

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        first, second = head, prev
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next

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

Онлайн-магистратура Кибербезопасность от Яндекса и МИФИ День открытых дверей 23 апреля в 19:00 мск | Онлайн Эксперты Яндекса и НИЯУ МИФИ расскажут об очной онлайн-магистратуре для карьеры в IT. Всё о поступлении и обучении, выступления экспертов, ответы на вопросы. Выбирайте всё: работу и учёбу, навыки и диплом магистра. Узнать больше #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 135. Candy Сложность: hard В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings. Вы раздаете конфеты этим детям с соблюдением следующих требований: Каждый ребенок должен получить как минимум одну конфету. Дети с более высоким рейтингом должны получать больше конфет, чем их соседи. Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей. Пример:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

👨‍💻 Алгоритм: 1️⃣Инициализация и первичное заполнение массивов: Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете. 2️⃣Обход и обновление значений в массивах: Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа. Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа. 3️⃣Расчет минимального количества конфет: Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет. Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил. 😎 Решение:

class Solution:
    def candy(self, ratings: List[int]) -> int:
        sum = 0
        n = len(ratings)
        left2right = [1] * n
        right2left = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left2right[i] = left2right[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right2left[i] = right2left[i + 1] + 1
        for i in range(n):
            sum += max(left2right[i], right2left[i])
        return sum

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

📅 Осталось 7 дней до конца краудфандинга Мы на финишной прямой! Если ты планировал присоединиться, но ещё не успел, сейчас идеальный момент. Вознаграждения за поддержку: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование 👉 Поддержать easyoffer 2.0 Не откладывай на последний момент 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ