格雷编码
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
速度
题目描述
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
- 每个整数都在范围
[0, 2n - 1]内（含0和2n - 1） - 第一个整数是
0 - 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n，返回任一有效的 n 位格雷码序列。
示例 1
输入：n = 2
输出：[0,1,3,2]
二进制为 [00,01,11,10]，相邻（含首尾）均仅一位不同；[0,2,3,1] 也是合法答案。
示例 2
输入：n = 1
输出：[0,1]
模拟答题者思考
1. 我先写暴力：用回溯枚举 0..2^n-1 的全排列，检查相邻与首尾是否仅一位不同——能出答案，但阶乘级搜索，n=16 时完全不可行。
2. 重复在哪里？合法的格雷码有固定构造规律：n 位序列总可以看成「n-1 位序列」与它的镜像（每位最高位翻转）首尾相接，且连接处仍只差一位。
3. 反射法：从 result = [0] 出发，对每一位 i，把 result 逆序遍历，把每个数 OR 上 1<<i 后追加到尾部——长度每轮 ×2，且相邻性由归纳保证。
4. 等价公式 gray(i) = i ^ (i >> 1)：按自然序 i 映射即得标准格雷码；实现更短，但「为什么相邻只差一位」不如反射法直观，面试可先讲反射再提公式。
5. 共生成 2^n 个数，每数 O(1) 处理，时间 O(2^n)；输出本身占 O(2^n) 空间。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
result | list<int> | 定义：当前已构造的格雷码前缀，长度始终为 2^k（k 为已处理位数）维护：初始为 [0]，表示 0 位格雷码只有 0更新：每增加一位时，在末尾追加「原序列逆序 + 最高位为 1」的镜像段 |
i | int | 定义：当前要插入的新二进制位所在位置（从低位 0 起） 维护： for i in range(n)，每轮把序列长度翻倍更新：每轮结束后 i += 1；镜像时用掩码 1 << i |
mask | int | 定义：本轮要在旧格雷码上点亮的最高位，值为 1 << i维护：与 result 中每个元素按位 OR，得到镜像半段更新：随 i 每轮重新计算 |
落码步骤
1. result = [0]
2. 对 i = 0 .. n-1：mask = 1 << i，令 result += [x | mask for x in reversed(result)]（C++ 可对前半段逆序追加）
3. 返回 result（长度已为 2^n，首项为 0）
代码实现
class Solution:
def grayCode(self, n: int) -> list[int]:
result = [0]
for i in range(n):
mask = 1 << i
result += [x | mask for x in reversed(result)]
return resultclass Solution {
public:
vector<int> grayCode(int n) {
vector<int> result = {0};
for (int i = 0; i < n; ++i) {
int mask = 1 << i;
int m = result.size();
for (int j = m - 1; j >= 0; --j) {
result.push_back(result[j] | mask);
}
}
return result;
}
};
// 时间 O(2^n)，空间 O(2^n)复杂度分析
时间复杂度
O(2^n)
空间复杂度
O(2^n)（输出序列，不计则 O(1)）
常见坑
镜像时忘记逆序追加：若按正序 OR mask，相邻项可能差多位，首尾也不满足格雷性质。
把「自然二进制序」0,1,2,… 直接当作答案——例如 n=2 时 [0,1,2,3] 中 1 与 2 的二进制差两位。
回溯写法未用 used 位集去重：同一数字出现两次会立即违反题意。
必测边界 Case
Case 1：n = 1
→ [0, 1]（仅两位，反射一轮后结束）
Case 2：n = 2
→ [0, 1, 3, 2]（与示例一致；[0,2,3,1] 等其它反射起点也合法）
Case 3：首尾相邻
n = 2 时末项 2（10）与首项 0（00）仅最低位不同，需单独心算验证，不能只检查中间相邻对