89. Gray Code.md

89. Gray Code

思路

思路一

就按照题目的意思进行模拟，用数组res和一个set来记录已经产生的结果，我们从0开始，遍历其二进制每一位，对其取反， 然后看其是否在set中出现过，如果没有，我们将其加入set和结果res中，然后再递归对这个数进行刚刚的操作，这样就可以得到所有的格雷码了。

思路二

如果对格雷码（可参考维基百科）熟悉的话这题其实就是将二进制转换为格雷码， 举个例子，3位的格雷码和二进制如下所示:

Int    Grey Code    Binary
 0  　　  000        000
 1  　　  001        001
 2   　 　011        010
 3   　 　010        011
 4   　 　110        100
 5   　 　111        101
 6   　 　101        110
 7   　　 100        111

参考维基百科及这篇博客可很容易地写出代码。

思路三（最快）

参考维基百科我们知道，格雷码是按照镜面排列的，n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到，如下图所示。

可以在前面加上新位元（如上图绿色所示），这样就和思路二产生的一样了；也可以在后面添加新位元，也是满足要求的（相邻两个编码只有一个bit不同）。

C++

思路一

class Solution {
private:
    void helper(vector<int> &res, set<int> &s, int code, int n){
        s.insert(code);
        res.push_back(code);
        
        for(int i = 0; i < n; i++){
            int mask = (1 << i);
            int t = code;
            if((t & mask) == 0)  // 第i位是0
                t |= mask;      // 把第i位变成1
            else            // 第i位是1
                t &= ~mask; // 把第i位变成0
            if(s.count(t)) continue;
            helper(res, s, t, n);
            break;
        }
    }
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        set<int>s;
        helper(res, s, 0, n);
        return res;
    }
};

思路二

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        for (int i = 0; i < pow(2,n); ++i) {
            res.push_back((i >> 1) ^ i);  // ^ 是异或的意思
        }
        return res;
    }
};

思路三

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int>res{0};
        for(int b = 0; b < n; b++){
            for(int i = res.size() - 1; i >= 0; i--) // 镜面复制
                res.push_back(res[i]);
            
            int half_size = res.size() >> 1;
            for(int i = 0; i < half_size; i++){
                // 在前面添加新位元
                res[i + half_size] += (1 << b);
                
                // 在后面添加新位元
                // res[i] <<= 1;
                // res[i + half_size] = (res[i + half_size] << 1) + 1;
            }
        }
        return res;
    }
};