solution.md

# 格雷编码

<p>格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。</p>
<p>给定一个代表编码总位数的非负整数<em> n</em>，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。</p>
<p>格雷编码序列必须以 0 开头。</p>
<p>&nbsp;</p>
<p><strong>示例 1:</strong></p>
<pre><strong>输入:</strong>&nbsp;2<strong><br />输出:</strong>&nbsp;[0,1,3,2]<strong><br />解释:</strong>00 - 001 - 111 - 310 - 2对于给定的&nbsp;<em>n</em>，其格雷编码序列并不唯一。例如，[0,2,3,1]&nbsp;也是一个有效的格雷编码序列。00 - 010 - 211 - 301 - 1</pre>
<p><strong>示例&nbsp;2:</strong></p>
<pre><strong>输入:</strong>&nbsp;0<strong><br />输出:</strong>&nbsp;[0]<strong><br />解释:</strong> 我们定义格雷编码序列必须以 0 开头。给定编码总位数为 <em>n</em> 的格雷编码序列，其长度为 2<sup>n</sup>。当 <em>n</em> = 0 时，长度为 2<sup>0</sup> = 1。因此，当 <em>n</em> = 0 时，其格雷编码序列为 [0]。</pre>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    vector<int> res;
    int n = 2;
    res = sol.grayCode(n);
    for (auto i : res)
        cout << i << " ";

    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    vector<int> grayCode(int n)
    {
        vector<int> res;
        if (0 == n)
        {
            res.push_back(0);
        }
        else
        {
            res.push_back(0);
            res.push_back(1);
            int i = 2;
            while (i <= n)
            {
                int m = res.size();
                int cc = pow(2, i - 1);
                for (int j = 0; j < m; j++)
                {
                    res.push_back(cc + res[m - j]);
                }
                i++;
            }
        }
        return res;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    vector<int> grayCode(int n)
    {
        int size = 1 << n;
        vector<int> res;
        for (int i = 0; i < size; i++)
        {
            int graycode = i ^ (i >> 1);
            res.push_back(graycode);
        }
        return res;
    }
};
```

### B

```cpp
class Solution
{
public:
    vector<int> grayCode(int n)
    {
        vector<int> res;
        res.push_back(0);
        if (n == 0)
            return res;
        int head = 1;
        for (int i = 0; i < n; i++)
        {
            for (int j = res.size() - 1; j >= 0; j--)
            {
                res.push_back(head + res[j]);
            }
            head <<= 1;
        }
        return res;
    }
};
```

### C

```cpp
class Solution
{
public:
    vector<int> grayCode(int n)
    {
        vector<int> res;
        for (int i = 0; i < (int)pow(2, n); i++)
            res.push_back(i ^ (i >> 1));
        return res;
    }
};
```