Python | LeetCode

Задача: 1338. Reduce Array Size to The Half Сложность: medium Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива. Верните минимальный размер набора, чтобы было удалено не менее половины целых чисел из массива. Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        arr.sort()
        
        counts = []
        current_run = 1
        for i in range(1, len(arr)):
            if arr[i] == arr[i - 1]:
                current_run += 1
                continue
            counts.append(current_run)
            current_run = 1
        counts.append(current_run)
        
        counts.sort(reverse=True)
        
        numbers_removed_from_arr = 0
        set_size = 0
        for count in counts:
            numbers_removed_from_arr += count
            set_size += 1   
            if numbers_removed_from_arr >= len(arr) // 2:
                break
        
        return set_size

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

Бесплатный урок по шитью распашонки из трикотажа. Даже если до этого раньше не шили и не знаете, с какой стороны подойти к швейной машине За 1,5 часа в онлайн формате разберем: ✅как сшить удобную распашонку на кнопках и со встроенными царапками за пару часов ✅что делать, если нет оверлока, и как обойтись обычной швейной машинкой ✅3 лайфхака, без которых не получится шить качественно ✅как избежать ошибок при работе с трикотажем, на которых попадаются 90% новичков В прямом эфире покажу по шагам как сшить распашонку для новорождененого. Все подробно поясню: как раскроить, сметать, где что подложить, как правильно проложить строчку. Кстати, затраты на такую распашонку – 600 руб. В магазинах такого качества дешевле 3000 не купить. Для регистрации жмите кнопку "Зарегистрироваться": Бесплатных мест осталось мало: Зарегистрироваться #реклама 16+ foxmaman-sew.ru О рекламодателе

Задача: 509. Fibonacci Number Сложность: easy Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть, F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), для n > 1. Дано n, вычислите F(n). Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

👨‍💻 Алгоритм: 1⃣Проверка начального условия Если N <= 1, вернуть N. 2⃣Инициализация переменных Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения. 3⃣Итерация и вычисление Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации. 😎 Решение:

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        current, prev1, prev2 = 0, 1, 0
        for _ in range(2, N + 1):
            current = prev1 + prev2
            prev2, prev1 = prev1, current
        return current

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

Задача: 1040. Moving Stones Until Consecutive II Сложность: medium Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать. Пример:

Input: stones = [7,4,9]
Output: [1,2]

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

def numMovesStonesII(stones):
    stones.sort()
    n = len(stones)
    
    max_moves = stones[-1] - stones[0] + 1 - n
    max_moves -= min(stones[1] - stones[0] - 1, stones[-1] - stones[-2] - 1)

    min_moves = float('inf')
    j = 0

    for i in range(n):
        while j < n and stones[j] - stones[i] + 1 <= n:
            j += 1
        already_in_window = j - i
        if already_in_window == n - 1 and stones[j-1] - stones[i] + 1 == n - 1:
            min_moves = min(min_moves, 2)
        else:
            min_moves = min(min_moves, n - already_in_window)

    return [min_moves, max_moves]

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

Задача: 1086. High Five Сложность: easy Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента. Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания. Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления. Пример:

Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]

👨‍💻 Алгоритм: 1⃣Создайте словарь для хранения оценок каждого студента, где ключом будет ID студента, а значением — список его оценок. Переберите элементы в массиве items и добавьте каждую оценку в соответствующий список в словаре, используя ID студента как ключ. 2⃣Создайте список для хранения результата result. Переберите словарь и для каждого студента отсортируйте его оценки в порядке убывания, возьмите пять лучших оценок, вычислите их среднее значение (с целочисленным делением на 5) и добавьте пару [ID, topFiveAverage] в результат. 3⃣Отсортируйте список result по возрастанию ID студента и верните его. 😎 Решение:

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        K = 5
        items.sort(key=lambda x: (x[0], -x[1]))
        
        solution = []
        i = 0
        while i < len(items):
            id = items[i][0]
            sum = 0
            for k in range(i, i + K):
                sum += items[k][1]
            while i < len(items) and items[i][0] == id:
                i += 1
            solution.append([id, sum // K])
        
        return solution

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

Задача: 332. Reconstruct Itinerary Сложность: hard Вам дан список авиабилетов, где tickets[i] = [fromi, toi] представляют собой аэропорты отправления и прибытия одного рейса. Восстановите маршрут в порядке следования и верните его. Все билеты принадлежат человеку, который вылетает из "JFK", поэтому маршрут должен начинаться с "JFK". Если существует несколько возможных маршрутов, вы должны вернуть маршрут, который имеет наименьший лексикографический порядок при чтении как одна строка. Например, маршрут ["JFK", "LGA"] имеет меньший лексикографический порядок, чем ["JFK", "LGB"]. Вы можете предположить, что все билеты формируют хотя бы один действительный маршрут. Вы должны использовать все билеты один раз и только один раз. Пример:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

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

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        flight_map = defaultdict(list)
        for origin, dest in tickets:
            flight_map[origin].append(dest)
        
        for origin in flight_map:
            flight_map[origin].sort()
        
        result = []
        self.dfs("JFK", flight_map, result)
        return result
    
    def dfs(self, origin, flight_map, result):
        dest_list = flight_map[origin]
        while dest_list:
            next_dest = dest_list.pop(0)
            self.dfs(next_dest, flight_map, result)
        result.insert(0, origin)

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

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

Задача: 1365. How Many Numbers Are Smaller Than the Current Number Сложность: easy Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i]. Верните ответ в виде массива. Пример:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

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

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sorted_nums = sorted(nums)
        return [sorted_nums.index(num) for num in nums]

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

Запусти свой металлургический завод онлайн! В честь Дня металлурга РМК запустила необычную игру — ты можешь буквально пройтись по цеху, выполнять задания, узнавать, как устроено производство. Никаких сложностей — просто играешь, а дальше всё зависит от твоей внимательности и удачи. Почему это интересно: Это атмосферная игра, которая даёт почувствовать себя внутри настоящего завода — будто ты там работаешь. Только безопасно и из дома. Уже тысячи людей прошли её. Ты — следующий? Перейти на сайт #реклама 16+ rmkmetallurg.ru О рекламодателе

Задача: 1325. Delete Leaves With a Given Value Сложность: medium Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target. Обратите внимание, что после удаления листового узла со значением target, если его родительский узел становится листовым узлом и имеет значение target, он также должен быть удален (необходимо продолжать делать это, пока это возможно). Пример:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

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

class Solution:
    def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
        if not root:
            return None

        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)

        if not root.left and not root.right and root.val == target:
            return None

        return root

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

Электрические карнизы Onviz - открывайте шторы голосом Производим бесшумные электрокарнизы для штор в России с 2015 года. Доставка по всей РФ. Узнать больше #реклама karniz-onviz.ru О рекламодателе

Задача: 83. Remove Duplicates from Sorted List Сложность: easy Дана голова отсортированного связного списка. Удалите все дубликаты таким образом, чтобы каждый элемент появлялся только один раз. Верните также отсортированный связный список. Пример:

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

👨‍💻 Алгоритм: 1️⃣Это простая задача, которая проверяет вашу способность манипулировать указателями узлов списка. Поскольку входной список отсортирован, мы можем определить, является ли узел дубликатом, сравнив его значение с значением следующего узла в списке. 2️⃣Если узел является дубликатом, мы изменяем указатель next текущего узла так, чтобы он пропускал следующий узел и напрямую указывал на узел, следующий за следующим. 3️⃣Это позволяет исключить дубликаты из списка, продвигаясь вперёд по списку и корректируя связи между узлами для сохранения только уникальных элементов. 😎 Решение:

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        current = head
        while current is not None and current.next is not None:
            if current.next.val == current.val:
                current.next = current.next.next
            else:
                current = current.next
        return head

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

Задача: 312. Burst Balloons Сложность: hard Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики. Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1. Верните максимальное количество монет, которое можно собрать, лопая шарики с умом. Пример:

Input: nums = [1,5]
Output: 10

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

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        
        @lru_cache(None)
        def dp(left: int, right: int) -> int:
            if left > right:
                return 0
            max_coins = 0
            for i in range(left, right + 1):
                coins = dp(left, i - 1) + dp(i + 1, right) + nums[left - 1] * nums[i] * nums[right + 1]
                max_coins = max(max_coins, coins)
            return max_coins
        
        return dp(1, n - 2)

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

Задача: 832. Flipping an Image Сложность: easy Дано бинарное изображение размером n x n, необходимо перевернуть изображение по горизонтали, затем инвертировать его и вернуть результат. Перевернуть изображение по горизонтали означает, что каждая строка изображения будет развернута. Например, переворот строки [1,1,0] по горизонтали дает [0,1,1]. Инвертировать изображение означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0. Например, инверсия строки [0,1,1] дает [1,0,0]. Пример:

Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

👨‍💻 Алгоритм: 1⃣Переверните каждую строку по горизонтали, обменяв элементы слева направо и наоборот. 2⃣Инвертируйте каждую строку, заменив каждый 0 на 1 и каждый 1 на 0. 3⃣Верните преобразованное изображение. 😎 Решение:

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        C = len(A[0])

        for row in A:
            for i in range((C + 1) // 2):
                row[i], row[C - 1 - i] = row[C - 1 - i] ^ 1, row[i] ^ 1

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

REKONFA Live 6 ноября приглашаем рекламодателей, агентства и рекламные площадки обсудить технологии, маркетинговые инструменты и актуальные новинки. Ключевые участники рынка поделятся опытом и расскажут: — О ситуации на рынке рекламы — Как продвигать и продавать в интернете в 2025 году — Как бизнесу адаптироваться к меняющимся условиям Вас ждут доклады на актуальные темы, классный нетворкинг, вдохновляющая атмосфера для творчества и креатива. Встречаемся 6 ноября в Москве. Для тех, кто не сможет приехать, организуем интерактивное digital-шоу. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 16+ ya.rekonfa.ru О рекламодателе

Задача: 167. Two Sum II - Input Array Is Sorted Сложность: medium Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length. Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2]. Тесты генерируются таким образом, что существует ровно одно решение. Нельзя использовать один и тот же элемент дважды. Ваше решение должно использовать только константное дополнительное пространство. Пример:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

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

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low = 0
        high = len(numbers) - 1
        while low < high:
            sum = numbers[low] + numbers[high]

            if sum == target:
                return [low + 1, high + 1]
            elif sum < target:
                low += 1
            else:
                high -= 1
        return [-1, -1]

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

Задача: 1011. Capacity To Ship Packages Within D Days Сложность: medium На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней. Пример:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

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

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        def canShipInDays(capacity):
            days = 1
            total = 0
            for weight in weights:
                if total + weight > capacity:
                    days += 1
                    total = 0
                total += weight
            return days <= D
        
        left, right = max(weights), sum(weights)
        
        while left < right:
            mid = (left + right) // 2
            if canShipInDays(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

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

Задача: 989. Add to Array-Form of Integer Сложность: easy Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо. Например, для num = 1321, массивная форма - это [1, 3, 2, 1]. Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k. Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k). Завести переменную carry для хранения переноса и инициализировать ее нулем. Создать пустой массив result для хранения результата. 2⃣Сложение массивов: Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry). Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1. Если сумма меньше 10, установите carry в 0. Добавьте результат текущего сложения в массив result 3⃣Обработка оставшихся цифр и переноса: Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом. Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result. Переверните массив result обратно и верните его. 😎 Решение:

def addToArrayForm(num, k):
    num = num[::-1]
    k = list(map(int, str(k)))[::-1]
    
    carry = 0
    result = []
    i = 0
    
    while i < len(num) or i < len(k) or carry:
        n = num[i] if i < len(num) else 0
        m = k[i] if i < len(k) else 0
        total = n + m + carry
        carry = total // 10
        result.append(total % 10)
        i += 1
    
    return result[::-1]

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

Задача: 484. Find Permutation Сложность: medium Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её. Пример:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

👨‍💻 Алгоритм: 1⃣Инициализация Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки. 2⃣Для каждого числа i Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result. 3⃣Завершение Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку. 😎 Решение:

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        res = [0] * (len(s) + 1)
        stack = []
        j = 0
        for i in range(1, len(s) + 1):
            if s[i - 1] == 'I':
                stack.append(i)
                while stack:
                    res[j] = stack.pop()
                    j += 1
            else:
                stack.append(i)
        stack.append(len(s) + 1)
        while stack:
            res[j] = stack.pop()
            j += 1
        return res

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

Задача: 477. Total Hamming Distance Сложность: medium Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются. Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums. Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

class Solution:
    def totalHammingDistance(self, nums):
        ans = 0
        
        if not nums:
            return ans
        
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                ans += bin(nums[i] ^ nums[j]).count('1')
        
        return ans

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