What is the Gray Code sequence?

Gray Code is a binary numeral system where two successive values differ in only one bit. It is used in various applications, such as error correction and digital communication.

How can Gray Code be efficiently generated?

Gray Code can be efficiently generated using backtracking with pruning, bit manipulation, or iterative construction methods.

What is the backtracking approach in Gray Code generation?

The backtracking approach explores all possible sequences, pruning the search space by ensuring only valid transitions between consecutive numbers, which differ by exactly one bit.

Why is bit manipulation important for solving the Gray Code problem?

Bit manipulation allows for efficient conversion between binary numbers and their Gray Code equivalents, utilizing XOR and bit shifts to achieve the desired sequence.

What is the time complexity of generating Gray Code?

The time complexity is O(2^n) when using backtracking or iterative construction methods, as the number of valid sequences grows exponentially with n.

#89

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

格雷编码

n 位格雷码序列是一个由 2 n 个整数组成的序列，其中：每个整数都在范围 [0, 2 n - 1] 内（含 0 和 2 n - 1 ）第一个整数是 0 一个整数在序列中出现不超过一次每对相邻整数的二进制表示恰好一位不同，且第一个和最后一个整数的二进制表示恰好一位不同给…

数学回溯位运算

题目描述

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

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

lightbulb

解题思路

方法一：二进制码转格雷码

格雷码是我们在工程中常会遇到的一种编码方式，它的基本的特点就是任意两个相邻的代码只有一位二进制数不同。

二进制码转换成二进制格雷码，其法则是保留二进制码的最高位作为格雷码的最高位，而次高位格雷码为二进制码的高位与次高位相异或，而格雷码其余各位与次高位的求法相类似。

假设某个二进制数表示为 $B_{n-1}B_{n-2}...B_2B_1B_0$ ，其格雷码表示为 $G_{n-1}G_{n-2}...G_2G_1G_0$ 。最高位保留，所以 $G_{n-1} = B_{n-1}$ ；而其它各位 $G_i = B_{i+1} \oplus B_{i}$ ，其中 $i=0,1,2..,n-2$ 。

因此，对于一个整数 $x$ ，我们可以用函数 $gray(x)$ 得到其格雷码：

int gray(x) {
    return x ^ (x >> 1);
}

我们直接将 $[0,..2^n - 1]$ 这些整数映射成对应的格雷码，即可得到答案数组。

时间复杂度 $O(2^n)$ ，其中 $n$ 为题目给定的整数。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [i ^ (i >> 1) for i in range(1 << n)]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to implement backtracking with pruning efficiently.
question_mark
Familiarity with bit manipulation techniques, especially XOR and bit shifting.
question_mark
Knowledge of iterative methods for constructing sequences.

warning

常见陷阱

外企场景

error
Failing to ensure the difference between consecutive numbers is exactly one bit.
error
Not optimizing the backtracking algorithm to prune unnecessary paths.
error
Incorrect handling of bit manipulation, especially when constructing Gray Code from binary numbers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generating Gray Code for larger n values (n > 10).
arrow_right_alt
Implementing Gray Code using dynamic programming.
arrow_right_alt
Optimizing for space complexity while maintaining correctness.

help

常见问题

外企场景

继续练习

#996 平方数组的数目 #90 子集 II #78 子集