Python | LeetCode

Задача: 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

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

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

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

Задача: 1268. Search Suggestions System Сложность: medium Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord. Пример:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

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

def suggestedProducts(products, searchWord):
    products.sort()
    result = []
    prefix = ""
    for char in searchWord:
        prefix += char
        suggestions = [product for product in products if product.startswith(prefix)]
        result.append(suggestions[:3])
    return result

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

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