Medium

题目描述

n 位格雷码序列是一个由 2^n 个整数组成的序列，其中：

  • 每个整数都在范围 [0, 2^n - 1] 内（含 0 和 2^n - 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

解题思路

格雷编码的构造可以通过以下几种方法实现：

方法一：递归构造法（推荐）

观察格雷码的构造规律：

  • 1位格雷码：[0, 1]
  • 2位格雷码：[0, 1, 3, 2]，即在1位基础上，前半部分保持不变，后半部分为前半部分的逆序并在最高位加1
  • 3位格雷码：[0, 1, 3, 2, 6, 7, 5, 4]，同样遵循此规律

具体构造过程：

  1. 对于 n=1，返回 [0, 1]
  2. 对于 n>1，先构造 n-1 位的格雷码
  3. 将 n-1 位格雷码的逆序添加到结果末尾，并在每个数的第 n 位（从右数）设置为1

方法二：公式法

可以直接使用格雷码的数学公式：第 i 个格雷码 = i ^ (i » 1)，其中 ^ 表示异或运算。

方法三：回溯法

通过深度优先搜索，每次尝试翻转一位，确保生成的序列满足格雷码的性质。

递归构造法思路清晰，实现简单，是最常用的方法。

代码实现

class Solution {
public:
    vector<int> grayCode(int n) {
        if (n == 1) {
            return {0, 1};
        }
        
        vector<int> prev = grayCode(n - 1);
        vector<int> result = prev;
        
        int highBit = 1 << (n - 1);
        for (int i = prev.size() - 1; i >= 0; i--) {
            result.push_back(prev[i] + highBit);
        }
        
        return result;
    }
};

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 1:
            return [0, 1]
        
        prev = self.grayCode(n - 1)
        result = prev[:]
        
        high_bit = 1 << (n - 1)
        for i in range(len(prev) - 1, -1, -1):
            result.append(prev[i] + high_bit)
        
        return result

public class Solution {
    public IList<int> GrayCode(int n) {
        if (n == 1) {
            return new List<int> {0, 1};
        }
        
        IList<int> prev = GrayCode(n - 1);
        List<int> result = new List<int>(prev);
        
        int highBit = 1 << (n - 1);
        for (int i = prev.Count - 1; i >= 0; i--) {
            result.Add(prev[i] + highBit);
        }
        
        return result;
    }
}

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
    const result = [0];
    
    for (let i = 0; i < n; i++) {
        const size = result.length;
        for (let j = size - 1; j >= 0; j--) {
            result.push(result[j] | (1 << i));
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型递归构造法
时间复杂度O(2^n)
空间复杂度O(2^n)

说明：

  • 时间复杂度：需要生成 2^n 个格雷码，每个码的生成时间为 O(1)
  • 空间复杂度：需要存储 2^n 个整数，递归栈深度为 O(n)，总空间复杂度为 O(2^n)

相关题目