LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用

简介: 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

方法一:递归公式法

解题步骤
  1. 递归定义:利用格雷码的递归性质,G(n) = [0G(n-1), 1G(n-1)_reverse],即先加上 n-1 的格雷码序列,然后加上 n-1 的格雷码序列反转并在最高位加 1。
  2. 基本情况:当 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)),递归栈的深度和输出结果的长度。

方法二:二进制法

解题步骤
  1. 二进制转换:格雷码可以通过 G(i) = i ^ (i >> 1) 来从二进制转换得到,对于每个数 i,从 02^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)),存储格雷码序列。

方法三:迭代法

解题步骤
  1. 迭代构建:从 n=0 开始,迭代构建到 n,每次迭代利用上一次的结果。
  2. 反向追加:每次迭代在前一次结果的基础上,反向追加加上高位 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. 镜像原理:格雷码可以通过镜像反射的方式构建。首先生成长度为 1 的序列 [0, 1],每次迭代时,对当前列表进行镜像反射,左半部分的数字前加 0,右半部分的数字前加 1
  2. 递增迭代:从 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)),需要存储整个格雷码序列。

方法五:位操作优化

解题步骤
  1. 位操作:利用位操作的特性直接生成格雷码序列。格雷码的生成可以看作是一种位操作,通过对数值进行异或操作实现。
  2. 一次计算:通过从 02^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))
优势 直观、递归简洁 直接、无需递归 易于理解和实现 直观且易于理解 极快且简洁
劣势 深度递归可能导致栈溢出 理解稍难 需要多次复制和追加 需要初始化较长列表 位操作可能不直观

应用示例

格雷码的应用非常广泛,特别是在数字系统和通信领域,如:

  • 数字逻辑设计:在数字逻辑和硬件设计中,格雷码被用来最小化信号在数字电路中的切换错误。
  • 位置编码:在旋转编码器和其他传感器中,格雷码用于确保位置信息在读取过程中的准确性,减少错误。
  • 数据压缩:在某些形式的数据压缩中,格雷码有助于更有效地编码信息。

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
21天前
|
索引
力扣随机一题 6/26 哈希表 数组 思维
力扣随机一题 6/26 哈希表 数组 思维
14 0
|
21天前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
9 0
|
19天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
21天前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
10 1
|
21天前
|
存储 算法
力扣每日一题 6/20 数学+数组
力扣每日一题 6/20 数学+数组
16 1
|
21天前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
17 1
|
24天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
9天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
|
17天前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
8 0