89. 格雷编码

🟠 🔖 位运算 数学 回溯 🔗 力扣open in new window LeetCodeopen in new window

题目

An n-bit gray code sequence is a sequence of 2n integers where:

Every integer is in the inclusive range [0, 2n - 1],
The first integer is 0,
An integer appears no more than once in the sequence,
The binary representation of every pair of adjacent integers differs by exactly one bit , and
The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any validn-bit gray code sequence.

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
0 0 and 0 1 differ by one bit
0 1 and 1 1 differ by one bit
1 1 and 1 0 differ by one bit
1 0 and 0 0 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
0 0 and 1 0 differ by one bit
1 0 and 1 1 differ by one bit
1 1 and 0 1 differ by one bit
0 1 and 0 0 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

Constraints:

1 <= n <= 16

题目大意

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] 。
0** 0** 和 0 1 有一位不同
0 1 和 1 1 有一位不同
1 1 和 1 0 有一位不同
1 0 和 0 0 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
0 0 和 1 0 有一位不同
1 0 和 1 1 有一位不同
1 1 和 0 1 有一位不同
0 1 和 0 0 有一位不同

示例 2：

输入： n = 1
输出：[0,1]

提示：

1 <= n <= 16

解题思路

状态记录：
- 使用一个数组 res 保存当前的结果序列。
- 使用一个集合 used 记录已经加入序列的数字，避免重复。
- 初始化结果数组 res 和集合 used，将起点 0 加入其中。
递归过程：
- 使用回溯法，递归尝试将下一个符合条件的数字加入到结果序列中。
- 每次尝试从当前数字开始，翻转其二进制表示的某一位以生成一个新数字。
- 翻转第 i 位可以通过公式 num ^ (1 << i) 实现。
- 如果新数字未被使用，将其加入序列，并继续递归。
- 如果无法继续（当前路径无法覆盖所有数字），回溯并尝试其他可能的路径。
递归退出条件：
- 当结果序列长度达到 2^n，说明所有数字均已访问，返回序列。

复杂度分析

时间复杂度：O(2^n * n)，回溯会尝试所有可能的数字组合，最多尝试 2^n 个数字，每次需要遍历 n 位。
空间复杂度：O(2^n)
- 递归栈深度最多为 O(2^n)。
- used 集合存储最多 2^n 个数字，空间复杂度为 O(2^n)。
- 整体空间复杂度为 O(2^n)。

代码

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function (n) {
	let res = [0]; // 初始序列
	let used = new Set([0]); // 记录已使用的数字

	const backtrack = (num) => {
		// 如果序列长度达到 2^n，返回 true
		if (res.length === Math.pow(2, n)) {
			return true;
		}

		// 遍历每一位，尝试翻转
		for (let i = 0; i < n; i++) {
			const next = num ^ (1 << i); // 翻转第 i 位
			if (used.has(next)) continue; // 如果已经使用过，跳过

			res.push(next); // 将数字加入序列
			used.add(next); // 标记为已使用

			if (backtrack(next)) return true; // 递归，如果成功，直接返回

			// 回溯
			res.pop();
			used.delete(next);
		}

		return false; // 无法继续扩展，返回 false
	};

	backtrack(0); // 从 0 开始生成序列
	return res; // 返回结果
};

89. 格雷编码

# 89. 格雷编码

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

89. 格雷编码

题目

题目大意

解题思路

复杂度分析

代码

相关题目