89. 格雷编码

题目

• 题号：89
• 难度：中等
• https://leetcode-cn.com/problems/gray-code/

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。

示例1

输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。
00 - 0
10 - 2
11 - 3
01 - 1

实现

思路1 回溯法

由题目得我们需要对二进制编码的可能性进行搜索，并且相邻的数值仅能有一个位数的差异，也就是变换二进制编码时每次只能修改一个位数。因此我们可以把不同的二进制编码看作状态，初始状态设为全部为0的二进制数，例如n=3时初始状态为000，那么第一步对初始状态进行变换就只有n=3种可能（001，010，100这三种状态）。但具体选择哪个状态我们不能确定，可以先选择其中一条路径测试，若不是后面再退回到这一步选择另外的路径测试。
上面的思路用编程表达其实就是回溯法，循环终止的条件就是 树深depth == 。此时从根到叶节点的路径上的每个节点，就是格雷编码。
由于假设001后会再生成101, 011, 000三种状态，而000与选择过的根节点相同，我们不能再选，所以这里定义一个hashset记录已经选过的数值。

class Solution:
    def grayCode(self, n: int) -> List[int]:
        visit = set([0]) #先加入根节点的状态
        def backtrack(path):
            if len(path) == 2 ** n:
                return path
            for i in range(n):
                # 对上一个状态的每个数字变换
                transform = 1 << i ^ path[-1]  # 用异或
                if transform in visit:
                    continue
                visit.add(transform)
                # 先选择这个状态
                path.append(transform)
                if backtrack(path): # 若这个path是错的，最后会为空
                    return path    # 只有对的才会进入
                path.pop()
                visit.remove(transform)
        return backtrack([0])

时间复杂度：
空间复杂度：
**

思路2 镜像法

该方法源自别人的题解，需要对格雷编码有一定了解，可以发现以下规律：

1. 给 G(n) 阶格雷码每个元素二进制形式前面添加 0，得到 G’(n)；
2. 设 G(n) 集合倒序（镜像）为 R(n)，给 R(n) 每个元素二进制形式前面添加 1，得到 R’(n)；
3. 拼接上述两个集合得到下一阶格雷码。

编程实现以上规律：

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res, head = [0], 1
        for i in range(n):
            for j in range(len(res) - 1, -1, -1):
                res.append(head + res[j])
            head <<= 1
        return res

参考
https://leetcode-cn.com/problems/gray-code/solution/gray-code-jing-xiang-fan-she-fa-by-jyd/