Python | LeetCode

#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]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Серверное Оборудование Купить БУ в Москве с Гарантией! Компания WestComp продает бу серверное оборудование вендора HPE в поколении Gen8 Gen9 и Gen10 всех линеек в отличном состоянии! Купить серверы можно с НДС без повышения цены и в лизинг. Доступна услуга Colocation в ЦОД TIER III Москвы! Можно выгодно купить сервер HP Proliant DL или BL, СХД HPE 3PAR, HPE Synergy, HPE BladeSystem, HPE Apollo любой конфигурации с гарантией до 5 лет! Цены в 10 раз ниже чем на новое оборудование! Выбрать #реклама westcomp.ru О рекламодателе

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Пикник для ИТ-специалистов в Коломенском Отдохните в кругу опытных ИТ-специалистов. Будут лекции, музыка, мастер-классы, интерактив — и все это в один день. Ждем вас 17.08. Зарегистрироваться #реклама it-picnic.ru О рекламодателе

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

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

Виртуальный сервер в аренду в Турции или России. Отказоустойчивый виртуальный облачный сервер на базе виртуализации VMWARE по модели подписки. - Бесплатная миграция инфраструктуры в Турцию - Размещайте ресурсы в Турции или России и оплачивайте в рублях, турицких лирах или евро. - Храните резервные копии данных за рубежом для минимизации рисков - Продолжайте использовать импортное ПО, скачивайте обновления и патчи, общайтесь с техподдержкой - Доступность сервиса — от 99,982% SLA - Дата центры Tier III в России и Турции - Почасовой биллинг и постоплата Подключите услугу сегодня со скидкой 50% на инфраструктуру. Подать заявку #реклама cloud4y.ru О рекламодателе

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

IT аутсорсинг в СПб! Обслуживание серверов и оргтехники! АйТи аутсорсинг в СПб! Сертифицированные специалисты! Опытная команда IT специалистов! Сертификаты Microsoft! CISCO Mikrotik! 12 лет на рынке! Перейти на сайт #реклама svcnet.ru О рекламодателе

#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)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Получи грант на обучение в Центральном университете Получи несгораемый грант до 2 800 000 ₽ на учебу в бакалавриате Центрального университета. Гранты покрывают от 25 до 100% стоимости обучения. Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Доставка от 30 минут из кафе и ресторанов в Яндекс Еде Заказывайте без очередей в приложении или на сайте. Скидки и акции каждый день 👍 Попробовать #реклама 16+ plms.adj.st О рекламодателе

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

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