Задача: 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

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

Задача: 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

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

Задача: 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)

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