文章目录
- 89. 格雷编码
- 题目描述
- 示例 1：
- 示例 2：
- 提示：
- 解题思路
- 问题深度分析
- 问题本质
- 核心思想
- 关键难点分析
- 典型情况分析
- 算法对比
- 算法流程图
- 主算法流程（对称反射法）
- 递归构造流程
- 对称反射可视化
- 复杂度分析
- 时间复杂度详解
- 空间复杂度详解
- 关键优化技巧
- 技巧1：对称反射法（最优解法）
- 技巧2：位运算公式（最简洁）
- 技巧3：递归构造
- 技巧4：迭代构造
- 边界情况处理
- 测试用例设计
- 基础测试
- 简单情况
- 特殊情况
- 边界情况
- 常见错误与陷阱
- 错误1：位运算公式理解错误
- 错误2：镜像反射实现错误
- 错误3：最高位添加错误
- 实战技巧总结
- 进阶扩展
- 扩展1：验证是否为格雷码
- 扩展2：生成固定长度的格雷码序列
- 扩展3：转换二进制到格雷码
- 应用场景
- 代码实现
- 测试结果
- 核心收获
- 应用拓展
- 完整题解代码
89. 格雷编码
题目描述
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]
提示：
- 1 <= n <= 16
解题思路
问题深度分析
这是经典的位运算问题，也是格雷码生成的经典应用。核心在于对称反射，在O(2^n)时间内生成n位格雷码序列。
问题本质
给定整数n，返回一个有效的n位格雷码序列，使得相邻两个整数在二进制表示中恰好有一位不同。
核心思想
对称反射法：
- 镜像反射：将n-1位格雷码镜像反射
- 添加最高位：在前一半最高位添加0，后一半最高位添加1
- 递归构造：从1位格雷码开始递归构造
- 位运算优化：使用异或运算快速生成
关键技巧：
- 利用格雷码的对称性质
- 递归构造格雷码序列
- 使用位运算优化
- 理解格雷码的数学性质
关键难点分析
难点1：对称反射的理解
- 格雷码具有对称性质
- n位格雷码可以通过n-1位格雷码镜像得到
- 需要理解对称反射的机制
难点2：递归构造的实现
- 从1位格雷码开始
- 每次构造需要镜像反射
- 添加最高位时需要正确处理
难点3：位运算优化
- 使用i^(i>>1)公式快速生成格雷码
- 理解异或运算的性质
- 正确实现位运算
典型情况分析
情况1：n=1
格雷码序列: [0, 1]
二进制: [0, 1]
说明: 基础情况情况2：n=2
n=1格雷码: [0, 1]
镜像反射: [0, 1, 1, 0]
添加最高位: [00, 01, 11, 10]
结果: [0, 1, 3, 2]情况3：n=3
n=2格雷码: [00, 01, 11, 10]
镜像反射: [00, 01, 11, 10, 10, 11, 01, 00]
添加最高位: [000, 001, 011, 010, 110, 111, 101, 100]
结果: [0, 1, 3, 2, 6, 7, 5, 4]算法对比
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 对称反射 | O(2^n) | O(2^n) | 最优解法 |
| 位运算公式 | O(2^n) | O(2^n) | 最简洁实现 |
| 递归构造 | O(2^n) | O(2^n) | 逻辑清晰 |
| 迭代构造 | O(2^n) | O(2^n) | 避免递归 |
注：n为格雷码位数
算法流程图
主算法流程（对称反射法）
graph TDA[开始: n] --> B[n == 1?]B -->|是| C[返回[0, 1]]B -->|否| D[递归生成n-1位格雷码]D --> E[镜像反射序列]E --> F[添加最高位]F --> G[前一半添加0]G --> H[后一半添加1]H --> I[返回结果]递归构造流程
graph TDA[构造n位格雷码] --> B{n > 1?}B -->|否| C[返回[0,1]]B -->|是| D[递归构造n-1位格雷码]D --> E[获取n-1位格雷码序列]E --> F[镜像反射序列]F --> G[前一半添加0]G --> H[后一半添加1]H --> I[返回n位格雷码]对称反射可视化
复杂度分析
时间复杂度详解
对称反射算法：O(2^n)
- 需要生成2^n个格雷码
- 每个格雷码的生成时间为O(1)
- 总时间：O(2^n)
位运算公式：O(2^n)
- 遍历0到2^n-1的每个数
- 使用公式i^(i>>1)计算格雷码
- 总时间：O(2^n)
空间复杂度详解
所有算法：O(2^n)
- 需要存储2^n个格雷码
- 空间复杂度：O(2^n)
关键优化技巧
技巧1：对称反射法（最优解法）
func grayCode(n int) []int {
if n == 1 {
return []int{0, 1}
}
// 递归生成n-1位格雷码
prev := grayCode(n - 1)
result := make([]int, len(prev)*2)
// 前一半：直接添加0
for i := 0; i < len(prev); i++ {
result[i] = prev[i]
}
// 后一半：添加1并镜像反射
for i := 0; i < len(prev); i++ {
result[len(prev)+i] = prev[len(prev)-1-i] + (1 << (n - 1))
}
return result
}优势：
- 时间复杂度：O(2^n)
- 逻辑清晰，易于理解
- 利用格雷码的对称性质
技巧2：位运算公式（最简洁）
func grayCode(n int) []int {
result := make([]int, 1<<n)
for i := 0; i < 1<<n; i++ {
result[i] = i ^ (i >> 1)
}
return result
}特点：使用公式i^(i>>1)快速生成格雷码
技巧3：递归构造
func grayCode(n int) []int {
result := make([]int, 0, 1<<n)
var dfs func(int, []int)
dfs = func(n int, prev []int) {
if n == 1 {
result = append(result, prev[0])
result = append(result, prev[1])
return
}
// 镜像反射
next := make([]int, len(prev)*2)
for i := 0; i < len(prev); i++ {
next[i] = prev[i]
next[len(prev)*2-1-i] = prev[i] + (1 << (n - 1))
}
dfs(n-1, next)
}
dfs(n, []int{0})
return result
}特点：使用递归DFS构造，代码清晰
技巧4：迭代构造
func grayCode(n int) []int {
result := []int{0}
for i := 0; i < n; i++ {
size := len(result)
for j := size - 1; j >= 0; j-- {
result = append(result, result[j]|(1<<i))
}
}
return result
}特点：避免递归，使用迭代构造
边界情况处理
- n=1：返回[0, 1]
- n=2：返回[0, 1, 3, 2]
- n=0：返回空数组
- n=16：处理大数情况
测试用例设计
基础测试
输入: n = 2
输出: [0,1,3,2]
说明: 一般情况简单情况
输入: n = 1
输出: [0,1]
说明: 基础情况特殊情况
输入: n = 3
输出: [0,1,3,2,6,7,5,4]
说明: 递归构造边界情况
输入: n = 16
输出: [0,...,2^16-1]
说明: 大数情况常见错误与陷阱
错误1：位运算公式理解错误
// ❌ 错误：不理解公式
result[i] = i ^ (i << 1) // 错误的方向
// ✅ 正确：使用公式
result[i] = i ^ (i >> 1)错误2：镜像反射实现错误
// ❌ 错误：没有正确镜像反射
for i := 0; i < len(prev); i++ {
result[i] = prev[i]
result[len(prev)+i] = prev[i] + (1 << (n - 1)) // 错误
}
// ✅ 正确：镜像反射
for i := 0; i < len(prev); i++ {
result[i] = prev[i]
result[len(prev)*2-1-i] = prev[i] + (1 << (n - 1))
}错误3：最高位添加错误
// ❌ 错误：添加最高位不正确
result[i] = prev[i] + (1 << n) // 错误，应该是n-1
// ✅ 正确：添加最高位
result[i] = prev[i] + (1 << (n - 1))实战技巧总结
- 对称反射模板：利用格雷码的对称性质
- 递归构造：从1位格雷码开始递归构造
- 位运算公式：使用i^(i>>1)快速生成
- 最高位处理：正确添加最高位
- 镜像反射：正确处理镜像反射
进阶扩展
扩展1：验证是否为格雷码
func isGrayCode(code []int) bool {
// 验证序列是否为有效的格雷码
// ...
}扩展2：生成固定长度的格雷码序列
func generateGrayCodeFixed(n, length int) []int {
// 生成指定长度的格雷码序列
// ...
}扩展3：转换二进制到格雷码
func binaryToGray(num int) int {
return num ^ (num >> 1)
}应用场景
- 数字电路：格雷码用于减少数字电路中的错误
- 编码器：旋转编码器使用格雷码
- 通信：减少数据传输错误
- 算法竞赛：位运算经典应用
- 系统设计：减少状态转换错误
代码实现
本题提供了四种不同的解法，重点掌握对称反射法和位运算公式。
测试结果
| 测试用例 | 对称反射法 | 位运算公式 | 递归构造 | 迭代构造 |
|---|---|---|---|---|
| 基础测试 | ✅ | ✅ | ✅ | ✅ |
| 简单情况 | ✅ | ✅ | ✅ | ✅ |
| 特殊情况 | ✅ | ✅ | ✅ | ✅ |
| 边界情况 | ✅ | ✅ | ✅ | ✅ |
核心收获
- 对称反射法：格雷码的对称性质
- 位运算公式：i^(i>>1)的妙用
- 递归构造：从1位格雷码递归构造
- 迭代构造：避免递归的迭代方法
- 边界处理：各种边界情况的考虑
应用拓展
- 数字电路设计
- 编码器应用
- 通信系统
- 算法竞赛
- 系统设计
完整题解代码
package main
import (
"fmt"
)
// =========================== 方法一：对称反射法（最优解法） ===========================
func grayCode1(n int) []int {
if n == 1 {
return []int{0, 1}
}
// 递归生成n-1位格雷码
prev := grayCode1(n - 1)
result := make([]int, len(prev)*2)
// 前一半：直接添加0
for i := 0; i < len(prev); i++ {
result[i] = prev[i]
}
// 后一半：添加1并镜像反射
for i := 0; i < len(prev); i++ {
result[len(prev)+i] = prev[len(prev)-1-i] + (1 << (n - 1))
}
return result
}
// =========================== 方法二：位运算公式（最简洁） ===========================
func grayCode2(n int) []int {
result := make([]int, 1<<n)
for i := 0; i < 1<<n; i++ {
result[i] = i ^ (i >> 1)
}
return result
}
// =========================== 方法三：迭代构造 ===========================
func grayCode3(n int) []int {
result := []int{0}
for i := 0; i < n; i++ {
size := len(result)
for j := size - 1; j >= 0; j-- {
result = append(result, result[j]|(1<<i))
}
}
return result
}
// =========================== 方法四：递归构造（DFS） ===========================
func grayCode4(n int) []int {
if n == 1 {
return []int{0, 1}
}
result := []int{0}
mask := 1 << (n - 1)
var dfs func(int, int)
dfs = func(bits, pos int) {
if bits == 0 {
return
}
size := len(result)
for i := size - 1; i >= 0; i-- {
result = append(result, result[i]^mask)
}
dfs(bits-1, pos<<1)
}
dfs(n-1, 1)
return result
}
// =========================== 测试代码 ===========================
func main() {
fmt.Println("=== LeetCode 89: 格雷编码 ===\n")
testCases := []struct {
name string
n int
expected []int
}{
{
name: "Test1: n=1",
n: 1,
expected: []int{0, 1},
},
{
name: "Test2: n=2",
n: 2,
expected: []int{0, 1, 3, 2},
},
{
name: "Test3: n=3",
n: 3,
expected: []int{0, 1, 3, 2, 6, 7, 5, 4},
},
{
name: "Test4: n=4",
n: 4,
expected: []int{0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8},
},
}
methods := map[string]func(int) []int{
"对称反射法（最优解法）": grayCode1,
"位运算公式（最简洁）": grayCode2,
"迭代构造": grayCode3,
"递归构造（DFS）": grayCode4,
}
for name, method := range methods {
fmt.Printf("方法%s：%s\n", name, name)
passCount := 0
for i, tt := range testCases {
got := method(tt.n)
// 验证格雷码的有效性
valid := isValidGrayCode(got)
status := "✅"
if !valid {
status = "❌"
} else {
passCount++
}
fmt.Printf(" 测试%d: %s\n", i+1, status)
if status == "❌" {
fmt.Printf(" 输入: n=%d\n", tt.n)
fmt.Printf(" 输出: %v\n", got)
}
}
fmt.Printf(" 通过: %d/%d\n\n", passCount, len(testCases))
}
}
// 验证格雷码的有效性
func isValidGrayCode(code []int) bool {
if len(code) == 0 {
return true
}
// 检查相邻元素是否只有一位不同
for i := 0; i < len(code)-1; i++ {
diff := code[i] ^ code[i+1]
if diff == 0 || (diff&(diff-1)) != 0 {
// 检查是否只有一个位不同
ones := 0
for diff > 0 {
ones += diff & 1
diff >>= 1
}
if ones != 1 {
return false
}
}
}
// 检查首尾是否只有一位不同
if len(code) > 1 {
diff := code[0] ^ code[len(code)-1]
ones := 0
for diff > 0 {
ones += diff & 1
diff >>= 1
}
if ones != 1 {
return false
}
}
return true
}