Python | LeetCode

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

Задача: 411. Minimum Unique Word Abbreviation Сложность: hard Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными. Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них. Пример:

Input: target = "apple", dictionary = ["blade"]
Output: "a4"

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

def generate_abbreviations(word):
    def helper(word, current, pos, count, result):
        if pos == len(word):
            result.add(current + (str(count) if count > 0 else ""))
            return
        helper(word, current, pos + 1, count + 1, result)
        helper(word, current + (str(count) if count > 0 else "") + word[pos], pos + 1, 0, result)
    
    result = set()
    helper(word, "", 0, 0, result)
    return result

def min_abbreviation(target, dictionary):
    target_abbrs = generate_abbreviations(target)
    dict_abbrs = set()
    for word in dictionary:
        dict_abbrs.update(generate_abbreviations(word))
    valid_abbrs = target_abbrs - dict_abbrs
    return min(valid_abbrs, key=len)

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

👩‍💻 Docker — лучший канал для ускоренного обучения DevOps. С помощью инфографики, наглядных визуализаций и коротких обучающих видео вам будут доступны все ключевые концепции работы с Docker и методики DevOps. Прокачать скиллы: t.me/DevopsDocker

Профессия «Аналитик данных» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Подать заявку #реклама 16+ eduson.academy О рекламодателе

Задача: 1277. Count Square Submatrices with All Ones Сложность: medium Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы. Пример:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15

👨‍💻 Алгоритм: 1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов. 2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. 3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц. 😎 Решение:

def countSquares(matrix):
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    count = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                count += dp[i][j]
                
    return count

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

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

Задача: 823. Binary Trees With Factors Сложность: medium Дан массив уникальных целых чисел arr, где каждое целое число arr[i] строго больше 1. Мы создаем бинарное дерево, используя эти числа, и каждое число может быть использовано любое количество раз. Значение каждого не листового узла должно быть равно произведению значений его дочерних узлов. Верните количество бинарных деревьев, которые мы можем создать. Ответ может быть слишком большим, поэтому верните ответ по модулю 10^9 + 7. Пример:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

👨‍💻 Алгоритм: 1⃣Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование. 2⃣Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k. 3⃣После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением. 😎 Решение:

class Solution:
    def numFactoredBinaryTrees(self, A):
        MOD = 10 ** 9 + 7
        A.sort()
        dp = [1] * len(A)
        index = {x: i for i, x in enumerate(A)}
        
        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0:
                    right = x // A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

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

Профессия «Аналитик данных» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Узнать больше #реклама 16+ eduson.academy О рекламодателе

Задача: 214. Shortest Palindrome Сложность: hard Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки. Верните самый короткий палиндром, который можно получить, выполняя это преобразование. Пример:

Input: s = "aacecaaa"
Output: "aaacecaaa"

👨‍💻 Алгоритм: 1️⃣Создайте обратную строку от исходной строки s, назовем ее rev. Она будет использована для сравнения, чтобы найти наибольший палиндромный сегмент с начала строки. 2️⃣ Итеративно перемещайтесь по переменной i от 0 до size(s) - 1: Если s[0:n−i] == rev[i:] (т.е. подстрока s от 0 до n−i равна подстроке rev от i до конца строки). Это по сути означает, что подстрока от 0 до n−i является палиндромом, так как rev является обратной строкой s. 3️⃣ Так как мы находим сначала большие палиндромы, можем вернуть обратную строку от наибольшего палиндрома + s, как только найдем его. 😎 Решение:

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        rev = s[::-1]
        for i in range(n):
            if s[: n - i] == rev[i:]:
                return rev[:i] + s
        return ""

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

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

Задача: 1140. Stone Game II Сложность: medium Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней. Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1. В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X). Игра продолжается до тех пор, пока все камни не будут взяты. Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса. Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

👨‍💻 Алгоритм: 1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи), и m (максимальное количество куч, которые можно взять за ход). Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его. 2⃣Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния. Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат. Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат. 3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res. 😎 Решение:

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        def f(p, i, m):
            if i == len(piles):
                return 0
            if dp[p][i][m] != -1:
                return dp[p][i][m]
            res = 1000000 if p == 1 else -1
            s = 0
            for x in range(1, min(2 * m, len(piles) - i) + 1):
                s += piles[i + x - 1]
                if p == 0:
                    res = max(res, s + f(1, i + x, max(m, x)))
                else:
                    res = min(res, f(0, i + x, max(m, x)))
            dp[p][i][m] = res
            return res

        dp = [[[-1] * (len(piles) + 1) for _ in range(len(piles) + 1)] for _ in range(2)]
        return f(0, 0, 1)

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

Получи грант на обучение в Центральном университете Получи несгораемый грант до 2 800 000 ₽ на учебу в бакалавриате Центрального университета. Грант покрывает до 100% стоимости обучения. Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе. Участвуй в отборе! Для учеников 10-х и 11-х классов, колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 259. 3Sum Smaller Сложность: medium Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target. Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

👨‍💻 Алгоритм: 1️⃣Отсортируйте массив nums. 2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения. 3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар. 😎 Решение:

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        sum_count = 0
        for i in range(len(nums) - 2):
            sum_count += self.twoSumSmaller(nums, i + 1, target - nums[i])
        return sum_count

    def twoSumSmaller(self, nums: List[int], startIndex: int, target: int) -> int:
        sum_count = 0
        for i in range(startIndex, len(nums) - 1):
            j = self.binarySearch(nums, i, target - nums[i])
            sum_count += j - i
        return sum_count

    def binarySearch(self, nums: List[int], startIndex: int, target: int) -> int:
        left, right = startIndex, len(nums) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid - 1
        return left

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

80 лет назад: хроники Победы Собрали самое главное: ✨ Военные сводки и хроники с фронта ✨ Герои и их подвиги ✨ Культура 1941—1945 годов ✨ Настоящие новости тех лет Перейти на сайт #реклама 16+ dzen.ru О рекламодателе

Задача: 965. Univalued Binary Tree Сложность: easy Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение. Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае. Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        vals = []
        
        def dfs(node):
            if node:
                vals.append(node.val)
                dfs(node.left)
                dfs(node.right)
        
        dfs(root)
        return all(v == vals[0] for v in vals)

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

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

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