//
// Created by 高森森 on 2022/1/27.
//

#ifndef LEETCODE_SOLUTION8_H
#define LEETCODE_SOLUTION8_H
#include<iostream>
using namespace std;
#include<vector>

class Solution8 {
public:
    vector<int> grayCode(int n) {
        vector<int>ret;
        ret.reserve(n);
        //G[0]=0
       ret.push_back(0);
       for(int i=1;i<=n;i++)
       {
           int m=ret.size();
           for(int j=m-1;j>=0;j--)
           {
               ret.push_back(ret[j]|(1<<i-1));
           }
       }
       return ret;
    }
    vector<int> grayCode2(int n){
        vector<int>ret;
        ret.reserve(n);
        int size=1<<n;
        for(int i=0;i<size;i++)
            ret.push_back((i>>1)^i);
        return ret;
    }

};


#endif //LEETCODE_SOLUTION8_H