格雷编码

问题描述

picture 0

解题思路

格雷编码是一种特殊的二进制编码方式，其中相邻的两个数（包括首尾）只有一位二进制位不同。题目要求我们生成一个有效的n位格雷码序列。

解决思路

格雷编码有一个经典的构造方法：反射法（镜像法）

构造规律：

1. 基础情况：当n=1时，格雷码序列为[0, 1]
2. 递推关系：假设我们已经得到了n-1位的格雷码序列，如何构造n位的格雷码？
   • 将n-1位的格雷码序列前面加0，保持原有顺序
   • 将n-1位的格雷码序列反转，然后前面加1
   • 将这两部分拼接起来就是n位的格雷码序列

举例说明：

• n=1: [0, 1]
• n=2:
  • 前半部分（加0）：[00, 01] → [0, 1]
  • 后半部分（加1，反转）：[11, 10] → [3, 2]
  • 合并：[0, 1, 3, 2]
• n=3:
  • 前半部分：[000, 001, 011, 010] → [0, 1, 3, 2]
  • 后半部分：[110, 111, 101, 100] → [6, 7, 5, 4]
  • 合并：[0, 1, 3, 2, 6, 7, 5, 4]

数学公式法：

格雷码还有一个直接的数学公式：G(i) = i ^ (i >> 1)

• 其中^表示异或运算
• i >> 1表示i右移一位（相当于除以2）
• 这个公式可以直接计算第i个格雷码的值

Python代码实现

方法一：反射法（递归/迭代）

def grayCode(n):
    """
    使用反射法构造格雷码序列
    """
    if n == 0:
        return [0]
    
    # 初始化n=1的情况
    result = [0, 1]
    
    # 从2位开始逐步构造到n位
    for i in range(2, n + 1):
        # 当前位数的最高位对应的值（2^(i-1)）
        prefix = 1 << (i - 1)  # 等价于 2^(i-1)
        
        # 将当前序列反转，并在每个数前面加上最高位
        reversed_part = [prefix + x for x in reversed(result)]
        
        # 拼接原序列和新序列
        result.extend(reversed_part)
    
    return result

方法二：数学公式法（推荐）

def grayCode(n):
    """
    使用数学公式 G(i) = i ^ (i >> 1) 直接生成格雷码
    """
    result = []
    for i in range(1 << n):  # 1 << n 等价于 2^n
        gray = i ^ (i >> 1)
        result.append(gray)
    return result

方法三：一行代码实现

def grayCode(n):
    return [i ^ (i >> 1) for i in range(1 << n)]

复杂度分析

• 时间复杂度：O(2^{n)，需要生成2}n个格雷码
• 空间复杂度：O(2^n)，存储结果数组

验证示例

# 测试
print(grayCode(1))  # [0, 1]
print(grayCode(2))  # [0, 1, 3, 2]
print(grayCode(3))  # [0, 1, 3, 2, 6, 7, 5, 4]

总结

格雷码问题的核心在于理解其构造规律。数学公式法G(i) = i ^ (i >> 1)是最简洁高效的解法，它直接利用了格雷码的数学性质，代码简洁且易于理解。反射法虽然直观，但实现相对复杂一些。

在实际面试中，如果能推导出数学公式会给人留下深刻印象，但如果一时想不起来，反射法也是完全可以接受的解决方案。