The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return[0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example,[0,2,3,1]is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

class Solution {
public:
    vector<int> grayCode(int n) {
        int num = pow(2, n);
        vector<vector<char>> record;
        record.resize(num);
        for(int i = 0; i < record.size(); ++i){
            record[i].resize(n);
        }

        //根据观察，我们从纵向看，假设第k位，其01变化趋势是这样的：
        //第k位的连续2^(k-1)个元素的变化是一致的，只是在第2^(k- 1)倍数位置而且其倍数为奇数的时候发生变化，所以依据这个公式可以直接写出代码
        for(int i = 0; i < n; ++i){
            record[0][i] = '0';
        }
        for(int i = n - 1; i >= 0; --i){
            int n = pow(2, i);
            for(int j = 1; j < num; ++j){
                if(j % n != 0){
                    record[j][i] = record[j - 1][i];
                }
                else{
                    int k = j / n;
                    if(k % 2 != 0){
                        record[j][i] = ((record[j - 1][i] - '0') + 1) % 2 + '0';
                    }
                    else{
                        record[j][i] = record[j - 1][i];
                    }
                }
            }
        }
        //将二进制转换为数字
        vector<int> result;
        for(int i = 0; i < num; ++i){
            reverse(record[i].begin(), record[i].end());
            int num = 0;
            for(int j = 0; j < n; ++j){
                num += (record[i][j] - '0') * pow(2, n - j - 1);
            }
            result.push_back(num);
        }
        return result;
    }
};

int main(){
    Solution solution;
    solution.grayCode(3);
    return 0;
}