【leetcode】格雷编码

【leetcode】格雷编码

题目：

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

给定一个代表编码总位数的非负整数 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

示例 2:

输入: 0
输出:
[0]
解释: 我们定义
格雷编码序列必须以 0 开头。

给定
编码总位数为
n 的格雷编码序列，其长度为 2n
。
当 n = 0 时，长度为 20 = 1。
因此，当 n = 0 时，其格雷编码序列为 [0]。

思路：

编码的规律。什么规律呢？通过观察我们可以发现，格雷编码是通过上一级的编码得到的。也就是n个数的编码可以通过n - 1个数的编码得到。

如果n = 1，那么编码为[0, 1]；

n = 2，编码为[00, 10, 11, 01]；

n = 3，编码为[000, 100, 110, 010, 011, 111, 101, 001]；

所以，n级的编码的生成，是从n - 1编码的最后一个编码开始倒序遍历，每遍历一个编码，就将这个编码+1后的码字添加到结果列表的后面，然后再将这个编码+0。

比如，n = 2，编码为[00, 10, 11, 01]，倒序遍历，得到：

01，+1后生成新的码字添加到后面，再对01+0，结果列表变成[00, 10, 11, 010, 011]；

接着向前遍历，对11做与上一步相同的处理，结果列表变成[00, 10, 110, 010, 011, 111]；

最后，结果列表变为[000, 100, 110, 010, 011, 111, 101, 001]。这样生成的编码就是符合格雷编码条件的。也就是说，n级格雷编码是由n - 1级格雷编码生成的，这是很典型的递归思想。

最后，把二进制的字符转换成十进制整数就行。

根据这种规律，保持首位1不变，后面的位依次前一位异或即可。

比如n = 2，初始化res=[0]

i = 0时,change = 1 << 0 = 1。cur = 1-1 = 0, res.get(0) ^ change = 1, res.add(1)。此时res = [0,1]。

i = 1时,change = 1 << 1 = 2。cur = 2-1 =1, res.get(1)^change = 1^2 = 3,res.add(3)。

cur = 0, res.get(0)^change = 0^2 = 2,res.add(2)。

java代码：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        int cur;
        for(int i=0;i<n;i++){
            int change = 1 << i;
            cur = res.size()-1;
            while(cur >= 0){
                res.add(res.get(cur)^change);
                cur--;
            }
        }
        return res;
    }
}