企业官网建设流程全解析

LeetCode 89. 格雷编码

题目描述

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

思路：公式法

格雷码与二进制数之间存在转换公式：

对于二进制数 i，其对应的格雷码为 i ^ (i >> 1)

因此，我们只需遍历 i 从 0 到 2^n - 1，依次计算并加入结果列表即可。这样生成的序列天然满足相邻两个数仅有一位不同，且以 0 开头。

Java 实现

classSolution{publicList<Integer>grayCode(intn){List<Integer>res=newArrayList<>();intsize=1<<n;// 2^nfor(inti=0;i<size;i++){res.add(i^(i>>1));}returnres;}}

另一种写法：镜像反射法

classSolution{publicList<Integer>grayCode(intn){List<Integer>res=newArrayList<>();res.add(0);for(inti=0;i<n;i++){intsize=res.size();for(intj=size-1;j>=0;j--){res.add(res.get(j)|(1<<i));}}returnres;}}

复杂度分析

指标 复杂度
时间复杂度 O(2^n)，需要生成 2^n 个数字
空间复杂度 O(1)，不计返回结果所占空间

示例验证

输入：n = 2

· i = 0：0 ^ 0 = 0
· i = 1：1 ^ 0 = 1
· i = 2：2 ^ 1 = 3
· i = 3：3 ^ 1 = 2

输出：[0, 1, 3, 2] ✅
相邻元素 0-1、1-3、3-2 均只有一位不同，且以 0 开头。

关键点

1. 公式 i ^ (i >> 1) 是二进制转格雷码的标准方法。
2. 当 n = 0 时，size = 1，返回 [0]，符合要求。
3. 镜像法从 [0] 开始，每次将已有序列逆序并加上最高位 1，也能得到正确结果。