Python | LeetCode

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

Задача: 995. Minimum Number of K Consecutive Bit Flips Сложность: hard Дан бинарный массив nums и целое число k. Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0. Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1. Подмассив - это непрерывная часть массива. Пример:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

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

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        flip = 0
        flips = 0
        flip_queue = [0] * n
        
        for i in range(n):
            if i >= k:
                flip ^= flip_queue[i - k]
            if nums[i] == flip:
                if i + k > n:
                    return -1
                flips += 1
                flip ^= 1
                flip_queue[i] = 1
        
        return flips

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

Бесплатное льготное обучение: 3 месяца Мы ищем людей, которые хотят работать в IT-сфере из дома 💰 Оплата от 150.000 рублей в месяц Образование, место жительства, трудовой стаж — не важны! Подходит, как для подработки / декретного отпуска, так и для полной занятости. Если заинтересовались, то для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку: Узнать больше #реклама technolium.ru О рекламодателе

Задача: 190. Reverse Bits Сложность: easy Переверните биты заданного 32-битного беззнакового целого числа. Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

👨‍💻 Алгоритм: 1️⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа. 2️⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции. 3️⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений. 😎 Решение:

import functools
class Solution:
    def reverseBits(self, n: int) -> int:
        ret, power = 0, 24
        while n:
            ret += self.reverseByte(n & 0xFF) << power
            n = n >> 8
            power -= 8
        return ret
    @functools.lru_cache(maxsize=256)
    def reverseByte(self, byte):
        return (byte * 0x0202020202 & 0x010884422010) % 1023

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

⚡️ Python теперь в Telegram! Ребята сделали крутейший канал, где на простых картинках и понятном языке обучают Python, делятся полезными фишками и инструментами Подписывайтесь: @PythonPortal

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

Задача: 171. Excel Sheet Column Number Сложность: easy Дана строка columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца. Пример:

Input: columnTitle = "A"
Output: 1

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

class Solution:
    def titleToNumber(self, s: str) -> int:
        result = 0

        alpha_map = {chr(i + 65): i + 1 for i in range(26)}

        n = len(s)
        for i in range(n):
            cur_char = s[n - 1 - i]
            result += alpha_map[cur_char] * (26**i)
        return result

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

Стать бэкендером в Яндексе за несколько дней 12–17 апреля устраиваем Week Offer Backend: за несколько дней можно пройти технические секции и попасть в Яндекс. Для этого нужно зарегистрироваться и решить несколько задач в Контесте. Ищем классных бэкенд-разработчиков с опытом работы от 3 лет на C++, Python, Java/Kotlin или Go, готовых работать в офисном или гибридном режиме в России. Вы сможете выбрать одну из команд: Яндекс Пэй, Яндекс ID, Яндекс Плюс, Яндекс Сплит, Яндекс Сейвы, Яндекс 360. Можно пообщаться с нанимающими менеджерами и выбрать самый интересный проект. Если всё пройдёт хорошо, сразу же получите офер. Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 969. Pancake Sorting Сложность: medium Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов. При одном перевороте блина мы выполняем следующие шаги: Выбираем целое число k, где 1 <= k <= arr.length. Переворачиваем подмассив arr[0...k-1] (индексация с 0). Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3. Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным. Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

👨‍💻 Алгоритм: 1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0 ] (в Python). 2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего. 3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте. 😎 Решение:

class Solution:
    def pancakeSort(self, A):
        ans = []

        for value_to_sort in range(len(A), 0, -1):
            index = self.find(A, value_to_sort)
            if index == value_to_sort - 1:
                continue
            if index != 0:
                ans.append(index + 1)
                self.flip(A, index + 1)
            ans.append(value_to_sort)
            self.flip(A, value_to_sort)

        return ans

    def flip(self, sublist, k):
        sublist[:k] = sublist[:k][::-1]

    def find(self, a, target):
        for i, num in enumerate(a):
            if num == target:
                return i
        return -1

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

Ошибки в защите данных: как СУБД Jatoba избегает их? Дата: 17 апреля (четверг) Время: 12:00 - 13:30 МСК Не пропустите вебинар «Кластерные решения для больших объемов данных: отечественный опыт» Эксперты УЦСБ и «Газинформсервис» расскажут, как избежать ошибок в настройке СУБД, повысить доступность данных и защитить их от утечек, даже при пиковых нагрузках. 1. Как Jatoba обеспечивает высокую доступность данных при максимальных нагрузках? 2. Почему стоит выбрать отечественную СУБД для хранения и защиты данных? 3. Реальные примеры успешных внедрений в крупных компаниях. 4. Демонстрация интерфейса и отказоустойчивости Jatoba DB в действии! Бонус: фирменный мерч от «Газинформсервис» за самый интересный вопрос! Зарегистрироваться #реклама 16+ sec.ussc.ru О рекламодателе

Задача: 974. Subarray Sums Divisible by K Сложность: medium Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1. 2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений. 3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k. 😎 Решение:

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefixMod = 0
        result = 0
        modGroups = [0] * k
        modGroups[0] = 1

        for num in nums:
            prefixMod = (prefixMod + num % k + k) % k
            result += modGroups[prefixMod]
            modGroups[prefixMod] += 1

        return result

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

На обучение в IT-компанию на удаленку требуются стажеры! ⚡ Для тестирования программ и приложений. (Можно без опыта, всему научим) С нас обучение, с вас — пару свободных часов в день. Наша цель — предоставить IT-компаниям качественных специалистов в сфере тестирования приложений и программ. 👌 Вы подходите, если любите работать и зарабатывать! Можно совмещать с основной работой или декретным отпуском. Сперва проведу бесплатный вводный урок, на котором расскажу: — об основах тестирования; — о поиске клиентов; — как пройти стажировку и устроиться в топовую IT-компанию. ✅ Что будет требоваться от вас: — проверять программы или приложения; — находить в них ошибки; — зарабатывать. 💰 За свою работу можно зарабатывать от 70 000 рублей. 👍 Для регистрации жмите кнопку "Зарегистрироваться" Зарегистрироваться #реклама 16+ site.purrweb-academy.ru О рекламодателе

Задача: 834. Sum of Distances in Tree Сложность: hard Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами. Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве. Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами. Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

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

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        import collections
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        ans = [0] * N
        count = [1] * N

        def dfs(node=0, parent=None):
            for neighbor in graph[node]:
                if neighbor != parent:
                    dfs(neighbor, node)
                    count[node] += count[neighbor]
                    ans[node] += ans[neighbor] + count[neighbor]

        def dfs2(node=0, parent=None):
            for neighbor in graph[node]:
                if neighbor != parent:
                    ans[neighbor] = ans[node] - count[neighbor] + N - count[neighbor]
                    dfs2(neighbor, node)

        dfs()
        dfs2()

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

Ты уже начал изучать IT, но чувствуешь, что сам не вывезешь? Нужно больше практики, системности и поддержки? 🔥Приходи на бесплатный интенсив "Первые шаги в Python: начни свой путь в IT" 🔥 8, 9 и 10 апреля | Онлайн За 3 дня ты: ✅ поймёшь, как устроена профессия backend-разработчика; ✅ изучишь основы Python и напишешь свою первую программу прямо в Google Colab; ✅ разберёшься, какие шаги реально приведут тебя в IT; ✅ получишь поддержку и ответы на свои вопросы от опытного наставника. Интенсив проведёт Сергей Смелков — backend-разработчик с 5-летним опытом, преподаватель и ментор, который помогает новичкам уверенно войти в профессию. Сергей объясняет сложные темы простым языком, помогает не запутаться в старте и уже на первых шагах почувствовать себя уверенно. Если хочешь перестать блуждать в потёмках и получить чёткое направление — начни с этих трёх дней. ❗️Это бесплатно, понятно и под силу каждому. 🎯Регистрируйся сейчас — старт 8 апреля👇 https://salebot.site/md/smelkov_stutyit

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

Задача: №21. Merge Two Sorted Lists Сложность: easy Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка. Пример:

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]  

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

class Solution:
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)
        cur = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        
        cur.next = l1 or l2
        return dummy.next

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

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

Задача: 1244. Design A Leaderboard Сложность: medium Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста. Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

👨‍💻 Алгоритм: 1⃣addScore(playerId, score): Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение. Если игрок не существует, добавляем его с заданным счетом. 2⃣top(K): Сортируем игроков по их счету в порядке убывания. Возвращаем сумму очков K лучших игроков. 3⃣reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:

from collections import defaultdict

class Leaderboard:

    def __init__(self):
        self.scores = defaultdict(int)

    def addScore(self, playerId, score):
        self.scores[playerId] += score

    def top(self, K):
        return sum(sorted(self.scores.values(), reverse=True)[:K])

    def reset(self, playerId):
        self.scores[playerId] = 0

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

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

Задача: №44. Wildcard Matching Сложность: hard При наличии входных строк s и шаблона p реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой "?" и "*", где: - "?" соответствует любому отдельному символу. - "*" соответствует любой последовательности символов (включая пустую последовательность). Соответствие должно охватывать всю входную строку (не частичное). Пример:

Input: s = "adceb", p = "*a*b"  
Output: true  

👨‍💻 Алгоритм: 1️⃣Используем динамическое программирование, создаем матрицу dp для хранения промежуточных результатов. 2️⃣Инициализируем dp[0][0] = True (пустая строка соответствует пустому шаблону). 3️⃣Заполняем dp, учитывая, что "?" заменяет любой символ, а "*" может заменять любую последовательность символов. 😎 Решение:

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == s[i - 1] or p[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
        
        return dp[m][n]

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