Leetcode 43题

思路

由小学知识, 我们可以通过列竖式计算乘法

e.g. 1234 x 567

(突然发现617多打了个0, 不过无所谓了, 我懒得改了)

不难注意到, 竖式计算就是先计算一位数乘以多位数的结果然后再将其相加

还是以1234 x 567为例, 可转化为 1234 x 7 + 1234 x 60 + 1234 x 500

最后在这里将结果汇总 (多简单的小学乘法, 对吧?)

也就是说我们可以使用list存储数位, 乘了以后存储到其中

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        # 逆序
        num1 = list(int(i) for i in num1)[::-1]
        num2 = list(int(i) for i in num2)[::-1]
        # 结果存储, 长度为两数相乘结果最大长度
        Res = [0] * (len(num1) + len(num2))

接下来一位一位乘, 以及进位 (十位加到下一位, 只保留个位)

for i in range(len(num2)):
   for a in range(len(num1)):
      Res[a + i] += num1[a] * num2[i]   # 这里a + i的原因是因为数位变动, 补0
   while max(Res) > 9:   # 是否都进位完
      for a in range(len(Res)):
         if Res[a] > 9:
            Res[a + 1] += Res[a] // 10
            Res[a] %= 10

返回结果 (反转, 去前导0)

Res.reverse()
while Res and Res[0] == 0:
   Res.pop(0)
return ''.join(str(i) for i in Res) or '0'

完整代码

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        num1 = list(int(i) for i in num1)[::-1]
        num2 = list(int(i) for i in num2)[::-1]
        Res = [0] * (len(num1) + len(num2))
        for i in range(len(num2)):
            for a in range(len(num1)):
                Res[a + i] += num1[a] * num2[i]
            while max(Res) > 9:
                for a in range(len(Res)):
                    if Res[a] > 9:
                        Res[a + 1] += Res[a] // 10
                        Res[a] %= 10
        Res.reverse()
        while Res and Res[0] == 0:
            Res.pop(0)
        return ''.join(str(i) for i in Res) or '0'

复杂度

时间复杂度O(N∗M)

空间复杂度O(N+M)