Задача: 115. Distinct Subsequences
Сложность: hard

"Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t.

Тестовые примеры сгенерированы таким образом, что ответ укладывается в 32-битное целое число со знаком."

Пример:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

👨‍💻 Алгоритм:

1️⃣Определите функцию с названием recurse, которая принимает два целочисленных значения i и j. Первое значение представляет текущий обрабатываемый символ в строке S, а второе - текущий символ в строке T. Инициализируйте словарь под названием memo, который будет кэшировать результаты различных вызовов рекурсии.**

2️⃣Проверьте базовый случай. Если одна из строк закончилась, возвращается 0 или 1 в зависимости от того, удалось ли обработать всю строку T или нет. Есть ещё один базовый случай, который следует рассмотреть. Если оставшаяся длина строки S меньше, чем у строки T, то совпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и возвращается 0.**

3️⃣Затем проверяем, существует ли текущая пара индексов в нашем словаре. Если да, то просто возвращаем сохранённое/кэшированное значение. Если нет, то продолжаем обычную обработку. Сравниваем символы s[i] и t[j]. Сохраняем результат вызова recurse(i + 1, j) в переменную. Как упоминалось ранее, результат этой рекурсии необходим, независимо от совпадения символов. Если символы совпадают, добавляем к переменной результат вызова recurse(i + 1, j + 1). Наконец, сохраняем значение этой переменной в словаре с ключом (i, j) и возвращаем это значение в качестве ответа.

😎 Решение:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:

        memo = {}

        def uniqueSubsequences(i: int, j: int) -> int:

            M, N = len(s), len(t)

            if i == M or j == N or M - i < N - j:
                return int(j == len(t))

            if (i, j) in memo:
                return memo[i, j]

            ans = uniqueSubsequences(i + 1, j)

            if s[i] == t[j]:
                ans += uniqueSubsequences(i + 1, j + 1)

            memo[i, j] = ans
            return ans

        return uniqueSubsequences(0, 0)

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

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

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

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

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

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

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

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

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