一、 题目
输入一个数n，将这个数的格雷码输出。
例如：输入2，返回{0,1,3,2}
二、 分析
1、二进制码->格雷码（编码）：从最右边一位起，依次将每一位与左边一位异或（XOR），作为对应格雷码该位的值，最左边一位不变（相当于左边是0）；（对应以上代码的for循环里的循环体）。
格雷码->二进制码（解码）：从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。
2、找规律
以3位格雷码为例。
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
可以看到第n位的格雷码由两部分构成，一部分是n-1位格雷码，再加上1<<(n-1)和n-1位格雷码的逆序的和。
如下：
（0）00
（0）01
（0）11
（0）10
100+010=110
100+011=111
100+001=101
100+000=100
class Solution {
public:
vector<int> grayCode(int n) {
int num = 1<<n;
vector<int> ans;
ans.reserve(num);
for(int i=0;i<num;i++)
ans.push_back(i^(i>>1));
return ans;
}
};
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> ans;
if(n==0){
ans.push_back(0);
return ans;
}
vector<int> res = grayCode(n-1);
int len = res.size()-1;
int adder = 1<<(n-1);
for(int i=len;i>=0;i--){
res.push_back(adder+res[i]);
}
return res;
}
};