[LeetCode]43. 字符串相乘(Multiply Strings)

题目描述

给定两个以字符串形式表示的非负整数 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)或直接将输入转换为整数来处理。

解题思路

参考竖式除法的原理,按位相乘之后存储到对应的位置上,超过 10 即进位,进位上去得到的数大于 10 也不会影响,因为后面遍历到该位置的时候也会做进位处理。使用 ord 函数避免 int

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"

def get_num(s):
return ord(s) - ord("0")

res = [0] * (len(num1) + len(num2))
num1 = num1[::-1]
num2 = num2[::-1]
for i in range(len(num1)):
for j in range(len(num2)):
tmp = get_num(num1[i]) * get_num(num2[j]) + res[i + j]
if tmp >= 10:
res[i + j] = tmp % 10
res[i + j + 1] += (tmp // 10)
else:
res[i + j] = tmp
res.reverse()
while res and res[0] == 0:
res = res[1:]
return "".join(map(str, res))

执行用时 : 192 ms
内存消耗 : 13.9 MB