格雷编码
难度:
标签:
题目描述
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] 。 - 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
代码结果
运行时间: 168 ms, 内存: 18.1 MB
/*
* 思路：
* 1. 使用Java Stream，我们可以更简洁地生成格雷码序列。
* 2. 同样利用公式G(i) = i ^ (i >> 1)生成每个元素，并将其收集到List中。
*/
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class GrayCodeStream {
public List<Integer> grayCode(int n) {
return IntStream.range(0, 1 << n) // 生成0到2^n-1的数字
.map(i -> i ^ (i >> 1)) // 转换为格雷码
.boxed() // 转换为Integer对象
.collect(Collectors.toList()); // 收集到List中
}
}解释
方法:
这个题解使用回溯法生成格雷码序列。它从空字符串开始，每次在当前字符串后面添加一个字符 '0' 或 '1'，然后递归地生成下一个字符。添加字符的顺序通过 choices 参数控制，第一次添加 '0' 后继续使用 ('0', '1')，添加 '1' 后改用 ('1', '0')，这样可以保证相邻的格雷码二进制表示只有一位不同。当字符串长度达到 n 时，将其转换为整数添加到结果列表中。
时间复杂度:
O(n * 2^n)
空间复杂度:
O(n * 2^n)
代码细节讲解
🦆
在回溯算法中，你是如何确保每对相邻整数的二进制表示恰好一位不同的？
▷🦆
为什么在添加'1'后要改用选择列表('1', '0')而不是继续使用('0', '1')？这种改变的顺序有什么特别的意义吗？
▷🦆
回溯法在生成格雷码时，如何保障第一个和最后一个整数的二进制表示恰好一位不同？
▷🦆
在使用回溯法生成格雷码的过程中，有没有可能生成重复的码？如果有，是如何避免的？
▷相关问题
1 比特与 2 比特字符
有两种特殊字符：
- 第一种字符可以用一比特
0表示 - 第二种字符可以用两比特（
10或11）表示
给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。
示例 1:
输入: bits = [1, 0, 0] 输出: true 解释: 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。 所以最后一个字符是一比特字符。
示例 2:
输入：bits = [1,1,1,0] 输出：false 解释：唯一的解码方式是将其解析为两比特字符和两比特字符。 所以最后一个字符不是一比特字符。
提示:
1 <= bits.length <= 1000bits[i]为0或1