LeetCode 89. 格雷编码
题目描述
✅ 89. 格雷编码
题意分析
返回一个从 0 开始的整数序列，恰好包含所有
n位非负整数且不重复。相邻两个数的二进制表示必须恰好一位不同，最后一个数和第一个数也要满足这个条件；返回任意一种有效顺序即可。
解法：二进制转格雷码公式
核心思路
[!blue]
普通二进制加一时，末尾连续的 1 和它前面的 0 会一起翻转。希望把这一整段变化压成一位变化，可以让新数的每一位等于原数相邻两位的异或：整段内部的两位同时翻转，异或结果不变；只有翻转段与未翻转段的交界处会改变。这就得到公式
g(i) = i ^ (i >> 1)。具体来说，若
i的末尾有t个连续的 1，加一只会翻转第 0 到第t位。在格雷码中，第t位对应的一对原始位只有一位翻转；更低位置对应的两位都翻转，更高位置都不变。因此g(i)和g(i + 1)恰好只在第t位不同。还需保证不重复：格雷码的最高位就是原数最高位，知道原数较高一位后，就能用当前格雷位逐位还原下一位。因此转换可以唯一还原，枚举所有
i会得到全部 $2^n$ 个不同的n位数。首项
g(0) = 0；最后的i = 2^n - 1在低n位全为 1，和自身右移一位异或后只剩最高位 1，故末项为 $2^{n-1}$，与首项也恰好相差一位。
解题步骤
- 计算序列长度
size = 1 << n，并一次性申请结果空间。- 从
i = 0枚举到size - 1。- 对每个
i计算i ^ (i >> 1)，依次写入结果。- 返回结果；公式已同时保证起点、相邻关系、不重复和首尾闭合，无需额外校验或调整顺序。
代码实现
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)$。
关键点总结
[!green]
- 相邻位异或会消去进位过程中整段翻转的内部变化，只保留边界上的一位变化。
- 能从格雷码唯一还原原数，保证所有结果不重复，无需集合判重。
- 正确性同时覆盖数值范围、从 0 开始、不重复、相邻差一位和首尾差一位。
易错点总结
[!yellow]
- 必须使用异或
^，按位或|不能消去同时翻转的变化。- 枚举范围是 $[0,2^n)$，不能把
2^n也加入结果。- 相邻条件包括最后一项到第一项，不能只证明线性顺序中相邻的数。
- 题目保证
1 <= n <= 16，这里的1 << n和每个结果都在整数范围内；接口返回整数列表，不是二进制字符串。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1238. 循环码排列 | 中等 | 原题要求从指定数开始的循环格雷排列，可用本题格雷码与起点异或获得。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！