本文主要是介绍LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
python源码解读
程序员必备的数学知识与应用
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
格雷码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷码序列的顺序。格雷码序列必须以 0 开头。
输入格式
- n：编码的位数。
输出格式
- 返回格雷码序列的列表。
示例
示例 1
输入: n = 2
输出: [0, 1, 3, 2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2
方法一：递归公式法
解题步骤
- 递归定义：利用格雷码的递归性质，
G(n) = [0G(n-1), 1G(n-1)_reverse]，即先加上n-1的格雷码序列，然后加上n-1的格雷码序列反转并在最高位加 1。 - 基本情况：当
n = 0时，返回[0]。
完整的规范代码
def grayCode(n):"""根据递归公式生成格雷码:param n: int, 编码的位数:return: List[int], 格雷码序列"""if n == 0:return [0]# 递归生成前一位的格雷码previous = grayCode(n - 1)max_number = 1 << (n - 1)return previous + [max_number + i for i in reversed(previous)]# 示例调用
print(grayCode(2)) # 输出: [0, 1, 3, 2]
算法分析
- 时间复杂度：(O(2^n))，生成长度为 (2^n) 的格雷码序列。
- 空间复杂度：(O(2^n))，递归栈的深度和输出结果的长度。
方法二：二进制法
解题步骤
- 二进制转换：格雷码可以通过
G(i) = i ^ (i >> 1)来从二进制转换得到，对于每个数i，从0到2^n - 1，计算对应的格雷码。
完整的规范代码
def grayCode(n):"""使用二进制转换法生成格雷码:param n: int, 编码的位数:return: List[int], 格雷码序列"""return [i ^ (i >> 1) for i in range(1 << n)]# 示例调用
print(grayCode(2)) # 输出: [0, 1, 3, 2]
算法分析
- 时间复杂度：(O(2^n))，一次遍历生成格雷码序列。
- 空间复杂度：(O(2^n))，存储格雷码序列。
方法三：迭代法
解题步骤
- 迭代构建：从
n=0开始，迭代构建到n，每次迭代利用上一次的结果。 - 反向追加：每次迭代在前一次结果的基础上，反向追加加上高位
1的结果。
完整的规范代码
def grayCode(n):"""迭代法生成格雷码:param n: int, 编码的位数:return: List[int], 格雷码序列"""result = [0]for i in range(n):result += [x + (1 << i) for x in reversed(result)]return result# 示例调用
print(grayCode(2)) # 输出: [0, 1, 3, 2]
算法分析
- 时间复杂度：(O(2^n))，每次迭代都会将结果列表长度翻倍。
- 空间复杂度：(O(2^n))，存储格雷码序列。
方法四：镜像反射法
解题步骤
- 镜像原理：格雷码可以通过镜像反射的方式构建。首先生成长度为
1的序列[0, 1]，每次迭代时，对当前列表进行镜像反射，左半部分的数字前加0，右半部分的数字前加1。 - 递增迭代：从
1位开始，通过递增方式逐步扩展到n位格雷码。
完整的规范代码
def grayCode(n):"""镜像反射法生成格雷码:param n: int, 编码的位数:return: List[int], 格雷码序列"""result = [0, 1]for i in range(1, n):result += [x + (1 << i) for x in reversed(result)]return result# 示例调用
print(grayCode(2)) # 输出: [0, 1, 3, 2]
算法分析
- 时间复杂度：(O(2^n))，每次迭代列表长度翻倍，需要 (n) 次迭代来完成。
- 空间复杂度：(O(2^n))，需要存储整个格雷码序列。
方法五：位操作优化
解题步骤
- 位操作：利用位操作的特性直接生成格雷码序列。格雷码的生成可以看作是一种位操作，通过对数值进行异或操作实现。
- 一次计算：通过从
0到2^n - 1的循环，直接计算每个值的格雷码表示。
完整的规范代码
def grayCode(n):"""位操作优化生成格雷码:param n: int, 编码的位数:return: List[int], 格雷码序列"""return [(i >> 1) ^ i for i in range(1 << n)]# 示例调用
print(grayCode(2)) # 输出: [0, 1, 3, 2]
算法分析
- 时间复杂度：(O(2^n))，对于给定的位数
n，生成所有可能的2^n个格雷码。 - 空间复杂度：(O(2^n))，用于存储生成的格雷码序列。
不同算法的优劣势对比
| 特征 | 方法一：递归公式法 | 方法二：二进制法 | 方法三：迭代法 | 方法四：镜像反射法 | 方法五：位操作优化 |
|---|---|---|---|---|---|
| 时间复杂度 | (O(2^n)) | (O(2^n)) | (O(2^n)) | (O(2^n)) | (O(2^n)) |
| 空间复杂度 | (O(2^n)) | (O(2^n)) | (O(2^n)) | (O(2^n)) | (O(2^n)) |
| 优势 | 直观、递归简洁 | 直接、无需递归 | 易于理解和实现 | 直观且易于理解 | 极快且简洁 |
| 劣势 | 深度递归可能导致栈溢出 | 理解稍难 | 需要多次复制和追加 | 需要初始化较长列表 | 位操作可能不直观 |
应用示例
格雷码的应用非常广泛，特别是在数字系统和通信领域，如：
- 数字逻辑设计：在数字逻辑和硬件设计中，格雷码被用来最小化信号在数字电路中的切换错误。
- 位置编码：在旋转编码器和其他传感器中，格雷码用于确保位置信息在读取过程中的准确性，减少错误。
- 数据压缩：在某些形式的数据压缩中，格雷码有助于更有效地编码信息。
这篇关于LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
