LeetCode题目43:字符串相乘

输入: num1 = "2", num2 = "3"
输出: "6"

输入: num1 = "123", num2 = "456"
输出: "56088"

def multiply(num1: str, num2: str) -> str:
    # 特殊情况处理，任一数字为'0'，结果即为'0'
    if num1 == "0" or num2 == "0":
        return "0"
    # 结果最多为两数字长度之和
    result = [0] * (len(num1) + len(num2))
    # 从后向前遍历两个字符串
    for i in range(len(num1)-1, -1, -1):
        for j in range(len(num2)-1, -1, -1):
            # 乘积在result对应的索引位置
            mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
            # 加上result[i+j+1]位置的旧值
            sum_ = mul + result[i+j+1]
            # 更新result数组
            result[i+j+1] = sum_ % 10  # 当前位
            result[i+j] += sum_ // 10  # 进位
    # 将结果数组转换为字符串，跳过前导零
    result_str = ''.join(map(str, result))
    return result_str.lstrip('0')  # 去除可能存在的前导零
# 示例调用
print(multiply("123", "456"))  # 输出: "56088"

def multiply(num1: str, num2: str) -> str:
    # 基础情况处理
    if len(num1) == 1 or len(num2) == 1:
        return str(int(num1) * int(num2))
    
    # 使得num1和num2长度相同，前面补0
    max_len = max(len(num1), len(num2))
    num1 = num1.zfill(max_len)
    num2 = num2.zfill(max_len)
    
    # 分割数字
    m = max_len // 2
    high1, low1 = num1[:-m], num1[-m:]
    high2, low2 = num2[:-m], num2[-m:]
    
    # 递归计算p1, p2, p3
    z0 = multiply(low1, low2)
    z1 = multiply(str(int(low1) + int(high1)), str(int(low2) + int(high2)))
    z2 = multiply(high1, high2)
    
    # 计算并合并结果
    return str(int(z2 + '0'*(2*m)) + (int(z1) - int(z2) - int(z0)) * (10**m) + int(z0))
# 示例调用
print(multiply("123", "456"))  # 输出: "56088"

import numpy as np
def fft(a):
    n = len(a)
    if n == 1:
        return a
    omega_n = np.exp(2j * np.pi / n)
    omega = 1
    a0 = a[0::2]
    a1 = a[1::2]
    y0 = fft(a0)
    y1 = fft(a1)
    y = np.zeros(n, dtype=complex)
    for k in range(n // 2):
        y[k] = y0[k] + omega * y1[k]
        y[k + n // 2] = y0[k] - omega * y1[k]
        omega *= omega_n
    return y
def ifft(y):
    n = len(y)
    y_conj = np.conjugate(y)
    a = fft(y_conj)
    a = np.conjugate(a)
    return a / n
def multiply(num1, num2):
    # 初始化数据
    n = 1
    while n < max(len(num1), len(num2)):
        n *= 2
    n *= 2
    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)
    # FFT
    A = fft(a)
    B = fft(b)
    C = A * B
    # 逆FFT
    c = ifft(C).real.round().astype(int)
    # 处理进位
    carry = 0
    for i in range(len(c)):
        c[i] += carry
        carry = c[i] // 10
        c[i] %= 10
    # 去除前导0并转换为字符串
    while len(c) > 1 and c[-1] == 0:
        c = c[:-1]
    return ''.join(map(str, c[::-1]))
# 示例调用
print(multiply("123", "456"))  # 输出: "56088"