LeetCode 78, часто используемые советы по собеседованию, получить все подмножества через двоичный код

алгоритм

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


СегодняТемы LeetCodeВ 47-й статье давайте рассмотрим 78-е подмножества LeetCode.

Официальная сложность этого вопроса — средняя, ​​с 3489 лайками, 79 отклонениями и процентом ответов 59,9%. Из этих данных мы также можем видеть, что этоНе слишком сложно, но качественновопрос. Ведь при решении этой задачи вы освоите новый навык.

Без дальнейших церемоний, давайте сначала посмотрим на смысл вопроса.

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

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

Образец 

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

Скопируйте вопрос выше

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

Это легко понять, очевидно, мы можемПовторно используйте алгоритм из предыдущего вопроса, давайте пройдём это k, от 0 до n, мы сможем получить все подмножества. Пока вы ответили на предыдущий вопрос, этот вопрос почти не вызывает затруднений. Если вы не читали статью по предыдущему вопросу, вы можете ознакомиться с ней через портал:

LeetCode 77, комбинаторная задача, можете ли вы найти решение без рекурсии?

Давайте посмотрим непосредственно на код:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # 上一题求解k个组合的解法
        def combine(n, k, ret):
            window = list(range(1, k+1)) + [n+1]
            j = 0
            
            while j < k:
                cur = []
                for i in range(k):
                    cur.append(nums[window[i] - 1])
                ret.append(cur[:])
                
                j = 0
                while j < k and window[j+1] == window[j] + 1:
                    window[j] = j + 1
                    j += 1
                window[j] += 1
                
        # 手动添加空集
        ret = [[]]
        n = len(nums)
        # 遍历k从1到n
        for i in range(1, n+1):
            combine(n, i, ret)
        return ret

бинарная комбинация

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

Поскольку этот вопрос задает нам все подмножества, мы можемНачните с характеристик подмножества. Ранее мы узнали, что количество подмножества из n элементов равно. Это легко понять, потому что n элементов, каждый элемент имеет два состояния, опциональное или нет. иЭти n элементов не зависят друг от друга, то есть выбор или невыбор элемента не повлияет на другие элементы, поэтому мы можем знать, что всего будетВозможность.

Мы также можем начать с количества комбинаций, пусть количество всех подмножеств равно S, тогда в соответствии с решением, которое мы решили комбинацией выше, мы можем получить:

Результаты обоих одинаковы, что указывает на то, что этот вывод должен быть правильным.

Я не знаю, что вы думаете, когда видите n элементов, каждый элемент имеет два значения, если вы задали достаточно вопросов, вы сможете быстро думать о двоичном коде. Потому что в двоичном формате каждый двоичный бит имеет только два значения: 0 и 1. Затем мы можем использовать n-битные двоичные числа для представления состояния выбора n наборов элементов. Диапазон значений для n-битного двоичного числа составляет, так что мыперебрать его с помощью цикла, что эквивалентно циклу, проходящему по всем состояниям всей коллекции.

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

По этой методике нам очень просто реализовать код.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 遍历所有的状态
        # 1左移n位相当于2的n次方
        for s in range(1 << n):
            cur = []
            # 通过位运算找到每一位是0还是1
            for i in range(n):
                # 判断s状态在2的i次方上，也就是第i位上是0还是1
                if s & (1 << i):
                    cur.append(nums[i])
            ret.append(cur[:])
            
        return ret

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

Суммировать

Не знаю, что у вас осталось после прочтения статьи.Может первое чувство такоеЛецкод должен быть обновлен в порядкеПравильно ХД.

Действительно, у тестировщиков LeetCode есть правила постановки вопросов: часто после того, как задан вопрос, чтобы увеличить количество вопросов (сложить количество вопросов), они деформируют предыдущие вопросы и превращают их в новый вопрос. Итак, если вы пройдете вопросы по порядку, это будет очевидно. Если подумать с этой точки зрения, можно не только понять связь между темами, но иВыясните намерение спрашивающего, что тоже очень интересно.

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

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

Категории