Python | LeetCode

Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed Сложность: hard RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента. Реализуйте класс RandomizedCollection: RandomizedCollection(): Инициализирует пустой объект RandomizedCollection. bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае. bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них. int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество. Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени. Пример:

    
        Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]{}
    

👨‍💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества. 2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае. Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента. 😎 Решение:

    
        import random
from collections import defaultdict

class RandomizedCollection:
    def __init__(self):
        self.dict = defaultdict(set)
        self.list = []

    def insert(self, val: int) -> bool:
        self.dict[val].add(len(self.list))
        self.list.append(val)
        return len(self.dict[val]) == 1

    def remove(self, val: int) -> bool:
        if not self.dict[val]:
            return False
        index = self.dict[val].pop()
        last_element = self.list[-1]
        self.list[index] = last_element
        self.dict[last_element].add(index)
        self.dict[last_element].discard(len(self.list) - 1)
        self.list.pop()
        if not self.dict[val]:
            del self.dict[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.list){}
    

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

SOC Forum 2025 онлайн — все профи ИБ в одном месте 📅 18–20 ноября пройдет ключевое событие Недели кибербезопасности — SOC Forum. 👍 Ведущие эксперты соберутся, чтобы обсудить самые острые темы и представить лучшие практические кейсы: каждый доклад прошел строгий отбор, так что вас ждет концентрат пользы. ⚡ Станьте частью форума даже онлайн! Помимо прямой трансляции лекций, для удаленных участников будут работать «Кибербез ТВ» и радиостанция «ЭХО лОСЕЙ» — с новостными дайджестами, эксклюзивными интервью, мастер-классами и специальными сюжетами, доступными только в онлайн-формате. ✅ Зарегистрируйтесь, и мы пришлем напоминание перед стартом. Зарегистрироваться #реклама 16+ registration.forumsoc.ru О рекламодателе

Задача: 268. Missing Number Сложность: easy Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве. Пример:

    
        Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.{}
    

👨‍💻 Алгоритм: 1️⃣Сначала отсортируйте массив nums. 2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце. 3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число. 😎 Решение:

    
        class Solution:
    def missingNumber(self, nums):
        nums.sort()
        if nums[-1] != len(nums):
            return len(nums)
        elif nums[0] != 0:
            return 0
        for i in range(1, len(nums)):
            expected_num = nums[i - 1] + 1
            if nums[i] != expected_num:
                return expected_num
        return -1{}
    

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

Станьте разработчиком нейро-сотрудников на Python и зарабатывайте от 150.000р в месяц 🔥🔥🔥 Мы научим вас создавать топовых нейро-сотрудников на базе GPT-4 Omni, и вы сможете: 1️⃣ Устроиться разработчиком в крупную компанию и зарабатывать от 150 тысяч ₽ в месяц 2️⃣ Разрабатывать такие проекты на заказ и зарабатывать от 500 тысяч ₽ за проект 3️⃣ Создать нейро-сотрудника в вашей компании и вырасти на +30-100% в зарплате Что будет на интенсиве? 🧬 Теория: как создаются нейро-сотрудники с GPT-4o на Python 🧬 Практика: мы создадим нейро-консультанта, нейро-HR, нейро-маркетолога и др. Ведущий интенсива - Senior AI разработчик нейросетей и основатель Университета искусственного интеллекта 🔥 Регистрируйтесь на бесплатный интенсив! Встречаемся в ближайший четверг!

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 736. Parse Lisp Expression Сложность: hard Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

    
        Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14{}
    

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

    
        class Solution:
    def evaluate(self, expression: str) -> int:
        def evaluate(expression, env):
            if expression[0] != '(':
                if expression[0].isalpha():
                    return env[expression]
                return int(expression)
            
            tokens = tokenize(expression)
            if tokens[0] == 'let':
                for i in range(1, len(tokens) - 2, 2):
                    env[tokens[i]] = evaluate(tokens[i + 1], env)
                return evaluate(tokens[-1], env)
            elif tokens[0] == 'add':
                return evaluate(tokens[1], env) + evaluate(tokens[2], env)
            elif tokens[0] == 'mult':
                return evaluate(tokens[1], env) * evaluate(tokens[2], env)
        
        def tokenize(expression):
            tokens, token, parens = [], '', 0
            for char in expression:
                if char == '(':
                    parens += 1
                    if parens == 1:
                        continue
                elif char == ')':
                    parens -= 1
                    if parens == 0:
                        tokens.append(tokenize(token))
                        token = ''
                        continue
                elif char == ' ' and parens == 1:
                    if token:
                        tokens.append(token)
                        token = ''
                    continue
                token += char
            if token:
                tokens.append(token)
            return tokens
        
        return evaluate(expression, {}){}
    

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

REKONFA Live 6 ноября приглашаем всех, кто имеет отношение к маркетингу и рекламным технологиям, обсудить рынок, тренды, вызовы и их решения. С докладами на актуальные темы выступят лидеры индустрии и медийные спикеры. Принять участие можно офлайн и онлайн. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 18+ ya.rekonfa.ru О рекламодателе

Задача: 1357. Apply Discount Every n Orders Сложность: medium В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i]. Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара). Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100). Реализуйте класс Cashier: Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен. double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты. Пример:

    
        Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами. 2⃣Обработка каждого счета: Создайте метод getBill, который принимает массивы product и amount. Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты. Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу. 3⃣Верните итоговую сумму счета. 😎 Решение:

    
        class Cashier:

    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
        self.n = n
        self.discount = discount
        self.productsPrices = dict(zip(products, prices))
        self.customerCount = 0

    def getBill(self, product: List[int], amount: List[int]) -> float:
        self.customerCount += 1
        bill = sum(self.productsPrices[prod] * amt for prod, amt in zip(product, amount))
        
        if self.customerCount % self.n == 0:
            bill *= (100 - self.discount) / 100.0
        
        return bill{}
    

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