题目
思路
首先我们先看一下格雷编码的一些情况，为了一会方便理解，我们看它的二进制情况。
当n=1时，输出[0，1]
当n=2时，输出[00,01,11,10]
当n=3时，输出[000, 001, 011, 010, 110, 111, 101, 100]
我们可以看到2的前半部分就是1，3的前半部分就是2。
所以我们只需要求后半部分即可，
格雷码的生成有一个递推公式。已知n-1位的格雷码，如何得到n位的？方法是，首先将n-1位的格雷码列表逆序，然后每个数的最高位设为1，然后拼接到原来的列表后面。例如，n=1的格雷码是0,1。n=2的时候，将之前的逆序是1,0，然后前面加上最高位1，变成11,10，然后拼接到原来的00,01后面，得到00,01,11,10，对应十进制的0,1,3,2。
总结一下，就是：
-
将k-1位序列逆序。
-
对逆序后的每个元素，在最高位（即第k-1位）添加1。
-
将新生成的序列追加到原序列之后。
代码详解
首先，定义一个ans用来存储格雷码序列。
ans.reserve是将ans的capacity容量扩大，n位格雷码有2^n个序列，所以就给他2^n的空间。
至于里面为什么是1<<n。
它的意思就是把1向左移动n位
n=1, 移动完：10 2^1=2
n=2, 移动完：100 2^2=4
n=3, 移动完：1000 2^3=8
接着将里面的变量初始化为0。
for(int i=1;i<=n;i++) 这个是用来逐位构造格雷码的，对于n=1，只会循环一次
int m =ans.size();
这个是求ans现有的元素数
for(int j=m-1;j>=0;j--){ans.push_back(ans[j] | (1 << (i-1)));}这个就是对里面现有的数进行倒序访问。
ans.push_back(ans[j] | (1 << (i-1)));
这个是1左移i-1位与原有的数相或。如果i=1,就是1左移0位，其实他就是用来将第i-1位设为1，并添加到结果中。
当n=1时，输出[0，1]
当n=2时，输出[00,01,11,10]
对于这个例子，n=2就是将第二位设为1，分别是11，10并添加到序列中，因为是逆序，所以先给1加，后给0加。
最后返回ans即可。
代码
class Solution {
public:vector<int> grayCode(int n) {vector<int> ans;ans.reserve(1<<n);ans.push_back(0);for(int i=1;i<=n;i++){int m =ans.size();for(int j=m-1;j>=0;j--){ans.push_back(ans[j] | (1 << (i-1)));}}return ans;}
};
