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:

1
2
3
4
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.

思路

这个格雷码啊……必须要找到一个合适的组合满足题目要求才行。

如果n=2, 必须是[0,1,3,2] ；如果n=3, 必须是[0,1,3,2,6,7,5,4]；究其原因，就是因为它的解法比较固sha定bi。

我找了半天规律，发现如果生成的格雷码序列不符合题意，就根本没有规律可言……

在这道题中，格雷码分布的规律是[0,1]是对称的。

00 01 | 11 10 当中，第一位是镜像对称的，

000 001 011 010 | 110 111 101 100， 第一，第二位都是镜像对称的。 从而可以得到规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        if (n < 0) return result;
        else {
            result.push_back(0);
            int count = 0;
            while(count < n){
                int curlen = result.size();
                for (int i = curlen - 1; i >= 0; i--){
                    int tmp = result[i] + ( 1 << count );
                    result.push_back(tmp);
                }
                count++;
            }
        }
        return result;
    }
};