043. 字符串相乘

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

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”
说明：

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        pass

    def multiply(self, num1: str, num2: str) -> str:
        # 把每一位的乘积保留到对应指数位的数组里
        saves = [[] for _ in range(len(num1)+len(num2))]
        num1_int_r = [int(x) for x in num1[::-1]]
        num2_int_r = [int(x) for x in num2[::-1]]
        for pow1,n1 in enumerate(num1_int_r):
            for pow2,n2 in enumerate(num2_int_r):
                saves[pow1+pow2].append(n1*n2)

        # 每一位数组求和，十位以上部分进位
        res_r = []
        pow=0
        while pow<len(saves):
            sum_now = sum(saves[pow])
            res_r.append(sum_now%10)
            remain = sum_now//10
            if remain:
                if pow<len(saves):
                    saves[pow+1].append(remain)
                else:
                    saves.append([remain])
            pow+=1

        # 去除结尾多余的0，逆序拼接字符串
        while len(res_r)>1 and res_r[-1]==0: res_r.pop(-1)
        return ''.join([str(x)for x in res_r[::-1]])


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])]  # list转node
    return s.multiply(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        ["123","456"],
        ["0","0"],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{time.time() - t0}s')

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

备注：
GitHub：https://github.com/monijuan/leetcode_python

CSDN汇总：模拟卷Leetcode 题解汇总_卷子的博客-CSDN博客

可以加QQ群交流：1092754609

leetcode_python.utils详见汇总页说明
先刷的题，之后用脚本生成的blog，如果有错请留言，我看到了会修改的！谢谢！