LeetCode 89. 格雷编码

2026-03-25 HGNULB 约 5 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 89. 格雷编码

题意分析

要构造一个长度为 $2^n$ 的整数序列，它必须同时满足四件事：第一项是 0；每一项都在 $[0, 2^n - 1]$ 范围内；$2^n$ 个数互不重复，也就是恰好把这个范围排满一遍；相邻两项的二进制表示只有一位不同，并且首尾两项之间也要只差一位。答案不唯一，任意一个合法序列都算对。

「排满 $[0, 2^n-1]$ 且相邻只差一位」翻译过来就是：在 $n$ 维超立方体上找一条经过每个顶点恰好一次的回路。首尾也要相差一位这个附加条件，把「路径」升级成了「回路」，很多手写实现之所以在 n = 2 上过不了，就是漏看了这一条。

输出规模是 $2^n$，任何解法都至少要这么多时间和空间，因此不存在「比 $O(2^n)$ 更快」的目标，唯一要争取的是每生成一个数只花常数代价，不要在里面套搜索或去重。$n$ 的上界是 16，$2^{16} = 65536$，规模很小，但这不改变算法该有的形态。

「答案不唯一」这句话是重要的松弛信号：不需要按字典序或任何特定顺序输出，只要满足约束即可，所以可以自由选择一种最好构造的方案。

边界要盯住：n = 1 时答案是 [0, 1]，首尾 0 与 1 也恰好差一位；题目保证 $n \ge 1$，但实现上如果 n = 0 也应自然得到 [0]；返回的是十进制整数列表，不是二进制字符串。

解法：二进制转格雷码公式

核心思路

第 $i$ 个格雷码可以直接由二进制数 $i$ 得到：
\[g(i)=i\oplus(i\gg 1)\]
右移让原二进制的第 $k+1$ 位与第 $k$ 位对齐，异或后，格雷码第 $k$ 位就表示原数相邻两位是否不同。枚举 $i=0,1,\ldots,2^n-1$ 并套用公式，便能按顺序生成完整答案，无需回溯、判重或维护上一项。

为什么相邻结果只差一位？ 设 $i$ 的末尾有 $t$ 个连续的 1，那么 i + 1 会把这 $t$ 个 1 变成 0，并把它们前面的 0 变成 1。因此
\[x=i\oplus(i+1)=2^{t+1}-1\]
即 $x$ 的低 $t+1$ 位全为 1。两项格雷码的差异为
\[g(i)\oplus g(i+1)=x\oplus(x\gg 1)=2^t\]
结果只有第 $t$ 位是 1，所以相邻格雷码恰好变化一位。这是公式解最关键的证明。

为什么没有重复？ 若 $g(a)=g(b)$，令 $x=a\oplus b$，可得 $x\oplus(x\gg 1)=0$，即 $x=x\gg 1$。有限位非负整数只有 $x=0$ 能满足，因此 $a=b$。输入区间有 $2^n$ 个数，输出又都在 $n$ 位范围内，所以它们恰好覆盖 $[0,2^n-1]$。

为什么首尾也只差一位？ 首项 $g(0)=0$；末项对应 $i=2^n-1$，其二进制是 $n$ 个 1，右移后是 $n-1$ 个 1，异或结果为 $2^{n-1}$。它与 0 仅最高位不同，序列因此闭合成环。

解题步骤

计算序列长度 size = 1 << n，并一次性申请结果空间。

从 i = 0 枚举到 size - 1。

对每个 i 计算 i ^ (i >> 1)，依次写入结果。

返回结果；公式已同时保证起点、相邻关系、不重复和首尾闭合，无需额外校验或调整顺序。

以 n = 3 为例：

i 二进制 i >> 1 格雷码

0 000 000 000

1 001 000 001

2 010 001 011

3 011 001 010

4 100 010 110

5 101 010 111

6 110 011 101

7 111 011 100

得到 [0, 1, 3, 2, 6, 7, 5, 4]。相邻项只变一位，末项 100 与首项 000 也只变一位。

`i`	二进制	`i >> 1`	格雷码
0	`000`	`000`	`000`
1	`001`	`000`	`001`
2	`010`	`001`	`011`
3	`011`	`001`	`010`
4	`100`	`010`	`110`
5	`101`	`010`	`111`
6	`110`	`011`	`101`
7	`111`	`011`	`100`

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> grayCode(int n) {
        int size = 1 << n;
        List<Integer> ans = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            ans.add(i ^ (i >> 1));
        }
        return ans;
    }
}

func grayCode(n int) []int {
    ans := make([]int, 1<<n)
    for i := 0; i < len(ans); i++ {
        ans[i] = i ^ (i >> 1)
    }
    return ans
}

复杂度分析

时间复杂度：$O(2^n)$。共生成 $2^n$ 个数，每个数只做一次移位和异或；这已经达到输出规模的下界。

空间复杂度：$O(2^n)$，用于保存返回结果；除返回值外只使用常数个变量，额外空间为 $O(1)$。

关键点总结

公式 i ^ (i >> 1) 是二进制到格雷码的标准转换：异或比较相邻二进制位。

相邻性证明抓住“加一会翻转末尾连续的 1”：差异掩码形如低位连续 1，再与自身右移异或后只剩一位。

正确性不能只证明相邻项，还要覆盖首项为 0、结果不重复以及首尾只差一位。

闭式构造每项 $O(1)$，比回溯或用集合判重更直接，也达到了输出规模决定的最优复杂度。

易错点总结

运算优先级写错：应写 i ^ (i >> 1)。加括号能直接表达先右移再异或，避免把公式抄错。

少算或多算一个元素：循环范围必须是 $[0,2^n)$；若写成 i <= 1 << n，会多生成一个越界值。

误以为普通二进制顺序就是答案：n = 2 时 [0, 1, 2, 3] 中 01 到 10 变化两位，不满足要求。

只检查线性相邻项，漏掉首尾条件：题目要求形成环。公式末项为 $2^{n-1}$，必须明确它与首项 0 只差最高位。

把结果返回成二进制字符串：二进制只用于解释位变化，接口要求返回十进制整数列表。

相似题目

题目	难度	考察点
78. 子集	中等	同样可用「已有解镜像扩展一位」的迭代构造，但对相邻元素的关系无任何要求
338. 比特位计数	简单	也是按位递推填满 $[0, n]$，转移用 `i >> 1` 或 `i & (i-1)` 复用子结果
191. 位1的个数	简单	单个数的位操作基本功，可用来练 `n & (n-1)` 消最低位 1 的技巧
46. 全排列	中等	必须真正回溯枚举，不存在本题这种闭式构造，是构造法与搜索法的对照组
784. 字母大小写全排列	中等	每个字母两种取值，同样可用「结果集翻倍」的迭代扩展，但无相邻约束
60. 排列序列	困难	要求直接算出第 k 个排列而不是全部列出，靠阶乘进制逐位定位
136. 只出现一次的数字	简单	利用异或的自反性求唯一元素，是位运算「配对抵消」思路的代表
260. 只出现一次的数字 III	中等	在 136 基础上用最低位 1 把元素分成两组，分组思路与本题的最高位划分呼应