题目描述

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。

格雷编码序列必须以 0 开头。

样例

示例 1:
输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。

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

示例 2:
输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
     给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
     因此，当 n = 0 时，其格雷编码序列为 [0]。

算法1

(BFS) $O(n * 2^n)$

这题有很多奇技淫巧貌似，我想不出，写个BFS不过分吧hh;
BFS比较简单，用一个数组或者哈希表记录是否访问过，然后每次检查哪一位可以变动，能变就变，然后所有方案就枚举出来了。

时间复杂度

共$O(2^n)$个方案，每次枚举最多$O(n)$，故总时间复杂度$O(n * 2^n)$

参考文献

C++ 代码

class Solution {
public:
    vector<int> grayCode(int n) {
        if (n < 0) return {};
        vector<bool> st(1 << n);
        queue<int> Q; Q.push(0); st[0] = true; 
        vector<int> res;

        while (Q.size()){
            int num = Q.front(); Q.pop(); res.push_back(num);

            for (int i = 0; i < n; ++i){
                if (!st[num ^ (1 << i)]){
                    Q.push(num ^ (1 << i));
                    st[num ^ (1 << i)] = true;
                    break;
                }
            }
        }

        return res;
    }
};

算法2

(镜面反射法?) $O(2^n)$

奇技淫巧，详见参考文献图片。

时间复杂度

时间复杂度是方案数$O(2^n)$

参考文献

https://leetcode-cn.com/problems/gray-code/solution/gray-code-jing-xiang-fan-she-fa-by-jyd/

C++ 代码

class Solution {
public:
    vector<int> grayCode(int n) {
        if (n < 0) return {};
        vector<int> res; res.push_back(0);

        for (int i = 0; i < n; ++i){
            int size = res.size();
            for (int j = size - 1; j >= 0; --j)
                res.push_back(res[j] | (1 << i));
        }

        return res;
    }
};