LeetCode 89. 格雷编码

Categories:

题目描述
思路分析
1. 解法一：公式法（推荐）
相似题目

题目描述

✅ 89. 格雷编码

思路分析

解法一：公式法（推荐）

核心思路：

第 i 个格雷码为 i ^ (i >> 1)。

直接枚举 0..2^n-1 生成序列。

相邻两数只会有一位不同。

复杂度分析：

时间复杂度：O(2^n)，生成全部格雷码。

空间复杂度：O(2^n)，存储结果序列。

class Solution {
    public List<Integer> grayCode(int n) {
        int size = 1 << n;
        List<Integer> res = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            // 公式 i ^ (i >> 1)
            res.add(i ^ (i >> 1));
        }

        return res;
    }
}

func grayCode(n int) []int {
	size := 1 << n
	res := make([]int, 0, size)

	for i := 0; i < size; i++ {
		// 公式 i ^ (i >> 1)
		res = append(res, i^(i>>1))
	}

	return res
}

相似题目

题目	难度	考察点
1238. 循环码排列	中等	格雷码
89. 格雷编码	中等	位运算
191. 位 1 的个数	简单	位运算
231. 2 的幂	简单	位运算
268. 丢失的数字	简单	位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/68972917