#hard
Задача: 76. Minimum Window Substring

Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "".

Тестовые примеры будут сформированы таким образом, что ответ будет уникальным.

Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

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

1️⃣Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S.

2️⃣Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.

3️⃣Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.

😎 Решение:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        dict_t = Counter(t)
        required = len(dict_t)
        l, r = 0, 0
        formed = 0
        window_counts = {}
        ans = float("inf"), None, None

        while r < len(s):
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            while l <= r and formed == required:
                character = s[l]
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1

                l += 1

            r += 1
        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 77. Combinations

Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].

Ответ можно вернуть в любом порядке.

Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

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

1️⃣Инициализировать массив ответов ans и массив для построения комбинаций curr.

2️⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:
Если длина curr равна k, добавить копию curr в ans и вернуться.
Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.
Итерировать num от firstNum до firstNum + available включительно.
Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.

3️⃣Вызвать backtrack с изначально пустым curr и firstNum = 1.
Вернуть ans.

😎 Решение:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(curr, first_num):
            if len(curr) == k:
                ans.append(curr[:])
                return

            need = k - len(curr)
            remain = n - first_num + 1
            available = remain - need

            for num in range(first_num, first_num + available + 1):
                curr.append(num)
                backtrack(curr, num + 1)
                curr.pop()

        ans = []
        backtrack([], 1)
        return ans

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 78. Subsets

Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор).

Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.

Пример:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

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

1️⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.

2️⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.

3️⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.

😎 Решение:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first=0, curr=[]):
            if len(curr) == k:
                output.append(curr[:])
                return
            for i in range(first, n):
                curr.append(nums[i])
                backtrack(i + 1, curr)
                curr.pop()

        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 79. Word Search

Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.

Слово можно составить из букв последовательно смежных ячеек, где смежные ячейки находятся рядом по горизонтали или вертикали. Одна и та же ячейка с буквой не может быть использована более одного раза.

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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

1️⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки.

2️⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова.

3️⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования.

😎 Решение:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.ROWS = len(board)
        self.COLS = len(board[0])
        self.board = board

        for row in range(self.ROWS):
            for col in range(self.COLS):
                if self.backtrack(row, col, word):
                    return True
        return False

    def backtrack(self, row: int, col: int, suffix: str) -> bool:
        if len(suffix) == 0:
            return True

        if (row < 0 or row == self.ROWS or col < 0 or col == self.COLS or self.board[row][col] != suffix[0]):
            return False

        ret = False
        self.board[row][col] = "#"
        for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])
            if ret:
                break

        self.board[row][col] = suffix[0]
        return ret

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 80. Remove Duplicates from Sorted Array II

Дан массив целых чисел nums, отсортированный в неубывающем порядке. Удалите из него некоторые дубликаты на месте так, чтобы каждый уникальный элемент встречался не более двух раз. Относительный порядок элементов должен быть сохранён.

Поскольку в некоторых языках программирования невозможно изменить длину массива, результат следует разместить в первой части массива nums. Более формально, если после удаления дубликатов остаётся k элементов, то первые k элементов массива nums должны содержать итоговый результат. Не важно, что остаётся за пределами первых k элементов.

Верните k после размещения итогового результата в первые k слотов массива nums.

Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменяя исходный массив на месте с использованием дополнительной памяти O(1).

Пример:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

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

1️⃣Инициализация переменных: Используйте две переменные: i, которая указывает на текущий индекс в массиве, и count, которая отслеживает количество каждого элемента. Начните обработку массива с первого элемента (индекс 1), предполагая, что первый элемент всегда имеет count равный 1.

2️⃣Обработка элементов массива: Для каждого элемента в массиве:

3️⃣Если текущий элемент такой же, как предыдущий (nums[i] == nums[i - 1]), увеличьте count.
Если count больше 2, это означает, что текущий элемент встречается более двух раз. В этом случае удалите этот элемент из массива с помощью операции удаления, поддерживаемой вашим языком программирования (например, del, pop, remove), и уменьшите индекс i на 1, чтобы корректно обработать следующий элемент.
Если текущий элемент отличается от предыдущего (nums[i] != nums[i - 1]), это означает начало новой последовательности, поэтому сбросьте count к 1.
Возвращение результата: После обработки всех элементов в массиве, все ненужные дубликаты удалены, и в массиве остаются только допустимые элементы. Верните длину обработанного массива, так как это количество элементов, которые теперь соответствуют условиям задачи.

😎 Решение:

class Solution(object):
    def removeDuplicates(self, nums):
        i, count = 1, 1
        while i < len(nums):
            if nums[i] == nums[i - 1]:
                count += 1
                if count > 2:
                    nums.pop(i)
                    i -= 1
            else:
                count = 1
            i += 1
        return len(nums)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 81. Search in Rotated Sorted Array II

В массиве целых чисел nums, отсортированном в неубывающем порядке (не обязательно содержащем уникальные значения), произведена ротация в неизвестном индексе поворота k (0 <= k < nums.length). В результате массив принимает вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (нумерация с 0). Например, массив [0,1,2,4,4,4,5,6,6,7] может быть повернут в индексе 5 и превратиться в [4,5,6,6,7,0,1,2,4,4].

Для данного массива nums после ротации и целого числа target необходимо вернуть true, если target присутствует в nums, и false в противном случае.

Необходимо сократить количество операций поиска настолько, насколько это возможно.

Пример:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

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

1️⃣Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска.

2️⃣Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске:
Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end].
Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid).
Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска.
Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска.

3️⃣Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно.

😎 Решение:

class Solution:
    def search(self, nums, target):
        n = len(nums)
        if n == 0:
            return False
        end = n - 1
        start = 0
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return True
            if not self.isBinarySearchHelpful(nums, start, nums[mid]):
                start += 1
                continue
            pivotArray = self.existsInFirst(nums, start, nums[mid])
            targetArray = self.existsInFirst(nums, start, target)
            if pivotArray ^ targetArray:
                if pivotArray:
                    start = mid + 1
                else:
                    end = mid - 1
            else:
                if nums[mid] < target:
                    start = mid + 1
                else:
                    end = mid - 1
        return False

    def isBinarySearchHelpful(self, nums, start, element):
        return nums[start] != element

    def existsInFirst(self, nums, start, element):
        return nums[start] <= element

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 82. Remove Duplicates from Sorted List II

Дана голова отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные числа из исходного списка. Верните отсортированный связный список.

Пример:

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

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

1️⃣Инициализация "стража" и предшественника:
Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены.
Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж.

2️⃣Проход по списку с проверкой на дубликаты:
Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.
Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов.

3️⃣Переход к следующему узлу и возврат результата:
Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел.
Двигаем указатель head на следующий узел в списке.
После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов.

😎 Решение:

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        sentinel = ListNode(0, head)
        pred = sentinel

        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val:
                    head = head.next
                pred.next = head.next
            else:
                pred = pred.next
            head = head.next

        return sentinel.next

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

👨‍💻 Нужен человек для создания постов в сети каналов Leetcode. Работа оплачивается. Писать сюда

#easy
Задача: 83. Remove Duplicates from Sorted List

Дана голова отсортированного связного списка. Удалите все дубликаты таким образом, чтобы каждый элемент появлялся только один раз. Верните также отсортированный связный список.

Пример:

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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 84. Largest Rectangle in Histogram

Дан массив целых чисел heights, представляющий высоту столбцов гистограммы, где ширина каждого столбца равна 1. Верните площадь наибольшего прямоугольника в гистограмме.

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

1️⃣Введение в проблему:
Прежде всего, следует учитывать, что высота прямоугольника, образованного между любыми двумя столбиками, всегда будет ограничена высотой самого низкого столбика, находящегося между ними. Это можно понять, взглянув на рисунок ниже.

2️⃣Описание метода:
Таким образом, мы можем начать с рассмотрения каждой возможной пары столбиков и нахождения площади прямоугольника, образованного между ними, используя высоту самого низкого столбика между ними в качестве высоты и расстояние между ними в качестве ширины прямоугольника.

3️⃣Вычисление максимальной площади:
Таким образом, мы можем найти требуемый прямоугольник с максимальной площадью.

😎 Решение:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        for i in range(len(heights)):
            for j in range(i, len(heights)):
                min_height = inf
                for k in range(i, j + 1):
                    min_height = min(min_height, heights[k])
                max_area = max(max_area, min_height * (j - i + 1))
        return max_area

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 85. Maximal Rectangle

Дана бинарная матрица размером rows x cols, заполненная 0 и 1. Найдите наибольший прямоугольник, содержащий только 1, и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

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

1️⃣Вычисление максимальной ширины прямоугольника для каждой координаты: Для каждой ячейки в каждой строке сохраняем количество последовательных единиц. При прохождении по строке обновляем максимально возможную ширину в этой точке, используя формулу row[i] = row[i - 1] + 1, если row[i] == '1'.

2️⃣Определение максимальной площади прямоугольника с нижним правым углом в данной точке: При итерации вверх по столбцу максимальная ширина прямоугольника от исходной точки до текущей точки является минимальным значением среди всех максимальных ширин, с которыми мы сталкивались. Используем формулу maxWidth = min(maxWidth, widthHere) и curArea = maxWidth * (currentRow - originalRow + 1), затем обновляем maxArea = max(maxArea, curArea).

3️⃣Применение алгоритма для каждой точки ввода для глобального максимума: Преобразуя входные данные в набор гистограмм, где каждый столбец является новой гистограммой, мы вычисляем максимальную площадь для каждой гистограммы.

😎 Решение:

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        maxarea = 0
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == "0":
                    continue
                width = dp[i][j] = dp[i][j - 1] + 1 if j else 1
                for k in range(i, -1, -1):
                    width = min(width, dp[k][j])
                    maxarea = max(maxarea, width * (i - k + 1))
        return maxarea

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 86. Partition List

Дана голова связного списка и значение x. Разделите его так, чтобы все узлы с значениями меньше x находились перед узлами с значениями, равными или большими x.

Необходимо сохранить исходный относительный порядок узлов в каждой из двух частей.

Пример:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

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

1️⃣Инициализация указателей: Создайте два указателя before и after, каждый из которых инициализирован временным (dummy) узлом. Это упрощает управление границами списка, минимизируя необходимость проверок условий в коде.

2️⃣Итерация по исходному связному списку: Перемещайте каждый узел в список before, если его значение меньше x, и в список after, если его значение равно или больше x. Это сохраняет относительный порядок узлов в каждой из двух частей.

3️⃣Соединение списков: После обработки всех узлов исходного списка, соедините списки before и after. Удалите временные узлы в начале каждого списка перед их соединением, чтобы исключить их из итогового связного списка.

😎 Решение:

class Solution(object):
    def partition(self, head: ListNode, x: int) -> ListNode:
        before = before_head = ListNode(0)
        after = after_head = ListNode(0)

        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next

        after.next = None
        before.next = after_head.next

        return before_head.next

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 87. Scramble String

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:

1. Если длина строки равна 1, остановиться.
2. Если длина строки больше 1, выполнить следующее:
- Разделить строку на две непустые подстроки в случайном индексе, например, если строка это s, разделить её на x и y, где s = x + y.
- Случайным образом решить, поменять ли местами две подстроки или оставить их в том же порядке. То есть после этого шага s может стать s = x + y или s = y + x.
- Применить шаг 1 рекурсивно к каждой из двух подстрок x и y.

Для двух строк s1 и s2 одинаковой длины вернуть true, если s2 является перемешанной строкой s1, в противном случае вернуть false.

Пример:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

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

1️⃣- Итерируйте i от 0 до n-1.
- Итерируйте j от 0 до n-1.
- Установите dp[1][i][j] в булево значение s1[i] == s2[j]. (Базовый случай динамического программирования).

2️⃣- Итерируйте length от 2 до n.
- Итерируйте i от 0 до n + 1 - length.
- Итерируйте j от 0 до n + 1 - length.

3️⃣- Итерируйте newLength от 1 до length - 1.
- Если dp[newLength][i][j] && dp[length-newLength][i+newLength][j+newLength]) || (dp[newLength][i][j+length-newLength] && dp[length-newLength][i+newLength][j]) верно, установите dp[length][i][j] в true.
- Верните dp[n][0][0].

😎 Решение:

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        dp = [
            [[False for j in range(n)] for i in range(n)] for l in range(n + 1)
        ]
        for i in range(n):
            for j in range(n):
                dp[1][i][j] = s1[i] == s2[j]
        for length in range(2, n + 1):
            for i in range(n + 1 - length):
                for j in range(n + 1 - length):
                    for new_length in range(1, length):
                        dp1 = dp[new_length][i]
                        dp2 = dp[length - new_length][i + new_length]
                        dp[length][i][j] |= dp1[j] and dp2[j + new_length]
                        dp[length][i][j] |= (
                            dp1[j + length - new_length] and dp2[j]
                        )
        return dp[n][0][0]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 88. Merge Sorted Array

Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.

Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.

Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.

Пример:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

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

1️⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух указателей для чтения и одного указателя для записи для чтения значений из nums1Copy и nums2 и записи их в nums1.

2️⃣Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1.
Инициализируйте указатель для чтения p1 в начале nums1Copy.
Инициализируйте указатель для чтения p2 в начале nums2.

3️⃣Инициализируйте указатель для записи p в начале nums1.
Пока p все еще находится внутри nums1:
Если nums1Copy[p1] существует и меньше или равно nums2[p2]:
Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1.
Иначе
Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1.
Увеличьте p на 1.

😎 Решение:

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1_copy = nums1[:m]
        p1 = 0
        p2 = 0
        for p in range(n + m):
            if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):
                nums1[p] = nums1_copy[p1]
                p1 += 1
            else:
                nums1[p] = nums2[p2]
                p2 += 1

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 89. Gray Code

Последовательность Грея с n-битами — это последовательность из 2^n целых чисел, где:

1. Каждое число находится в включающем диапазоне от 0 до 2^n - 1,
2. Первое число равно 0,
3. Каждое число встречается в последовательности не более одного раза,
4. Двоичное представление каждой пары соседних чисел отличается ровно на один бит,
5. Двоичное представление первого и последнего чисел отличается ровно на один бит.

Для заданного числа n возвращается любая допустимая последовательность Грея с n-битами.

Пример:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

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

1️⃣Инициализируйте список результатов для хранения последовательности решений. Добавьте 0 в список перед вызовом вспомогательного метода, так как все последовательности Грея начинаются с 0.

2️⃣Инициализируйте множество visited. Это позволяет отслеживать числа, присутствующие в текущей последовательности, чтобы избежать повторения.
Начните с числа 0.
В функции grayCodeHelper() используйте цикл for, чтобы найти каждое возможное число (next), которое может быть сгенерировано путем изменения одного бита последнего числа в списке результатов (current). Делайте это, переключая i-ый бит на каждой итерации. Поскольку максимально возможное количество битов в любом числе последовательности равно n, необходимо переключить n битов.

3️⃣Если next не присутствует в множестве использованных чисел (isPresent), добавьте его в список результатов и множество isPresent.
Продолжайте поиск с next.
Если grayCodeHelper(next) возвращает true, это означает, что допустимая последовательность найдена. Дальнейший поиск не требуется (ранняя остановка). Это раннее завершение улучшает время выполнения.
Если с next не найдена допустимая последовательность, удаляем его из списка результатов и множества isPresent и продолжаем поиск.
При достижении базового условия, когда длина текущей последовательности равна 2^n, возвращаем true.
Выход из цикла for означает, что с current в качестве последнего числа не найдена допустимая последовательность кода Грея. Поэтому возвращаем false.

😎 Решение:

class Solution:
    def grayCode(self, n: int):
        result = [0]
        isPresent = {0}
        self.grayCodeHelper(result, n, isPresent)
        return result

    def grayCodeHelper(self, result, n, isPresent):
        if len(result) == (1 << n):
            return True
        current = result[-1]
        for i in range(n):
            nextNum = current ^ (1 << i)
            if nextNum not in isPresent:
                isPresent.add(nextNum)
                result.append(nextNum)
                if self.grayCodeHelper(result, n, isPresent):
                    return True
                isPresent.remove(nextNum)
                result.pop()
        return False

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 90. Subsets II

Дан массив целых чисел nums, который может содержать повторяющиеся элементы. Верните все возможные подмножества (степенной набор).

Результирующий набор не должен содержать дублирующихся подмножеств. Возвращаемый результат может быть в любом порядке.

Пример:

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

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

1️⃣Отсортируйте массив nums. Сортировка необходима для того, чтобы все сгенерированные подмножества также были отсортированы. Это помогает идентифицировать дубликаты.

2️⃣Инициализируйте maxNumberOfSubsets максимальным количеством подмножеств, которые можно сгенерировать, т.е., 2 в степени n.

Инициализируйте множество, seen, типа string, для хранения всех сгенерированных подмножеств. Добавление всех отсортированных подмножеств в множество дает нам возможность отловить любые дублирующие подмножества.

3️⃣Итерируйте от 0 до maxNumberOfSubsets - 1. Установленные биты в двоичном представлении subsetIndex указывают на позицию элементов в массиве nums, которые присутствуют в текущем подмножестве.

Инициализируйте строку hashcode, которая будет хранить список чисел в текущемSubset в виде строки, разделенной запятыми. hashcode необходим для уникальной идентификации каждого подмножества с помощью множества.

Выполните внутренний цикл for от j = 0 до n - 1, чтобы проверить позицию установленных битов в subsetIndex. Если на позиции j установлен бит, добавьте nums[j] в текущее подмножество currentSubset и добавьте nums[j] в строку hashcode.

Добавьте текущее подмножество currentSubset в seen и в список подмножеств, если сгенерированный hashcode еще не в seen.

Верните подмножества.

😎 Решение:

class Solution:
    def subsetsWithDup(self, nums):
        n = len(nums)
        nums.sort()
        maxNumberOfSubsets = 2**n
        seen = set()
        subsets = []
        for subsetIndex in range(maxNumberOfSubsets):
            currentSubset = []
            hashcode = ""
            for j in range(n):
                mask = 2**j
                isSet = mask & subsetIndex
                if isSet != 0:
                    currentSubset.append(nums[j])
                    hashcode += str(nums[j]) + ","
            if hashcode not in seen:
                subsets.append(currentSubset)
                seen.add(hashcode)
        return subsets

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 91. Decode Ways

Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:

- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"

Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:

- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)

Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06".

Для данной строки s, содержащей только цифры, верните количество способов декодирования.

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

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

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


1️⃣Входим в рекурсию с данной строкой, начиная с индекса 0.

2️⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.

3️⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.


😎 Решение:

from functools import lru_cache

class Solution:

    @lru_cache(maxsize=None)
    def recursiveWithMemo(self, index, s) -> int:
        if index == len(s):
            return 1

        if s[index] == "0":
            return 0

        if index == len(s) - 1:
            return 1

        answer = self.recursiveWithMemo(index + 1, s)
        if int(s[index: index + 2]) <= 26:
            answer += self.recursiveWithMemo(index + 2, s)

        return answer

    def numDecodings(self, s: str) -> int:
        return self.recursiveWithMemo(0, s)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 92. Reverse Linked List II

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

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

1️⃣Определяем рекурсивную функцию, которая будет отвечать за переворачивание части односвязного списка. Назовем эту функцию recurse. Функция принимает три параметра: m, начальную точку переворота, n, конечную точку переворота, и указатель right, который начинается с узла n в связанном списке и движется назад вместе с откатом рекурсии. Если это пока не ясно, следующие диаграммы помогут.

2️⃣Также у нас есть указатель left, который начинается с узла m в связанном списке и движется вперед. В Python мы должны использовать глобальную переменную для этого, которая изменяется с каждым вызовом рекурсии. В других языках, где изменения, сделанные в вызовах функций, сохраняются, мы можем рассматривать этот указатель как дополнительную переменную для функции recurse.
В рекурсивном вызове, учитывая m, n и right, мы проверяем, равно ли n единице. Если это так, дальше двигаться не нужно.

3️⃣До тех пор, пока мы не достигнем n = 1, мы продолжаем двигать указатель right на один шаг вперед, после чего делаем рекурсивный вызов с уменьшенным на один значением n. В то же время мы продолжаем двигать указатель left вперед до тех пор, пока m не станет равным 1. Когда мы говорим, что указатель движется вперед, мы имеем в виду pointer.next.
Таким образом, мы откатываемся, как только n достигает 1. В этот момент указатель right находится на последнем узле подсписка, который мы хотим перевернуть, и left уже достиг первого узла этого подсписка. Тогда мы меняем данные и перемещаем указатель left на один шаг вперед с помощью left = left.next. Нам нужно, чтобы это изменение сохранялось в процессе отката.
Оттуда при каждом откате указатель right движется на один шаг назад. Это и есть та симуляция, о которой мы всё время говорили. Обратное движение симулируется откатом.
Мы прекращаем обмены, когда right == left, что происходит, если размер подсписка нечетный, или right.next == left, что происходит в процессе отката для четного подсписка, когда указатель right пересекает left. Мы используем глобальный булевый флаг для остановки обменов, как только эти условия выполнены.

😎 Решение:

class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], m: int, n: int
    ) -> Optional[ListNode]:
        if not head:
            return None

        left, right = head, head
        stop = False

        def recurseAndReverse(right, m, n):
            nonlocal left, stop
            if n == 1:
                return
            right = right.next
            if m > 1:
                left = left.next
            recurseAndReverse(right, m - 1, n - 1)
            if left == right or right.next == left:
                stop = True
            if not stop:
                left.val, right.val = right.val, left.val
                left = left.next

        recurseAndReverse(right, m, n)
        return head

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 93. Restore IP Addresses

Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:

- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"

Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:

- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)

Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06".

Для данной строки s, содержащей только цифры, верните количество способов декодирования.

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

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

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


1️⃣Входим в рекурсию с данной строкой, начиная с индекса 0.

2️⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.

3️⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.


😎 Решение:

class Solution(object):
    def valid(self, s, start, length):
        return length == 1 or (
            s[start] != "0"
            and (length < 3 or s[start : start + length] <= "255")
        )

    def helper(self, s, startIndex, dots, ans):
        remainingLength = len(s) - startIndex
        remainingNumberOfIntegers = 4 - len(dots)
        if (
            remainingLength > remainingNumberOfIntegers * 3
            or remainingLength < remainingNumberOfIntegers
        ):
            return
        if len(dots) == 3:
            if self.valid(s, startIndex, remainingLength):
                temp = ""
                last = 0
                for dot in dots:
                    temp += s[last : last + dot] + "."
                    last += dot
                temp += s[startIndex:]
                ans.append(temp)
            return
        for curPos in range(1, min(4, remainingLength + 1)):
            dots.append(curPos)
            if self.valid(s, startIndex, curPos):
                self.helper(s, startIndex + curPos, dots, ans)
            dots.pop()

    def restoreIpAddresses(self, s):
        answer = []
        self.helper(s, 0, [], answer)
        return answer

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 94. Binary Tree Inorder Traversal

Дан корень бинарного дерева. Верните обход значений его узлов в симметричном порядке.

Пример:

Input: root = [1,null,2,3]
Output: [1,3,2]

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

Метод решения этой задачи использует рекурсию. Это классический метод, и он простой. Мы можем определить вспомогательную функцию для реализации рекурсии.

😎 Решение:

class Solution:
    def inorderTraversal(self, root):
        res = []
        self.helper(root, res)
        return res

    def helper(self, root, res):
        if root is not None:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых