Python | LeetCode

Задача: 1046. Last Stone Weight Сложность: easy Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0. Пример:

    
        Input: stones = [2,7,4,1,8,1]
Output: 1{}
    

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

    
        import heapq

def lastStoneWeight(stones):
    stones = [-stone for stone in stones]
    heapq.heapify(stones)
    
    while len(stones) > 1:
        first = -heapq.heappop(stones)
        second = -heapq.heappop(stones)
        if first != second:
            heapq.heappush(stones, -(first - second))
    
    return -stones[0] if stones else 0{}
    

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

Задача: 252. Meeting Rooms Сложность: easy Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи. Пример:

    
        Input: intervals = [[0,30],[5,10],[15,20]]
Output: false{}
    

👨‍💻 Алгоритм: 1️⃣Создайте функцию для проверки перекрытия двух интервалов: Возвращайте true, если начало одного интервала находится внутри другого интервала. 2️⃣Проверьте каждый интервал с каждым другим интервалом: Если найдено перекрытие, верните false. 3️⃣Если все интервалы проверены и перекрытий не найдено, верните true. 😎 Решение:

    
        class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        def overlap(interval1: List[int], interval2: List[int]) -> bool:
            return (interval1[0] >= interval2[0] and interval1[0] < interval2[1]
                or interval2[0] >= interval1[0] and interval2[0] < interval1[1])

        for i in range(len(intervals)):
            for j in range(i + 1, len(intervals)):
                if overlap(intervals[i], intervals[j]):
                    return False
        return True{}
    

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

Задача: 341. Flatten Nested List Iterator Сложность: medium Вам дан вложенный список целых чисел nestedList. Каждый элемент либо является целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Реализуйте итератор для его развёртки. Реализуйте класс NestedIterator: NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList. int next() Возвращает следующий целый элемент вложенного списка. boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае. Пример:

    
        Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].{}
    

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

    
        class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        self._flatten(nestedList)
    
    def _flatten(self, nestedList):
        for ni in reversed(nestedList):
            self.stack.append(ni)
    
    def next(self) -> int:
        return self.stack.pop().getInteger()
    
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            self._flatten(self.stack.pop().getList())
        return bool(self.stack){}
    

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

Задача: 281. Zigzag Iterator Сложность: medium Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно. Реализуйте класс ZigzagIterator: ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2. boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае. int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу. Пример:

    
        Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].{}
    

👨‍💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors. Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст. 2⃣Метод next: Удалите первую пару индексов из очереди. Извлеките элемент из соответствующего списка по указанным индексам. Если в текущем списке есть еще элементы, добавьте новую пару индексов (тот же список, следующий элемент) в конец очереди. Верните извлеченный элемент. 3⃣Метод hasNext: Проверьте, пуста ли очередь. Верните true, если в очереди есть элементы, и false в противном случае. 😎 Решение:

    
        from collections import deque

class ZigzagIterator:
    def __init__(self, v1, v2):
        self.vectors = [v1, v2]
        self.queue = deque((i, 0) for i, vec in enumerate(self.vectors) if vec)

    def next(self):
        vecIndex, elemIndex = self.queue.popleft()
        if elemIndex + 1 < len(self.vectors[vecIndex]):
            self.queue.append((vecIndex, elemIndex + 1))
        return self.vectors[vecIndex][elemIndex]

    def hasNext(self):
        return bool(self.queue){}
    

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

Задача: 25. Reverse Nodes in k-Group Сложность: hard Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список. k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть. Вы не можете изменять значения в узлах списка, можно изменять только сами узлы. Пример:

    
        Input: head = [1,2,3,4,5], k = 2  
Output: [2,1,4,3,5]  {}
    

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

    
        class Solution:  
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:  
        if k == 1:  
            return head  

        def reverse(first, last, pre_first):  
            nonlocal head  
            if pre_first:  
                pre_first.next = last  
            else:  
                head = last  

            prev, curr = first, first.next  
            first.next = last.next  
            for _ in range(k-1):  
                curr.next, prev, curr = prev, curr, curr.next  

        count = 1  
        curr = first = head  
        pre_first = None  
        while curr:  
            if count == k:  
                reverse(first, curr, pre_first)  
                pre_first = first  
                curr, first = first.next, first.next  
                count = 1  
            else:  
                curr = curr.next  
                count += 1  

        return head{}
    

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

Задача: 369. Plus One Linked List Сложность: hard Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу. Цифры хранятся таким образом, что самая значимая цифра находится в начале списка. Пример:

    
        Input: head = [1,2,3]
Output: [1,2,4]{}
    

👨‍💻 Алгоритм: 1️⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти. 2️⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль. 3️⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next). 😎 Решение:

    
        class Solution:
    def plusOne(self, head: ListNode) -> ListNode:
        # sentinel head
        sentinel = ListNode(0)
        sentinel.next = head
        not_nine = sentinel

        # find the rightmost not-nine digit
        while head:
            if head.val != 9:
                not_nine = head
            head = head.next

        # increase this rightmost not-nine digit by 1
        not_nine.val += 1
        not_nine = not_nine.next

        # set all the following nines to zeros
        while not_nine:
            not_nine.val = 0
            not_nine = not_nine.next

        return sentinel if sentinel.val else sentinel.next{}
    

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

ВитаМишки - мощный заряд детского иммунитета! 📅 Осень — время возвращаться к привычному ритму: школа, секции, ранние подъёмы. Для ребёнка это серьёзная адаптация: новый график, стресс, тесные помещения, контакт с большим количеством людей. Помогите иммунитету справиться с нагрузкой — начните приём ВитаМишки Smart Fruits IMMUNO+. ✅ Витамины С, D3 и цинк участвуют в выработке иммунных клеток и поддерживают защитные силы. ✅ Витамин Е и селен — мощные антиоксиданты, защищающие организм изнутри. ✅ Экстракт облепихи укрепляет и оказывает общеоздоравливающее действие. Сделано на основе натуральных соков, без красителей и ароматизаторов. Забота, которую дети принимают с удовольствием. ВитаМишки Smart Fruits — дети обожают, мамы — доверяют! Перейти на сайт Не является лекарством #реклама vitamishki.ru О рекламодателе

Задача: 1214. Two Sum BSTs Сложность: medium Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target. Пример:

    
        Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false{}
    

👨‍💻 Алгоритм: 1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2. 2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2. 3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false. 😎 Решение:

    
        class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def dfs(self, node, node_set):
        if not node:
            return
        self.dfs(node.left, node_set)
        node_set.add(node.val)
        self.dfs(node.right, node_set)

    def twoSumBSTs(self, root1, root2, target):
        node_set1 = set()
        node_set2 = set()
        self.dfs(root1, node_set1)
        self.dfs(root2, node_set2)
        
        for value1 in node_set1:
            if target - value1 in node_set2:
                return True
                
        return False{}
    

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

Задача: 560. Subarray Sum Equals K Сложность: medium Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k. Подмассив - это непрерывная непустая последовательность элементов внутри массива. Пример:

    
        Input: nums = [1,1,1], k = 2
Output: 2{}
    

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

    
        class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        for start in range(len(nums)):
            for end in range(start + 1, len(nums) + 1):
                sum_ = sum(nums[start:end])
                if sum_ == k:
                    count += 1
        return count{}
    

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

Задача: 155. Min Stack Сложность: medium Разработайте стек, который поддерживает операции добавления элемента, удаления элемента, получения верхнего элемента и извлечения минимального элемента за постоянное время. Реализуйте класс MinStack: MinStack() инициализирует объект стека. void push(int val) добавляет элемент val в стек. void pop() удаляет элемент на вершине стека. int top() возвращает верхний элемент стека. int getMin() извлекает минимальный элемент в стеке. Вы должны реализовать решение с временной сложностью O(1) для каждой функции. Пример:

    
        Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2{}
    

👨‍💻 Алгоритм: 1️⃣Инициализация стека: Создайте структуру данных, которая будет использоваться для хранения элементов стека. Эта структура должна поддерживать не только обычные операции стека, но и быстрый доступ к минимальному элементу. Инициализируйте стек с помощью конструктора MinStack(), который подготовит все необходимые структуры данных для дальнейшей работы. 2️⃣Работа со стеком: Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin(). Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента. 3️⃣Доступ к элементам: Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]). Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время. 😎 Решение:

    
        class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append((x, x))
            return
        current_min = self.stack[-1][1]
        self.stack.append((x, min(x, current_min)))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]{}
    

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