格雷编码

标签: 位运算 数学 回溯

难度: Medium

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
  • 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ，且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

提示：

  • 1 <= n <= 16

Submission

运行时间: 168 ms

内存: 18.1 MB

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = []

        def backtrack(path, choices=('0', '1')):
            if len(path) == n:
                num = int(''.join(path), 2)
                ans.append(num)
                return

            path.append(choices[0])
            backtrack(path, ('0', '1'))
            path.pop()

            path.append(choices[1])
            backtrack(path, ('1', '0'))
            path.pop()

        backtrack([])
        return ans

Explain

这个题解使用回溯法生成格雷码序列。它从空字符串开始，每次在当前字符串后面添加一个字符 '0' 或 '1'，然后递归地生成下一个字符。添加字符的顺序通过 choices 参数控制，第一次添加 '0' 后继续使用 ('0', '1')，添加 '1' 后改用 ('1', '0')，这样可以保证相邻的格雷码二进制表示只有一位不同。当字符串长度达到 n 时，将其转换为整数添加到结果列表中。

时间复杂度: O(n * 2^n)

空间复杂度: O(n * 2^n)

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = []

        def backtrack(path, choices=('0', '1')):
            if len(path) == n:
                # 当前字符串长度达到 n，将其转换为整数添加到结果列表中
                num = int(''.join(path), 2)
                ans.append(num)
                return

            # 添加字符 '0'，继续使用选择列表 ('0', '1')
            path.append(choices[0])
            backtrack(path, ('0', '1'))
            path.pop()

            # 添加字符 '1'，改用选择列表 ('1', '0')
            path.append(choices[1])
            backtrack(path, ('1', '0'))
            path.pop()

        backtrack([])
        return ans

Explore

在回溯算法中，确保每对相邻整数的二进制表示恰好一位不同是通过选择字符添加的策略实现的。具体来说，当添加一个字符后（例如 '0' 或 '1'），下一次的选择会反转（从 '0', '1' 变为 '1', '0' 或反之）。这种策略的核心在于它强制了每一步的变化都只影响二进制表示中的一个位，从而保证生成的序列满足格雷码的定义，即相邻的二进制数恰好一位不同。

在添加 '1' 后改用选择列表 ('1', '0') 而不是继续使用 ('0', '1') 的做法是为了确保生成的格雷码序列满足相邻码之间只有一位的差异。这种改变的顺序可以帮助算法在探索新的二进制位时，不会立即回到先前的状态，从而保证了序列的连续性和唯一性。通过这种方式，算法每次在二进制码的生成过程中都进入一个新的“分支”，避免了生成重复的码，并确保了格雷码的正确构造。

在使用回溯法生成格雷码序列时，虽然此算法实现本身不直接保证第一个和最后一个整数的二进制表示恰好一位不同，但这是格雷码的一个标准特性。通常，格雷码是设计为环形码，意味着列表的首尾两个码也应该只有一位之差。在实际应用中，可以在生成所有码之后，额外检查并确保首尾两个码满足这一条件，或者通过特定的构造方法（如反射格雷码方法）来保证。此回溯算法生成的是基本的格雷码序列，可能需要额外步骤来确保首尾闭环。

在使用回溯法生成格雷码的过程中，理论上有可能生成重复的码，特别是如果错误地管理了路径或者选择列表。然而，在此题解中通过递归回溯，每次添加字符后都会逆转选择列表的顺序，这样的设计有效地避免了重复路径的产生。每次递归返回时，都会撤销（pop）最近添加的字符，确保每个可能的码都是从未探索的状态开始生成的。这种策略确保了所有生成的码都是唯一的，没有重复。