43.md

题目地址

https://leetcode-cn.com/problems/multiply-strings/

解答1

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        """
            字符串相乘（竖式计算，非最优解）

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

            输入: num1 = "123", num2 = "456"
            输出: "56088"
        """
        ans = 0
        num1, num2 = num1[::-1], num2[::-1]
        s = [0] * (len(num1) + len(num2))
        for i in range(len(num1)):
            for j in range(len(num2)):
                s[i + j] = s[i + j] + int(num1[i]) * int(num2[j])
        for i in range(len(s)):
            ans += s[i] * 10 ** i
        return str(ans)

解答2

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        """
            字符串相乘, 算法复杂度n的1.59次方

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

            输入: num1 = "123", num2 = "456"
            输出: "56088"
        """
        if num1 == "0" or num2 == "0":
            return "0"
        n1, n2 = 0, 0
        t1, t2 = num1, num2 = int(num1), int(num2)
        while num1 >= 2:
            num1 >>= 1
            n1 += 1
        while num2 >= 2:
            num2 >>= 1
            n2 += 1
        k1, k2 = 1 << n1, 1 << n2
        r1, r2 = t1 & (k1 - 1), t2 & (k2 - 1)
        A, B, C, D = k1, r1, k2, r2
        return str(A * C + B * C + A * D + B * D)

解答3

class Solution:
    from functools import lru_cache
    @lru_cache(100)
    def multiply(self, num1: str, num2: str) -> str:
        """
            字符串相乘, Karatsuba算法，n的1.58次方, https://zh.wikipedia.org/wiki/Karatsuba%E7%AE%97%E6%B3%95

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

            输入: num1 = "123", num2 = "456"
            输出: "56088"
        """
        return str(self.karatsuba(num1, num2))

    def karatsuba(self, num1, num2):
        if not num1 or not num2:
            return 0
        n, m = len(num1), len(num2)
        if (n < 2) or (m < 2):
            return int(num1) * int(num2)

        maxLength = max(n, m)
        splitPosition = maxLength // 2
        high1, low1 = num1[:-splitPosition], num1[-splitPosition:]
        high2, low2 = num2[:-splitPosition], num2[-splitPosition:]
        z0 = self.karatsuba(low1, low2)
        z1 = self.karatsuba(str(int(low1) + int(high1 or "0")), str(int(low2) + int(high2 or "0")))
        z2 = self.karatsuba(high1, high2)

        return (z2 * 10 ** (2 * splitPosition)) + ((z1 - z2 - z0) * 10 ** (splitPosition)) + z0

解答4

class Solution:
    def toomCook3(self, num1, num2):
        """ 数字乘法 """
        import sympy as sy

        num1, num2 = int(num1), int(num2)
        # 数字分割
        base = 10000
        i = max(int(sy.log(num1, base)) // 3, int(sy.log(num2, base)) // 3) + 1
        B = base ** i

        d, m0 = divmod(num1, B)
        m2, m1 = divmod(d, B)

        d, n0 = divmod(num2, B)
        n2, n1 = divmod(d, B)

        # 评估
        po = m0 + m2
        p0 = m0
        p1 = po + m1
        p_1 = po - m1
        p_2 = (p_1 + m2) * 2 - m0
        pmax = m2

        qo = n0 + n2
        q0 = n0
        q1 = qo + n1
        q_1 = qo - n1
        q_2 = (q_1 + n2) * 2 - n0
        qmax = n2

        r0 = p0 * q0
        r1 = p1 * q1
        r_1 = p_1 * q_1
        r_2 = p_2 * q_2
        rmax = pmax * qmax

        # 插值求解
        a1 = [
            [1, 0, 0, 0, 0],
            [1, 1, 1, 1, 1],
            [1, -1, 1, -1, 1],
            [1, -2, 4, -8, 16],
            [0, 0, 0, 0, 1]
        ]

        a1 = sy.Matrix(a1)
        a1_I = a1.inv()  # 矩阵求逆

        a2 = sy.Matrix([r0, r1, r_1, r_2, rmax])
        ans = a1_I * a2

        return sum((ans[i, 0] * B ** i for i in range(len(ans))))