89. Gray Code

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.

Example 1:

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

---

格雷码是这样一种编码：第一个数为0，后面每个数和前一个数在二进制位上只相差一位。现在给定二进制编码为n位，要求输出一串格雷码。
在不了解格雷码的情况下，可以单纯根据上面格雷码的定义来列出这一串格雷码，我们需要尝试依次翻转n位中的每一位，如果翻转之后得到的编码之前没有出现过，则翻转成功，接着进入下一次尝试，直到产生所有格雷码。
假设一个二进制数为x，则翻转其第i位之后的二进制数为(x&(~(1 << i))) | (~x)&(1 << i)，还是有点复杂的。
这种思路可以用递归的方法实现，完整代码如下：

class Solution {
public:
    void work(vector<int>& ans, unordered_set<int>& codes, int gray, int n)
    {
        for (int i = 0; i < n; ++i) {
            int new_gray = (gray & (~(1 << i))) | (~gray) & (1 << i); // flip i-th bit
            if (codes.find(new_gray) == codes.end()) {
                codes.insert(new_gray);
                ans.push_back(new_gray);
                work(ans, codes, new_gray, n);
                break;
            }
        }
    }
    vector<int> grayCode(int n)
    {
        vector<int> ans = { 0 };
        if (n == 0)
            return ans;
        unordered_set<int> codes = { 0 };
        work(ans, codes, 0, n);
        return ans;
    }
};

本代码提交AC，用时6MS。
查看格雷码的维基百科，有好多种方法都可以生成格雷码序列，其中一种很有意思，可以根据二进制长度为n-1的格雷码序列生成二进制长度为n的格雷码序列，如下图所示，这种方法叫做镜射排列。

仔细观察会发现，n长的格雷码序列的前一半序列和n-1长的格雷码序列，在十进制数上是完全一样的，二进制数上也只是多了一个前导零；而后半序列是n-1长的格雷码序列镜面对称之后，加上一位前导1得到的。所以很容易可以写出镜射排列的代码：

class Solution {
public:
    vector<int> grayCode(int n)
    {
        vector<int> ans = { 0 };
        if (n == 0)
            return ans;
        ans.push_back(1);
        for (int i = 2; i <= n; ++i) {
            int sz = ans.size();
            while (sz–) {
                ans.push_back(ans[sz] | (1 << (i – 1)));
            }
        }
        return ans;
    }
};

本代码提交AC，用时3MS。