题解 | #大数乘法#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串 第一个整数
# @param t string字符串 第二个整数
# @return string字符串
#
class Solution:
    # 字符串乘法
    def solve(self, s: str, t: str) -> str:
        # write code here
        # 分治法
        num = max(len(s), len(t)) // 2
        # 递归出口
        if s == "" or t == "":
            return ""
        if num <= 2:
            return str(int(s) * int(t))

        # 将每个数字一分为2，（a*10^num+b）*(c*10^num+d)
        s_l, s_r = s[:-num], s[-num:]
        t_l, t_r = t[:-num], t[-num:]
        print(s_l, s_r)
        print(t_l, t_r)
        p1 = self.solve(s_l, t_l)  # a*c
        p2 = self.solve(s_r, t_r)  # b*d
        p3 = self.solve(self.str_add(s_l, s_r), self.str_add(t_l, t_r))  # (a+b)*(c+d)
        if p1 != "":
            res1 = self.add_zero(p1, num * 2)  # 10^n*(a*c)
        else:
            res1 = ""
        cun = self.str_sub(self.str_sub(p3, p1), p2)  # ((a+b)*(c+d)-a*c-b*d)
        res2 = self.add_zero(cun, num)  # 10^(n/2)*((a+b)*(c+d)-a*c-b*d)
        res = self.str_add(self.str_add(res1, res2), p2) # 10^n*(a*c)+10^(n/2)((a+b)*(c+d)-a*c-b*d)+b*d
        return res

    # 字符串加法
    def str_add(self, s: str, t: str) -> str:
        s = list(map(int, list(s)))  # 将s转化成数字数组
        s.reverse()  # 从低位开始计算
        t = list(map(int, list(t)))  # 将t转化为数字数组
        t.reverse()  # 从低位开始计算
        num = max(len(s), len(t)) + 1  # 最长串
        # 将两个串加0到等长
        for i in range(len(s) - 1, num):
            s.append(0)
        for i in range(len(t) - 1, num):
            t.append(0)
        carry = 0  # 进位
        res = [0] * num
        for i in range(num):
            cun = s[i] + t[i] + carry
            carry = (cun) // 10
            res[i] = str(cun % 10)
        # 去除多余的0
        while res[-1] == "0" and len(res) > 1:
            res.pop()
        res.reverse()
        return "".join(res)

    # 字符串减法
    def str_sub(self, s: str, t: str) -> str:
        # 大的减小的
        s = list(map(int, list(s)))  # 将s转化成数字数组
        s.reverse()  # 从低位开始计算
        t = list(map(int, list(t)))  # 将t转化为数字数组
        t.reverse()  # 从低位开始计算
        num = max(len(s), len(t)) + 1  # 最长串
        # 将两个串加0到等长
        for i in range(len(s) - 1, num):
            s.append(0)
        for i in range(len(t) - 1, num):
            t.append(0)
        carry = 0  # 借位
        res = [0] * num
        for i in range(num):
            cun = s[i] - t[i] - carry
            if cun < 0:
                # 不够借
                carry = 1
                cun += 10
            else:
                carry = 0
            res[i] = str(cun)
        # 去除多余的0
        while res[-1] == "0" and len(res) > 1:
            res.pop()
        res.reverse()
        return "".join(res)

    # 乘10的n次幂
    def add_zero(self, s: str, n) -> str:
        # 添加0，如s*10^n就是在s后面添加n个0
        s = list(s)
        res = "".join(s + ["0"] * n)
        return res