题目描述

格雷码是一个二进制数系统，满足相邻两个数只有一位不同。
给定一个非负整数 $n$，表示格雷码的位数，请输出一个合法的格雷码序列。
格雷码序列必须以0开始。

例如，给定 $n=2$，返回 [0, 1, 3, 2]。它表示的格雷码序列是：

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

注意：对于一个给定的 $n$，格雷码序列并不唯一。例如 [0, 2, 3, 1] 也是一个合法的格雷码序列。

算法

(构造) $O(2^n)$

我们可以先打表找规律，随便找出一种格雷码的构造方法即可。
我们可以递归构造：

1. 先构造 $n=1$，即只有一位的格雷码序列：[0, 1]；
2. 假设我们已经构造好了 $n=k$时的格雷码序列 $S_k$，我们可以利用它来构造 $S_{k+1}$：
   (1) $S_{k+1}$的前一半：将 $S_k$ 中的每个数开头补上1；
   (2) $S_{k+1}$的后一半，将 $S_k$ 变成逆序，然后在每个数开头补上0；

时间复杂度分析：对于给定的 $n$，计算量是 $2(1 + 2 + 4 + … + 2^{n-1}) = 2^{n+1}-2$，所以时间复杂度是 $O(2^n)$。

C++ 代码

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        res.push_back(0);
        int t = 1;
        while (n -- )
        {
            vector<int> newRes;
            for (int i = 0; i < res.size(); i ++ )
                newRes.push_back(res[i]);
            for (int i = res.size() - 1; i >= 0; i -- )
                newRes.push_back(t + res[i]);
            res = newRes;
            t *= 2;
        }
        return res;
    }
};