LeetCode 89. 格雷编码

LeetCode 89. 格雷编码
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

1. 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
2. 第一个整数是 0
3. 一个整数在序列中出现 不超过一次
4. 每对 相邻 整数的二进制表示 恰好一位不同 ，且
5. 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列。

思路：
这道题的规律如果不是之前做过很难想到，我们更新格雷编码就是把前一个数字的格雷编码镜像翻转，前一半的后面补0，后一半的后面补1。

代码：

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res(1,0);//n = 0 的时候只有一个0

        while(n--){
            for(int i=res.size() - 1;i >= 0;i--){
                res[i]*=2;//前一半后面补0
                res.push_back(res[i] + 1);//后一半后面补1
            }
        }
        return res;
    }
};