题目描述
格雷码是一种二进制编码系统，如果任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。
给定一个非负整数n，表示代码的位数，打印格雷码的序列。格雷码序列必须以0开头。
例如：给定n=2，返回[0,1,3,2]. 格雷码的序列为：
00 - 0
01 - 1
11 - 3
10 - 2
注意：
对于一个给定的n，格雷码的序列不一定是唯一的，
例如：根据题目描述，[0,2,3,1]也是一个有效的格雷码序列
思路：
仔细观察上图，从后往前拿出数字，在最高位前面加1，因为最高位前面总是0，新加入的数字可以与尾部数字只有最高位前一位不同，而因为之前的序列是满足只有一位不同的，由于新的数字最高位都为1，所以这些数字也是满足要求的，而且这样可以保证遍历所有的情况。
代码：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> res = new ArrayList();
res.add(0);
for (int i=0; i<n; i++){
for (int j=res.size()-1; j>=0; j--){
int num = res.get(j);
num = num|(1<<i);
res.add(num);
}
}
return res;
}
}
