格雷编码

1. 题目描述

n 位格雷码序列是一个由$2n$个整数组成的序列，其中：

• 每个整数都在范围$[0, 2n - 1]$内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现不超过一次
• 每对相邻整数的二进制表示恰好一位不同，且第一个和最后一个整数的二进制表示恰好一位不同

给你一个整数 n ，返回任一有效的n 位格雷码序列

示例1：

输入：n = 2

输出：[0,1,3,2]

解释：

[0,1,3,2] 的二进制表示是 [00,01,11,10] 。

• 00 和 01 有一位不同
• 01 和 11 有一位不同
• 11 和 10 有一位不同
• 10 和 00 有一位不同

[0,2,3,1]也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01]。

• 00 和 10 有一位不同
• 10 和 11 有一位不同
• 11 和 01 有一位不同
• 01 和 00 有一位不同

示例2：

输入：n = 1

输出：[0,1]

2. 分析

当 n=0 时，格雷码序列为 [0]。

如果我们获取到了$n−1$位的格雷码序列，记为$G_{n−1}$，我们可以使用它构造出$n$位的格雷码序列$G_n$。具体的方法如下：

• 我们将$G_{n−1}$复制一份并翻转，记为$G_{n−1}^T$ ；

• 我们给$G_{n−1}^T$中的每个元素的第$n−1$个二进制位都从 0 变为 1，得到 $(G_{n−1}^T)′$ 。这里最低的二进制位为第 0 个二进制位；

• 我们将$G_{n−1}$ 和 $(G_{n−1}^T )′$进行拼接，得到$G_n$​。

上述方法的正确性也可以通过直观的证明得到：

- 由于 $G_{n−1}$是 $[0,2n−1)$ 的一个排列，那么其中每个元素的第 n−1 个二进制位都是 0。因此，$(G_{n−1}^T)′$就是 $[2 
n−1,2n)$的一个排列，$G_n​ =G_{n−1} +(G _{n−1}^T)′$ 就是 [0,2n) 的一个排列；对于$G_{n−1} 和 $(G_{n−1}^T)′$的内部，每对相邻整数的二进制恰好有一位不同。

- 对于$G_{n−1}$的最后一个数和$(G_{n−1}^T​)′$ 的第一个数，它们仅有第 n−1 个二进制位不同。对于$G_{n−1}$​的第一个数和$(G_{n−1}^T​)′$ 的最后一个数，它们也仅有第 n−1 个二进制位不同。因此$G_n$​ 就是满足要求的 n 位格雷码序列。

3. 代码

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;
        ret.reserve(1 << n);
        ret.push_back(0);
        for (int i = 1; i <= n; i++) {
            int m = ret.size();
            for (int j = m - 1; j >= 0; j--) {
                ret.push_back(ret[j] | (1 << (i - 1)));
            }
        }
        return ret;
    }
};