89. 格雷编码
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
通过次数70,584提交次数97,569
法 2 构造法
思路
如下图所示，我们可以看出格雷码的一些规律：
n=1位格雷码有两个码字(0和1)
n位格雷码中的前(n-1)^2个码字等于n-1位格雷码的码字，按顺序书写，加前缀0
n位格雷码中的后(n-1)^2个码字等于n-1位格雷码的码字，按逆序书写，加前缀1
n位格雷码的集合 =n-1位格雷码集合(顺序)加前缀0+n-1位格雷码集合(逆序)加前缀1
如何在最高位置1呢？定义一个mask矩阵，没创建完一小轮，就mask = mask << 1，这样保证了mask永远指向最高位的。
题解
class Solution: def grayCode(self, n: int) -> List[int]: res = [] # 初始 1 位的要先写好 res.append(0) res.append(1) mask = 1 << 1 for i in range(2, n+1): # 倒序访问，最高位置 1 cur_size = len(res) for j in range(cur_size - 1, -1, -1): res.append(mask | res[j]) mask = mask << 1 return res
法1 回溯
思路
先填充0 ，再填充1。 满了三位就返回
题解
class Solution: def grayCode(self, n: int) -> List[int]: self.res = [] self.dfs(path="",n=n, nums=["0","1"]) return self.res def dfs(self, path, n, nums): if len(path) == n: self.res.append(int(path, 2)) return # 先补0 self.dfs(path+nums[0], n, ["0","1"]) # 再补1 self.dfs(path+nums[1], n, ["1","0"])