【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;
}
}
