Python | LeetCode

Задача: 983. Minimum Cost For Tickets Сложность: medium Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365. Билеты на поезд продаются тремя различными способами: однодневный билет продаётся за costs[0] долларов, семидневный билет продаётся за costs[1] долларов, и тридцатидневный билет продаётся за costs[2] долларов. Билеты позволяют путешествовать указанное количество дней подряд. Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8. Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days. Пример:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

👨‍💻 Алгоритм: 1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days. 2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его. 3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ. 😎 Решение:

class Solution:
    def __init__(self):
        self.isTravelNeeded = set()
    
    def solve(self, dp, days, costs, currDay):
        if currDay > days[-1]:
            return 0
        
        if currDay not in self.isTravelNeeded:
            return self.solve(dp, days, costs, currDay + 1)
        
        if dp[currDay] != -1:
            return dp[currDay]
        
        oneDay = costs[0] + self.solve(dp, days, costs, currDay + 1)
        sevenDay = costs[1] + self.solve(dp, days, costs, currDay + 7)
        thirtyDay = costs[2] + self.solve(dp, days, costs, currDay + 30)
        
        dp[currDay] = min(oneDay, min(sevenDay, thirtyDay))
        return dp[currDay]
    
    def mincostTickets(self, days, costs):
        lastDay = days[-1]
        dp = [-1] * (lastDay + 1)
        
        for day in days:
            self.isTravelNeeded.add(day)
        
        return self.solve(dp, days, costs, 1)

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

Торгуйте валютой с Альфа Форекс! Зарабатывайте на Forex бирже с Альфа Форекс💰 ✅Лицензия ЦБ Более 20 лет на рынке Forex👍 Вас ждет самый широкий выбор инструментов в РФ - 40+ валютных пар, включая рублевые! Ввод/вывод 0%, пополнение через СБП, торги от 0.01 лота! Альфа Форекс - лицензированный Брокер, которому доверяют!❤️ Узнать больше Финансовые услуги оказывает: ООО «Альфа-Форекс», АО "АЛЬФА-БАНК". #реклама alfaforex.ru О рекламодателе

Задача: 26. Remove Duplicates from Sorted Array Сложность: easy Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов в числах. Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее: - Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums. - Вернуть k. Пример:

Input: nums = [1,1,2]  
Output: 2, nums = [1,2,_]  

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

from typing import List  

class Solution:  
    def removeDuplicates(self, nums: List[int]) -> int:  
        i = 0    
        while i < len(nums) - 1:     
            if nums[i] == nums[i + 1]:  
                nums.pop(i + 1)     
            else:  
                i += 1    

        return len(nums)

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

Сколько приложений нужно вашей команде для работы? Всего один сервис — Битрикс24! А внутри десятки инструментов для совместной работы и бизнеса. Читайте подробнее в карточках. Регистрируйтесь сейчас, чтобы забрать их все себе бесплатно😊 Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint Сложность: hard Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия: Слово содержит первую букву головоломки. Каждая буква в слове присутствует в головоломке. Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке). Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i]. Пример:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

👨‍💻 Алгоритм: 1⃣Постройте карту. Для каждого слова в списке words: Преобразуйте его в битовую маску его символов. Если эта битовая маска не была ранее встречена, сохраните ее в качестве ключа в карте со значением 1. Если она была ранее встречена, увеличьте счетчик для этой битовой маски на 1. 2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles: Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки. 3⃣Для каждой подмаски увеличивайте счетчик на количество слов, соответствующих подмаске. Мы можем найти количество слов, соответствующих подмаске, используя карту, построенную на предыдущем шаге. 😎 Решение:

class Solution:
    def bitmask(self, word: str) -> int:
        mask = 0
        for letter in word:
            mask |= 1 << (ord(letter) - ord('a'))
        return mask

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        word_count = {}
        for word in words:
            mask = self.bitmask(word)
            word_count[mask] = word_count.get(mask, 0) + 1

        result = []
        for puzzle in puzzles:
            first = 1 << (ord(puzzle[0]) - ord('a'))
            count = word_count.get(first, 0)
            mask = self.bitmask(puzzle[1:])
            submask = mask
            while submask > 0:
                count += word_count.get(submask | first, 0)
                submask = (submask - 1) & mask
            result.append(count)
        return result

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

Обучение трейдингу для новичков и профессиналов Изучайте слайды с основными темами, смотрите видео и практикуйтесь. Торгуйте на рынке как профи! Зарегистрироваться #реклама 16+ fxproru.pro О рекламодателе

Задача: 827. Making A Large Island Сложность: hard Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1. Верните размер самого большого острова в grid после выполнения этой операции. Остров — это группа 1, соединенных в 4 направлениях. Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def dfs(r, c, index):
            ans = 1
            grid[r][c] = index
            for nr, nc in neighbors(r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = index
                    ans += dfs(nr, nc, index)
            return ans

        def neighbors(r, c):
            for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < N:
                    yield nr, nc

        N = len(grid)
        index = 2
        area = [0] * (N * N + 2)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    area[index] = dfs(r, c, index)
                    index += 1

        ans = max(area)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
                    ans = max(a

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

Задача: 373. Find K Pairs with Smallest Sums Сложность: medium Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k. Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива. Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами. Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

👨‍💻 Алгоритм: 1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар. 2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited. 3⃣Повторяйте до получения k пар и пока minHeap не пуст: Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2]. Добавьте пару (nums1[i], nums2[j]) в ans. Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap. Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap. Верните ans. 😎 Решение:

import heapq

class Solution:
    def kSmallestPairs(self, nums1, nums2, k):
        m, n = len(nums1), len(nums2)
        ans = []
        visited = set()
        minHeap = [(nums1[0] + nums2[0], 0, 0)]
        visited.add((0, 0))

        while k > 0 and minHeap:
            sum_val, i, j = heapq.heappop(minHeap)
            ans.append([nums1[i], nums2[j]])
            if i + 1 < m and (i + 1, j) not in visited:
                heapq.heappush(minHeap, (nums1[i + 1] + nums2[j], i + 1, j))
                visited.add((i + 1, j))
            if j + 1 < n and (i, j + 1) not in visited:
                heapq.heappush(minHeap, (nums1[i] + nums2[j + 1], i, j + 1))
                visited.add((i, j + 1))
            k -= 1

        return ans

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

Я смотрю на эту цифру и до сих пор не верю. Когда я запускал этот проект, мне реально было страшно. Страшно, что ничего не получится. Что я и мой проект никому не нужен. Страшно, что все увидят, как я публично обосрался. Я ставил планку в 300т рублей. В самом позитивном сценарии 1млн. Но про 5 миллионов… даже мысли не было. Уже в первые часы стало понятно, что кампания идет не по плану. Сайт краудфандинга не выдержал нашей нагрузки и лег 😁 Особенно в последние три дня — просто какой-то разрыв! Я ощущал, как будто ловлю попутный ветер. В последний час не хватало 50к до 5 млн, и я уже думал сам их докинуть, чтобы красиво закрыть 😁 Но финальная сумма это не так важно. Самое главное это как мы её собрали. Это не инвестиции, не чьи-то деньги под условия и контроль, не кредит. Это вы поверили и поддержали меня напрямую. Вы дали мне возможность оставить за собой полный контроль над easyoffer. Я чувствую огромную ответственность и нервничаю из-за высоких ожиданий. А вдруг что-то пойдёт не так? А вдруг на релизе кому-то что-то не понравится? Именно поэтому я рад, что могу честно выйти на новый этап и без давления от левых инвесторов. В такие моменты вспоминаю, с чего всё начиналось. Как 2 года назад я писал свои первые посты на 500 человек о том, как учу программирование. Как записывал первое видео на YouTube про поиск работы. Как пилил первую версию easyoffer, вообще без понимания, что из этого выйдет. И сейчас я думаю — может, эта история вдохновит кого-то из вас. Может, кто-то запустит свой айтишный проект, найдёт поддержку и соберёт бабки на развитие. Было бы круто Спасибо за невероятную и колосальную поддержку ❤️ О такой аудитории как вы я не мог мечтать

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

🚨 60 минут до финала Через час мы закроем краудфандинг easyoffer 2.0 Это последний шанс вписаться в самые выгодные условия. 👉 https://planeta.ru/campaigns/easyoffer

Финальный отсчёт: 3 часа до конца краудфандинга easyoffer 2.0! Это не просто скидка. Это шанс поддержать проект, который поможет и вам и тысячам айтишников готовиться к собеседованиям быстрее, эффективнее и увереннее. За последние недели: 💥 Нас поддержали уже больше 1450 человек; 🔥 Вместе собрали больше 4,5 млн. рублей на запуск проекта; Но сейчас важнее другое. ⏳ Через 3 часа всё закончится. – Больше не будет подписки за 3 200 руб. на целый год! – Не будет шанса первыми воспользоваться EasyOffer 2.0 на бета-тестировании Если вы: + Планируете менять работу в этом или следующем году; + Хотите иметь под рукой 40,000+ вопросов собеседований с разборами, видео-ответами и тренажёрами; + Хотите зафиксировать лучшую цену на целый год… (потом будет в 12 раз дороже) 👉 Тогда просто переходите и поддержите нас сейчас: https://planeta.ru/campaigns/easyoffer 📢 Три часа — и всё. Не откладывайте на потом. Спасибо всем, кто уже с нами! 💙

Задача: 1262. Greatest Sum Divisible by Three Сложность: medium Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три. Пример:

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

👨‍💻 Алгоритм: 1⃣Найдите сумму всех элементов массива. 2⃣Если сумма делится на 3, то она и есть ответ. 3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2). Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2). 😎 Решение:

def maxSumDivThree(nums):
    total_sum = sum(nums)
    if total_sum % 3 == 0:
        return total_sum
    
    mod1 = [x for x in nums if x % 3 == 1]
    mod2 = [x for x in nums if x % 3 == 2]
    
    mod1.sort()
    mod2.sort()
    
    if total_sum % 3 == 1:
        if len(mod1) >= 1 and len(mod2) >= 2:
            return max(total_sum - mod1[0], total_sum - sum(mod2[:2]))
        if len(mod1) >= 1:
            return total_sum - mod1[0]
        if len(mod2) >= 2:
            return total_sum - sum(mod2[:2])
    
    if total_sum % 3 == 2:
        if len(mod2) >= 1 and len(mod1) >= 2:
            return max(total_sum - mod2[0], total_sum - sum(mod1[:2]))
        if len(mod2) >= 1:
            return total_sum - mod2[0]
        if len(mod1) >= 2:
            return total_sum - sum(mod1[:2])
    
    return 0

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

⏳ Такого больше не будет! Всего пара часов и больше не будет возможности получить: 🚀 PRO подписку к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование 👉 Поддержать: https://planeta.ru/campaigns/easyoffer

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 783. Minimum Distance Between BST Nodes Сложность: easy Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы. 2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes. 3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance. Верните minDistance. 😎 Решение:

class Solution:
    def __init__(self):
        self.inorderNodes = []

    def inorderTraversal(self, root):
        if not root:
            return
        
        self.inorderTraversal(root.left)
        self.inorderNodes.append(root.val)
        self.inorderTraversal(root.right)
    
    def minDiffInBST(self, root):
        self.inorderTraversal(root)
        
        minDistance = float('inf')
        for i in range(1, len(self.inorderNodes)):
            minDistance = min(minDistance, self.inorderNodes[i] - self.inorderNodes[i - 1])
        
        return minDistance

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

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

🚨 Последний шанс! Сегодня — последний день краудфандинга. Через несколько часов всё закроется, и больше невозможно будет поучаствовать. Если ты хотел, но откладывал — СЕЙЧАС самое время. Займёт 2 минуты, но изменит твой подход к собеседованиям надолго. Поддержи easyoffer 2.0 и получи: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование PRO подписка к easyoffer 2.0: ✅ Доступ к списку вопросов, которые задаются на собеседованиях + вероятность встречи этих вопросов + их фильтрация по грейдам, типам интервью, компаниям ✅ Доступ к лучшим ответам на вопросы ✅ Список самых частых задач, которые задаются на собеседовании + их фильтрация по грейдам и компаниям ✅ Доступ к лучшим ответам на задачи ✅ Список тестовых заданий компаний + лучшее решение ✅ Доступ к тренажеру "Проработка вопросов", который позволит очень быстро подготовиться к самым частым вопросам ✅ Доступ к тренажеру "Реальное собеседование", который позволит тренироваться проходить собеседование в конкретную компанию До конца кампании — остались часы. Поддержать: https://planeta.ru/campaigns/easyoffer 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Битрикс24 дропнул новую фичу — онлайн-доски Теперь к вашему рабочему мессенджеру, видеозвонкам и таскам добавился еще один маст-хэв инструмент. Все это бесплатно и в одном комплекте. Офисные стикеры, берегитесь.😊 Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

Задача: 326. Power of Three Сложность: easy Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false. Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x. Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 3 == 0:
            n //= 3
        return n == 1

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