Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания

СегодняГлава 46Статья, давайте подойдем к 77 вопросам в LeetCode, Combinations (комбинации).

Можно сказать, что эта тема очень острая, и название всего из одного слова объясняет большую часть смысла темы. Официальная сложность этого вопроса — Medium, которая имеет высокий рейтинг в LeetCode: 1364 лайка и всего 66 отклонений. Проходимость составляет 53,6%.

смысл названия

Смысл названия очень прост, учитывая два целых числа n и k. n представляет n натуральных чисел от 1 до n, и требуется случайным образом выбрать k из этих n чисел.все комбинации.

Образец

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Мы уже знакомы с проблемой полной перестановки, а как насчет проблемы получения комбинаций?

рекурсия

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

Одна огромная разница между перестановкой и комбинацией заключается в том, чтоРасположение учитывает порядок размещения объектов. Другими словами, одни и те же элементы составлены, пока эти элементы заменены в каком-то порядке, они будут рассматриваться как разные аранжировки. Однако для комбинацийПорядок размещения объектов не учитываетсяиз. Пока эти элементы сформированы, независимо от того, как они расположены в одном и том же порядке, все они представляют собой одну и ту же комбинацию.

Когда мы получаем полную перестановку, мы используемВозвращение, мы, конечно, также можем использовать метод поиска с возвратом для получения комбинации. Но вопрос в том, как мы можем гарантировать, что получаемые нами комбинации представляют собой разные композиции элементов, а не разный порядок элементов?

Чтобы гарантировать это, нам нужно использовать небольшую идиоматическую процедуру, котораяУправляйте порядком, в котором извлекаются элементы, увеличивая индекс. Если мы ограничим индексы извлеченных элементов, которые будут увеличиваться, то мы можем гарантировать, что каждая извлеченная комбинация уникальна. Таким образом, мы можем добавить эту точку к методу поиска с возвратом.Пока мы понимаем это, этого нетрудно достичь.

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

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(start, cur):
            # 如果当前已经拿到了K个数的组合，直接加入答案
            # 注意要做深拷贝，否则在之后的回溯过程当中变动也会影响结果
            if len(cur) == k:
                ret.append(cur[:])
                return
            
            # 从start+1的位置开始遍历
            for i in range(start+1, n):
                cur.append(i+1)
                dfs(i, cur)
                # 回溯
                cur.pop()
                
        ret = []
        dfs(-1, [])
        return ret

повторять

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

Предположим, что n=8, k=3, тогда среди всех допустимых комбинаций наименьшая должна быть [1,2,3], а наибольшая должна быть [6,7,8]. Если мы убедимся, что элементы в комбинации расположены по порядку, то можно также определить соотношение размеров между комбинациями. Тогда мы можем думатьРазработайте схему, которая позволит нам выполнять итерации от наименьшей комбинации [1,2,3] до [6,7,8]., а также нужно следить за тем, чтобы порядок элементов в комбинации не нарушался в процессе итерации.

Мы можем представить, что эти n чисел выстроены в ряд на «линейке», и у нас есть k скользящих ящиков, чтобы перемещаться по ней. Результатом значений k скользящих блоков является комбинация k, выбранных из n элементов, и, поскольку скользящие блоки нельзя чередовать, значения k гарантированно будут упорядочены. Все, что нам нужно сделать, это спроектироватьАлгоритм перемещения выдвижного ящика, так что все комбинации могут быть найдены.

Мы можем представить, что в начале все скользящие ящики собраны в крайнем левом углу, и мы можем перемещать только скользящий ящик в крайнем правом углу. Мы переместили скользящую коробку из k в k+1, тогда в это время с правой стороны есть k-1 скользящих коробок, всего k позиций.

Тогда эта задача фактически превращается в подзадачу извлечения k-1 комбинаций из k элементов. Мы думаем об этой части 1-k как о новой «линейке», по которой мы перемещаем k-1 скользящих прямоугольников, чтобы получить все комбинации. Сначала нам нужно переместить все k-1 скользящих ящиков влево, а затем переместить крайний правый скользящий ящик. Затем цикл повторяется до тех пор, пока все скользящие блоки не переместятся на одну позицию вправо, что на самом деле является рекурсивным процессом.

Мы не будем вдаваться в весь процесс этой рекурсии, нам просто нужноРазберитесь с некоторыми ключевыми моментамиВот и все. Во-первых, для каждой рекурсии мыбудет перемещать только крайний правый скользящий блок в пределах этого рекурсивного диапазона, а во-вторых, мы знаем начальное состояние каждого рекурсивного процесса. В начальном состоянии все скользящие прямоугольники сосредоточены в крайнем левом углу «линейки», а в конечном состоянии все скользящие прямоугольники сосредоточены в крайнем правом углу.

Давайте разберем вышеприведенную логику Предположим, что после серии операций все m скользящих ящиков переместились в крайнее правое положение на линейке длины n. Это эквивалентнокомбинации были получены. Если в позиции n+1 есть скользящий ящик, и его правую сторону еще можно сдвинуть, то нам нужно переместить его на одну позицию вправо в позицию n+2. На данный момент остальная ситуация, для получения этих комбинаций мыВам нужно переместить все m скользящих прямоугольников в крайнее левое положение линейки., чтобы снова начать движение.

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

Позвольте мне сначала написать эту логику с рекурсией:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def comb(window, m, ret):
            ret.append(window[:-1])

            # 如果第m位的滑动框不超过直尺的范围并且m右侧的滑动框
            while window[m] < min(n - k + m + 1, window[m+1] - 1):
                # 向右滑动一位
                window[m] += 1
                # 如果m左侧还有滑动框，递归
                if m > 0:
                    # 把左侧的滑动框全部移动到最左侧
                    window[:m] = range(1, m+1)
                    comb(window, m-1, ret)
                else:
                    # 否则记录答案
                    ret.append(window[:-1])

                
        ret = []
        window = list(range(1, k+1))
        # 额外多放一个滑动框作为标兵
        window.append(n+1)
        comb(window, k-1, ret)
        return ret

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

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

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 构造滑动框
        window = list(range(1, k + 1)) + [n + 1]
        
        ret, j = [], 0

        while j < k:
            # 添加答案
            ret.append(window[:k])

            j = 0
            # 从最左侧的滑动框开始判断
            # 如果滑动框与它右侧滑动框挨着，那么就将它移动到最左侧
            # 因为它右侧的滑动框一定会向右移动
            while j < k and window[j + 1] == window[j] + 1:
                window[j] = j + 1
                j += 1
            # 连续挨着最右侧的滑动框向右移动一格
            window[j] += 1
            
        return ret

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

Суммировать

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

С точки зрения реализации кода рекурсивное решение метода скользящего ящика сложнее, чем нерекурсивное решение. Поскольку рекурсивные условия и логика более сложны, это также связано с проблемой хранения ответов. ноС точки зрения понимания, рекурсивное решение легче понять, нерекурсивные алгоритмы часто путаются со значением указателя j. Поэтому, если вы хотите понять алгоритм, вы можете начать с рекурсивного кода, а если вы хотите реализовать код, вы можете начать с нерекурсивного метода.

Эта тема очень интересна и заслуживает внимательного рассмотрения.

Если вам понравилась эта статья, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.

В этой статье используетсяmdniceнабор текста