Python | LeetCode

Задача: 112. Path Sum Сложность: easy Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum. Лист — это узел без детей. Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

👨‍💻 Алгоритм: 1️⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val. 2️⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом. 3️⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами. 😎 Решение:

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False

        de = [
            (root, sum - root.val),
        ]
        while de:
            node, curr_sum = de.pop()
            if not node.left and not node.right and curr_sum == 0:
                return True
            if node.right:
                de.append((node.right, curr_sum - node.right.val))
            if node.left:
                de.append((node.left, curr_sum - node.left.val))
        return False

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

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

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

Задача: 303. Range Sum Query - Immutable Сложность: easy Дан целочисленный массив nums. Обработайте несколько запросов следующего типа: Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right. Реализуйте класс NumArray: - NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums. - int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]). Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums. 2⃣Предварительное вычисление сумм: Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат. 😎 Решение:

class NumArray:
    def __init__(self, nums: List[int]):
        self.sum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.sum[i + 1] = self.sum[i] + nums[i]

    def sumRange(self, i: int, j: int) -> int:
        return self.sum[j + 1] - self.sum[i]

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

Старт продаж премиальных апартаментов Skysoul в Крыму Премиальный комплекс в 30 метрах от собственного пляжа ✅ Комплекс — 4-х кратный победитель премии в сфере недвижимости URBAN AWORDS как самый привлекательный инвестиционный проект ЮФО 🏠 Комплекс можно: - Сдавать посуточно через отельера международного класса и получать пассивный ежемесячный доход (при этом отдыхая в отпуске в собственном номере) - Выгодно перепродать ⚡ О проекте: - Первая береговая линия – всего в 30 метрах расположен собственный пляж - На территории открытый и 2 круглогодичных бассейна - Более 14,5 га впечатляющей территории: 4-этажный SPA-комплекс, амфитеатр, панорамный ресторан, медцентр, игровое пространство для детей, магазины и бутик ⚡Роскошные панорамные виды на потухший вулкан, море и виноградники ✅Получите цены и презентацию первыми: Перейти на сайт Проектная декларация на сайте https://наш.дом.рф/. #реклама mrqz.me О рекламодателе

Задача: 754. Reach a Number Сложность: medium Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения. Пример:

Input: target = 2
Output: 3

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps). 2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps. 3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps. 😎 Решение:

def reachTarget(target):
    target = abs(target)
    position = 0
    steps = 0
    while position < target or (position - target) % 2 != 0:
        steps += 1
        position += steps
    return steps

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

ИИ-революция в вашей карьере: бесплатный вебинар 2025 год: нейросети — это must-have навык для карьерного роста. 👌 ✅Приглашаем на бесплатный живой вебинар, где вы: --- Поймете, какие нейросети существуют и как их применять в работе. --- Научитесь писать эффективные промпты и автоматизировать рутину. --- Узнаете, как делегировать ИИ задачи и экономить от 20 часов в неделю! --- Создадите своего первого ИИ-ассистента в прямом эфире. Получите руководство «Как создать цифровой аватар» сразу после регистрации! Подойдет новичкам. Онлайн-формат с ответами на вопросы. ⚡ Жмите «Зарегистрироваться», чтобы прокачать свой скилл-сет и освободить время для главного! Зарегистрироваться #реклама 16+ ed.bonnieandslide.com О рекламодателе

Задача: 234. Palindrome Linked List Сложность: easy Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае. Пример:

Input: head = [1,2,2,1]
Output: true

👨‍💻 Алгоритм: 1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null. 2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся. 3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата. 😎 Решение:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        currentNode = head

        while currentNode is not None:
            vals.append(currentNode.val)
            currentNode = currentNode.next

        front = 0
        back = len(vals) - 1
        while front < back:
            if vals[front] != vals[back]:
                return False
            front += 1
            back -= 1
        return True

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

Как предотвратить ущерб от 89% кибератак Хакеры пытаются пройти через DNS, но мы всё видим! 📊 89% кибератак осуществляются через DNS-протоколы. SWG-системы не распознают часть аномалий сразу, и злоумышленники успевают этим воспользоваться. 💻 Solar DNS Radar автоматизирует блокировку фишинга и зараженных доменов, чтобы снизить нагрузку на SOC. А еще замечает уже попавшие внутрь вирусные ПО, незаметно использующие DNS для связи с управляющими серверами. 📅 29 октября эксперты «Солара» проведут онлайн-презентацию сервиса. Расскажут о результатах реальных кейсов и бесплатном тестировании пилота на 1 месяц. Подключайтесь — Solar DNS Radar подойдет любому бизнесу, а интеграция облачной версии максимально простая и быстрая ✅ Зарегистрируйтесь, и мы отправим вам напоминание о старте трансляции. Узнать больше #реклама 16+ rt-solar.ru О рекламодателе

Задача: 163. Missing Ranges Сложность: easy Вам дан диапазон [lower, upper] и отсортированный массив уникальных целых чисел nums, где все элементы находятся в этом диапазоне. Число x считается пропущенным, если оно находится в диапазоне [lower, upper] и его нет в массиве nums. Верните кратчайший отсортированный список диапазонов, который точно покрывает все пропущенные числа. То есть ни один элемент из nums не включен в какой-либо из диапазонов, и каждое пропущенное число покрыто одним из диапазонов.. Пример:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

👨‍💻 Алгоритм: 1️⃣Инициализация и проверка начальных условий: Создайте переменную n и инициализируйте её размером массива nums. Создайте список missingRanges, который будет содержать решение задачи. Если массив nums пуст, верните диапазон [lower, upper]. Проверьте, совпадает ли первый элемент массива с lower. Если lower < nums[0], добавьте в missingRanges диапазон [lower, nums[0] - 1]. 2️⃣Итерация по элементам массива: Проитерируйте по всем элементам в nums с помощью цикла от i = 0 до n - 2 (до предпоследнего элемента): Если текущий элемент nums[i] и следующий элемент nums[i + 1] отличаются на 1 или меньше, между этими двумя числами нет пропущенных чисел. В противном случае, если nums[i + 1] - nums[i] > 1, то пропущены числа от nums[i] + 1 до nums[i + 1] - 1 (включительно). В этом случае диапазон [nums[i] + 1, nums[i + 1] - 1] добавляется в missingRanges. 3️⃣Проверка и добавление последнего пропущенного диапазона: Проверьте, совпадает ли последний элемент массива с upper. Если nums[n - 1] < upper, добавьте в missingRanges диапазон [nums[n - 1] + 1, upper]. 😎 Решение:

class Solution:
    def findMissingRanges(
        self, nums: List[int], lower: int, upper: int
    ) -> List[List[int]]:
        n = len(nums)
        missing_ranges = []
        if n == 0:
            missing_ranges.append([lower, upper])
            return missing_ranges
        if lower < nums[0]:
            missing_ranges.append([lower, nums[0] - 1])
        for i in range(n - 1):
            if nums[i + 1] - nums[i] <= 1:
                continue
            missing_ranges.append([nums[i] + 1, nums[i + 1] - 1])
        if upper > nums[n - 1]:
            missing_ranges.append([nums[n - 1] + 1, upper])

        return missing_ranges

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

Вебинар — увеличение прибыли для строительных компаний! Покажем на реальных кейсах, как убрать кассовые разрывы и увеличить прибыль с проекта на 300 000 ₽ Вы узнаете на встрече, как: - Исключить ошибки в сметах и ускорить расчеты - Закрывать кассовые разрывы и навести порядок в финансах - Перейти от excel таблиц к удобному инструменту для всей команды - Экономить до 15-20% на закупках - Контролировать стройку и бюджет в реальном времени Узнать больше #реклама 16+ gectaro.com О рекламодателе

Задача: 278. First Bad Version Сложность: easy Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими. Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими. Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API. Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

👨‍💻 Алгоритм: 1⃣Инициализация границ поиска: Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n. 2⃣Бинарный поиск: Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid). Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1. 3⃣Возврат результата: Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии. 😎 Решение:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

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

В Битрикс24 теперь можно сделать сайт за 30 секунд Серьёзно. Пишешь, что нужно, и AI сам всё собирает: тексты, картинки, оформление. ✨Никакой магии, просто умный помощник. Попробуйте — закайфуете от скорости! Попробовать #реклама 16+ sites-24.bitrix24.ru О рекламодателе

Задача: 1434. Number of Ways to Wear Different Hats to Each Other Сложность: hard Дано n человек и 40 видов шляп, пронумерованных от 1 до 40. Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком. Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга. Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7. Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

👨‍💻 Алгоритм: 1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей. 2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп. 3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп. 😎 Решение:

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        MOD = 1000000007
        n = len(hats)
        hatsToPeople = {}
        for i, hatList in enumerate(hats):
            for hat in hatList:
                if hat not in hatsToPeople:
                    hatsToPeople[hat] = []
                hatsToPeople[hat].append(i)
                
        done = (1 << n) - 1
        memo = [[-1] * done for _ in range(41)]

        def dp(hat, mask):
            if mask == done:
                return 1
            if hat > 40:
                return 0
            if memo[hat][mask] != -1:
                return memo[hat][mask]
            
            ans = dp(hat + 1, mask)
            if hat in hatsToPeople:
                for person in hatsToPeople[hat]:
                    if (mask & (1 << person)) == 0:
                        ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD
            
            memo[hat][mask] = ans
            return ans

        return dp(1, 0)

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

Задача: 1522. Diameter of N-Ary Tree Сложность: medium Дано корневое дерево N-арности, нужно вычислить длину диаметра дерева. Диаметр N-арного дерева - это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень. (Входная сериализация N-арного дерева представлена их обходом в порядке уровней, каждая группа дочерних узлов разделена значением null.) Пример:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

👨‍💻 Алгоритм: 1⃣Определите функцию height(node), которая возвращает высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один. 2⃣Внутри функции height(node) выберите две наибольшие высоты среди дочерних узлов. Эти два значения помогут вычислить длину пути, которая будет кандидатом на диаметр всего дерева. 3⃣Существует два подхода для выбора двух наибольших высот: — Первый способ заключается в хранении высот всех дочерних узлов в массиве, последующей сортировке массива и выборе двух наибольших элементов. — Второй способ использует две переменные, которые отслеживают текущие два наибольших значения. Во время итерации по всем высотам эти переменные обновляются соответствующим образом. 😎 Решение:

class Solution:
    def __init__(self):
        self.diameter = 0

    def height(self, node):
        if not node.children:
            return 0

        maxHeight1, maxHeight2 = 0, 0
        for child in node.children:
            parentHeight = self.height(child) + 1
            if parentHeight > maxHeight1:
                maxHeight2 = maxHeight1
                maxHeight1 = parentHeight
            elif parentHeight > maxHeight2:
                maxHeight2 = parentHeight
            distance = maxHeight1 + maxHeight2
            self.diameter = max(self.diameter, distance)
        return maxHeight1

    def diameter(self, root):
        self.diameter = 0
        self.height(root)
        return self.diameter

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

Задача: 443. String Compression Сложность: medium Дан массив символов chars, сжать его, используя следующий алгоритм: Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars: Если длина группы равна 1, добавьте символ к строке s. В противном случае добавьте символ, а за ним длину группы. Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars. После того как вы закончите модификацию входного массива, верните новую длину массива. Вы должны написать алгоритм, который использует только постоянное дополнительное пространство. Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

👨‍💻 Алгоритм: 1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0. 2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе. 3⃣Верните res. 😎 Решение:

class Solution:
    def compress(self, chars: List[str]) -> int:
        i = 0
        res = 0
        while i < len(chars):
            group_length = 1
            while (i + group_length < len(chars) and chars[i + group_length] == chars[i]):
                group_length += 1
            chars[res] = chars[i]
            res += 1
            if group_length > 1:
                str_repr = str(group_length)
                chars[res:res+len(str_repr)] = list(str_repr)
                res += len(str_repr)
            i += group_length
        return res

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

Задача: 779. K-th Symbol in Grammar Сложность: medium Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10. Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110. Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк. Пример:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

👨‍💻 Алгоритм: 1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal. 2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal). 3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal). 😎 Решение:

class Solution:
    def depthFirstSearch(self, n: int, k: int, rootVal: int) -> int:
        if n == 1:
            return rootVal
        totalNodes = 2 ** (n - 1)
        if k > totalNodes / 2:
            nextRootVal = 1 if rootVal == 0 else 0
            return self.depthFirstSearch(n - 1, k - (totalNodes / 2), nextRootVal)
        else:
            nextRootVal = 0 if rootVal == 0 else 1
            return self.depthFirstSearch(n - 1, k, nextRootVal)

    def kthGrammar(self, n: int, k: int) -> int:
        return self.depthFirstSearch(n, k, 0)

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

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60 Сложность: medium Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0. Пример:

Input: time = [30,20,150,100,40]
Output: 3

👨‍💻 Алгоритм: 1⃣Инициализация и вычисление остатков: Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями. 2⃣Подсчет пар: Пройдитесь по каждой песне в списке и для каждого элемента: Вычислите остаток от деления времени песни на 60. Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0). Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0). Обновите массив остатков, увеличивая количество песен с текущим остатком на 1. 3⃣Возврат результата: Верните общее количество пар. 😎 Решение:

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        remainders = [0] * 60
        count = 0
        
        for t in time:
            if t % 60 == 0:
                count += remainders[0]
            else:
                count += remainders[60 - t % 60]
            remainders[t % 60] += 1
        
        return count

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