89：格雷编码

问题描述

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例

输入: 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

输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
给定编码总位数为 n 的格雷编码序列，其长度为 2ⁿ。当 n = 0 时，长度为 2⁰ = 1。
因此，当 n = 0 时，其格雷编码序列为 [0]。

问题分析

1位二进制格雷编码，序列长度为2¹ = 2, n 位二进制格雷编码，长度为 2ⁿ。
没什么思路啊。好像可以用动态规划。因为它有很多个结果，我们要找符合条件的结果。
动态规划就是个以小见大的过程，所以我们先考虑1位二进制时的情况。

0
1

来，我们往上扩展，看看能不能制造出2位二进制时的情况。

00
01
------
10
11

我们给原来的结果集在开头分别加上0和1，我们发现有点意思，但是添加0和添加1的分界线的地方变化的不平滑，所以我们调换一下位置：

00
01
------
11
10

这样就可以了。可是，我们凭什么可以这么做呢？
首先，我们看全在开头添加0的情况。上一个结果集是符合格雷编码的，即相邻编码只有一位不同。所以都添加0的话，也是符合格雷编码的，因为此时还是只有一位不同。同理，在开头添加1的情况也是如此。
所以说，我们的问题是，在添加0和1的分界线上，我们如果按照原来的顺序的话，就会导致2位甚至多位不同，所以不符合题意。我们如果换个思路，在原来的结果集的添加0的最后一个编码的前面再加上个1，这不就是符合编码了吗？ 这就是镜面对称法的理论基础。

所以我们根据原来的序列就能生成现在的序列。我们可以用位运算而不是用字符串拼接再用二进制转码的方式，这样可以提高效率。

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

我们当然不满足于此。二进制码转格雷码是有公式的。

整理一下就是，我们可以通过异或的方式来解决这个问题。因为为了统一性，我们打算对第一位也用异或。由于右移后第一位是0，所以1与0异或结果是1，0与0异或结果是0，符合题意。

class Solution:
    def grayCode(self, n: int):
        res = []
        for i in range(2**n):
            res.append(i^i>>1)
        return res

*给了我们一个新思路：
以二进制为 0 值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。

以 n = 3 为例。

0 0 0 第零项初始化为 0。

0 0 1 第一项改变上一项最右边的位元

0 1 1 第二项改变上一项右起第一个为 1 的位元的左边位

0 1 0 第三项同第一项，改变上一项最右边的位元

1 1 0 第四项同第二项，改变最上一项右起第一个为 1 的位元的左边位

1 1 1 第五项同第一项，改变上一项最右边的位元

1 0 1 第六项同第二项，改变最上一项右起第一个为 1 的位元的左边位

1 0 0 第七项同第一项，改变上一项最右边的位元

思路有了，代码自然也就出来了。

class Solution:
    def grayCode(self, n: int):
        res = [0]
        for i in range(1,2**n):
            if i%2:
                res.append(res[-1]^1) # 异或的取反作用
            else: # 偶数步的逻辑
                tmp = curs = res[-1]
                for j in range(n):
                    if tmp & 1 > 0: # &用作筛选
                        curs ^= 1<<(j+1)
                        res.append(curs)
                        break
                    else:
                        tmp >>= 1
        return res