Python | LeetCode

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

Задача: 346. Moving Average from Data Stream Сложность: easy Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне. Реализуйте класс MovingAverage: MovingAverage(int size) Инициализирует объект с размером окна size. double next(int val) Возвращает скользящее среднее последних size значений потока. Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        self.sum = 0
    
    def next(self, val: int) -> float:
        self.queue.append(val)
        self.sum += val
        if len(self.queue) > self.size:
            self.sum -= self.queue.popleft()
        return self.sum / len(self.queue)

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

Татарская 35. Дом с видом на Кремль Третьяковская галерея и тихие переулки старой Москвы, купеческие особняки и древние храмы, набережные канала и уютные кафе Пятницкой улицы. Всё это - домашний район для жителей ТАТАРСКОЙ 35. ТАТАРСКАЯ 35 - дом, у подножья которого все Замоскворечье, а из окон открываются виды на знаковые достопримечательности Москвы. Здесь есть собственный велнес-центр, 100 м2 клубной инфраструктуры для жителей и двор-сад 1,8 га. В доме представлены элитные квартиры, в том числе с авторской отделкой отделкой: итальянские кухни, европейская техника и сантехника, система "умный дом". Квартиры на ТАТАРСКОЙ 35 сейчас доступны с 0% рассрочкой от застройщика на 2,5 года. Узнать больше Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО "СЗ "ПРАКТИКА" #реклама btatarskaya35.ru О рекламодателе

Задача: 371. Sum of Two Integers Сложность: medium Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -. Пример:

Input: a = 1, b = 2
Output: 3

👨‍💻 Алгоритм: 1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата. 2⃣Если нужно вычислить сумму: Пока перенос не равен нулю (y != 0): Текущий ответ без переноса равен XOR x и y: answer = x ^ y. Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = carry. Верните x * sign. 3⃣Если нужно вычислить разность: Пока заимствование не равно нулю (y != 0): Текущий ответ без заимствования равен XOR x и y: answer = x ^ y. Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = borrow. Верните x * sign. 😎 Решение:

class Solution:
    def getSum(self, a: int, b: int) -> int:
        x, y = abs(a), abs(b)
        if x < y:
            return self.getSum(b, a)  
        sign = 1 if a > 0 else -1
        
        if a * b >= 0:
            while y:
                x, y = x ^ y, (x & y) << 1
        else:
            while y:
                x, y = x ^ y, ((~x) & y) << 1
        
        return x * sign

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

Задача: 532. K-diff Pairs in an Array Сложность: medium Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве. Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия: 0 <= i, j < nums.length i != j |nums[i] - nums[j]| == k Обратите внимание, что |val| обозначает абсолютное значение val. Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

👨‍💻 Алгоритм: 1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums. 2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям: Если k > 0, проверьте, существует ли ключ, равный x + k. Если k == 0, проверьте, есть ли более одного вхождения x. 3⃣ Увеличьте счётчик результатов, если условие выполняется. 😎 Решение:

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        counter = collections.Counter(nums)
        result = 0
        
        for x in counter:
            if k > 0 and (x + k) in counter:
                result += 1
            elif k == 0 and counter[x] > 1:
                result += 1
        
        return result

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама 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)

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