LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】

简介: LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

本文将详细介绍解决LeetCode题目43 "字符串相乘"的三种方法:模拟乘法手算、Karatsuba算法,以及快速傅立叶变换(FFT)方法。这些方法逐渐提升计算大数乘法的效率。

问题描述

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"

方法一:模拟乘法手算

解题步骤

  1. 初始化结果数组:长度为两数长度之和,用于存放乘积的每一位。
  2. 逐位相乘:外层和内层循环分别遍历两个字符串的每一位数字,相乘后加到结果数组的相应位置。
  3. 处理进位:从结果数组的末尾开始向前处理进位。
  4. 输出结果:将结果数组转换为字符串,注意去除前导零。

代码示例

def multiply(num1: str, num2: str) -> str:
    if num1 == "0" or num2 == "0":
        return "0"
    
    m, n = len(num1), len(num2)
    # 结果数组,长度为m+n,最大位数的情况
    result = [0] * (m + n)
    
    # 从后向前遍历两个数字
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            # 两数对应位相乘,并加上之前该位的累积结果
            mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
            # 求和位置,即数组中对应的索引
            p1, p2 = i + j, i + j + 1
            # 总和
            sum = mul + result[p2]
            
            # 设置当前位和进位
            result[p1] += sum // 10
            result[p2] = sum % 10
    
    # 将结果数组转换为字符串,首先去除数组前端的0
    while len(result) > 1 and result[0] == 0:
        result.pop(0)
    
    return ''.join(map(str, result))

算法分析

  • 时间复杂度: O(M*N), 其中 M 和 N 是输入数字的长度。
  • 空间复杂度: O(M+N), 用于存储计算结果。

方法二:Karatsuba 算法

解题步骤

Karatsuba 算法是一种分治算法,它通过将大数运算分解为较小数的运算来减少乘法操作的总数。这种方法利用了数学上的巧妙技巧来加速大整数的乘法过程。

  1. 分割数字:将每个数分割成两部分,例如,将数字123456分割为123和456,分割点通常在中间,或者靠近中间。
  2. 递归计算
  • 设两个大数为 ( a ) 和 ( b ),分别分割为 ( a1, a0 ) 和 ( b1, b0 ),其中 ( a1, b1 ) 是高位部分,( a0, b0 ) 是低位部分。
  • 计算三个关键乘积:
  • ( p1 = a1 * b1 )
  • ( p2 = a0 * b0 )
  • ( p3 = (a1 + a0) * (b1 + b0) )
  • 结果通过组合这三个乘积获得:( result = p1 * 10^2m + (p3 - p1 - p2) * 10^m + p2 ),其中 ( m ) 是分割的位数。
  1. 合并结果:根据上述公式组合得到最终的乘积。

完整的规范代码

def karatsuba(num1, num2):
    if len(num1) < 10 or len(num2) < 10:  # 为简化计算,小于10位数直接转为整数计算
        return str(int(num1) * int(num2))
    # 将输入数字补齐为等长
    max_len = max(len(num1), len(num2))
    num1 = num1.zfill(max_len)
    num2 = num2.zfill(max_len)
    
    # 计算分割位数
    half_len = max_len // 2
    
    # 高位和低位数
    high1, low1 = num1[:-half_len], num1[-half_len:]
    high2, low2 = num2[:-half_len], num2[-half_len:]
    
    # 递归计算p1, p2, p3
    z0 = karatsuba(low1, low2)
    z1 = karatsuba(str(int(low1) + int(high1)), str(int(low2) + int(high2)))
    z2 = karatsuba(high1, high2)
    
    # 组合结果
    result = str(int(z2) * 10**(2*half_len) + (int(z1) - int(z2) - int(z0)) * 10**half_len + int(z0))
    return result
# 示例调用
print(karatsuba("123456789", "987654321"))  # 输出: "121932631112635269"

算法分析

  • 时间复杂度: (O(n^1.585,其中 ( n ) 是输入数字的位数。这比传统的 (O(n^2)) 方法要快。
  • 空间复杂度: (O(log n)),主要空间消耗在递归调用栈上。

优点

  • 效率提升:对于大数乘法,Karatsuba算法提供了显著的速度优势。
  • 适用于大数:非常适合处理大规模数字,常用于计算机科学和大数据领域。

缺点

  • 实现复杂度:相比简单的逐位乘法,Karatsuba算法实现更为复杂,特别是在处理数字分割和递归方面。
  • 边界处理:在实际实现时,处理数字长度和递归的终止条件需要小心设计。

Karatsuba算法是大数乘法的一个有效优

化方法,尤其适合于需要快速乘法计算的应用,如加密和数值模拟。通过利用数学的分治技巧,它能够有效地减少计算复杂度,提升计算性能。

方法三:快速傅立叶变换(FFT)

解题步骤

快速傅立叶变换(FFT)是一种高效的数字乘法方法,适用于大数乘法。其基本思想是将整数乘法转换为多项式乘法问题,利用FFT快速进行点值计算。

  1. 数位扩展与对齐:首先将数字字符串转换为逆序的整数数组,并扩展长度至2的幂次方,以满足FFT的要求。
  2. 应用FFT转换:将数字数组通过FFT转换到频域,即计算其点值表示。
  3. 点值乘法:将两个数的点值数组对应位置相乘,这相当于多项式乘法的点值表示。
  4. 逆FFT变换:应用逆FFT将乘积的点值表示转换回系数表示,即得到时间域的多项式系数。
  5. 处理进位与格式化:将逆FFT的结果处理进位,然后转换为字符串输出。

完整的规范代码

使用numpy库来实现FFT和逆FFT,这里假设已经安装了numpy。

import numpy as np
def fft(a):
    n = len(a)
    if n == 1:
        return a
    even = fft(a[0::2])
    odd = fft(a[1::2])
    T = [np.exp(-2j * np.pi * k / n) * odd[k] for k in range(n // 2)]
    return [even[k] + T[k] for k in range(n // 2)] + [even[k] - T[k] for k in range(n // 2)]
def ifft(a):
    n = len(a)
    if n == 1:
        return a
    even = ifft(a[0::2])
    odd = ifft(a[1::2])
    T = [np.exp(2j * np.pi * k / n) * odd[k] for k in range(n // 2)]
    return [(even[k] + T[k]) / 2 for k in range(n // 2)] + [(even[k] - T[k]) / 2 for k in range(n // 2)]
def multiply(num1, num2):
    n = 1
    while n < max(len(num1), len(num2)):
        n <<= 1
    n <<= 1
    a = np.array([int(x) for x in num1[::-1]] + [0] * (n - len(num1)), dtype=complex)
    b = np.array([int(x) for x in num2[::-1]] + [0] * (n - len(num2)), dtype=complex)
    
    fa = fft(a)
    fb = fft(b)
    fc = fa * fb
    c = ifft(fc)
    
    result = [0] * n
    carry = 0
    for i in range(n):
        result[i] = int(np.round(c[i].real)) + carry
        carry = result[i] // 10
        result[i] %= 10
    
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    
    return ''.join(map(str, result[::-1]))
# 示例调用
print(multiply("123456789", "987654321"))  # 输出: "121932631112635269"

算法分析

  • 时间复杂度:(O(n log n)),其中 (n) 是结果数字的最大长度。这得益于FFT和逆FFT的效率,它们将多项式乘法的复杂度从 (O(n^2)) 降至 (O(n log n))。
  • 空间复杂度:(O(n)),主要用于存储数字数组及其变换结果。

优点

  • 极高效:对于大规模数字运算,FFT比传统算法和Karatsuba算法更高效。
  • 广泛应用:FFT在科学计算和工程领域中有广泛应用,特别是在信号处理方面。

缺点

  • 实现复杂度:FFT算法比起简单的乘法算法要复杂,需要处理复数运算和逆变换。
  • 依赖外部库:为了高效实现FFT,通常依赖于专门的数学库,如 numpy。

此FFT方法适用于需要快速处理非常大的数字乘法的场景,例如在数据加密、大数科学计算中非常有用。

结论

为了直观地比较解决LeetCode题目43 "字符串相乘"的三种方法,下面的表格将展示它们在不同技术维度的性能和特点,包括时间复杂度、空间复杂度以及各自的优势和劣势。

特征 方法一:模拟乘法手算 方法二:Karatsuba算法 方法三:FFT乘法
时间复杂度 O(M*N) O(N^1.585) O(N log N)
空间复杂度 O(M+N) O(N) O(N)
优势 - 直观且易于实现
- 不需要复杂的数学背景
- 快于传统方法
- 分治方法减少乘法次数
- 最快的方法,适用于非常大的数
- 有效利用FFT算法加速计算
劣势 - 时间复杂度高
- 对于非常大的数字效率低
- 实现相对复杂
- 对初学者不友好
- 实现复杂,需要数学背景知识
- 依赖外部数学库如numpy
适用场景 - 小到中等规模的数字
- 教学和简单应用
- 大数字乘法
- 需要快速算法但又不至于用FFT
- 大规模数字计算
- 科学计算和工程应用

综合分析

方法一(模拟乘法手算)

  • 这种方法非常直观,模拟了人们在纸上进行乘法运算的过程。
  • 它最适合于数字规模较小(例如数位不超过几百)的场景。
  • 对于大规模数字(如数千位或更多),计算效率会显著降低。

方法二(Karatsuba 算法)

  • Karatsuba 算法通过分治技术提高了乘法的效率,适合中到大规模的数字乘法。
  • 虽然它比模拟乘法快,但在极大规模数字乘法(例如数万位)场景下,仍可能不够高效。

方法三(FFT乘法)

  • FFT 乘法提供了最优的时间复杂度,特别适合于大规模数位的乘法问题,如在密码学或大规模科学计算中常见。
  • FFT 的主要缺点是实现复杂性高,需要较强的数学背景支持,并且在某些实现中需要依赖专业的数学库。

在实际选择算法时,应考虑具体的应用需求、数字的规模以及可用资源(如是否可以使用外部库)。对于日常应用和教学,模拟乘法或Karatsuba算法通常足够用;而在需要处理非常大规模数字的科学计算中,FFT 算法是最佳选择。


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


相关文章
|
2天前
|
存储 Python 容器
Python基础语法:变量和数据类型详解(整数、浮点数、字符串、布尔值)
变量和数据类型是Python编程的基础,理解这些概念对于编写高效和正确的代码至关重要。通过本文的介绍,希望你能对Python中的变量和常用数据类型有一个清晰的认识,并能够在实际编程中灵活运用这些知识。
|
7天前
|
Java 开发者 Python
Python中,字符串(String)是一种不可变的数据类型
Python中,字符串(String)是一种不可变的数据类型
|
10天前
|
存储 Python 容器
Python基础:变量和数据类型详解(整数、浮点数、字符串、布尔值)
变量和数据类型是Python编程的基础,理解这些概念对于编写高效和正确的代码至关重要。通过本文的介绍,希望你能对Python中的变量和常用数据类型有一个清晰的认识,并能够在实际编程中灵活运用这些知识。
|
6天前
|
机器学习/深度学习 缓存 安全
Python标准库中的`str`类型有一个`translate()`方法,它用于替换字符串中的字符或字符子集。这通常与`str.maketrans()`方法一起使用,后者创建一个映射表,用于定义哪些字符应该被替换。
Python标准库中的`str`类型有一个`translate()`方法,它用于替换字符串中的字符或字符子集。这通常与`str.maketrans()`方法一起使用,后者创建一个映射表,用于定义哪些字符应该被替换。
|
6天前
|
存储 算法 安全
我们来看一个简单的Python代码示例,它使用`hashlib`模块中的`md5()`和`sha256()`函数来计算字符串的哈希值。
我们来看一个简单的Python代码示例,它使用`hashlib`模块中的`md5()`和`sha256()`函数来计算字符串的哈希值。
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词