43. 字符串相乘 [medium]
43. 字符串相乘 [medium]
https://leetcode-cn.com/problems/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）或直接将输入转换为整数来处理。
通过次数75,007提交次数176,546
Second Try
2020-07-27
参考题解得到的简化写法，但怎么感觉写起来要注意的细节有点太多了，还是没有first try来的直接。
从个位数算起，且起始值为0，则第i位和第j位的乘积在第i + j位和i + j + 1位(如果大于10的话)。 考虑如下，如果大于10，则会有倍增效应。如果2位数和2位数，乘积应该是3位数或者4位数。不过位数从0算起，2位数的下标位1，刚好就是1 + 1 或者1 + 1 + 1,分别是下标2和3，也就是3或4位。
最后再考虑下在[i + j]位或者[i + j + 1]位的结果中，仍然需要进位的情况，就算搞定了。
不过细节有点多，又贡献了错误提交，还是不如first try的原始方法来得稳妥。
class Solution:
def multiply(self, num1: str, num2: str) -> str:
def atoi(a):
return ord(a) - ord('0')
if num1 == '0' or num2 == '0':
return '0'
rv = [0] * (len(num1) + len(num2))
for i in range(len(num1)):
for j in range(len(num2)):
t = atoi(num1[i]) * atoi(num2[j])
carry, digit = divmod(t, 10)
# 从尾数开始的真正尾数，个位数为0，十位数为1
# 与rv的顺序也是相反的，需要特殊处理
posi = len(num1) - 1 - i
posj = len(num2) - 1 - j
rv[posi + posj + 1] += carry
rv[posi + posj] += digit
# print("i", posi, num1[i], "j", posj, num2[j], "rv", rv, carry, digit )
# rv里面还有溢出的
for i in range(len(rv)):
if rv[i] >= 10:
carry, digit = divmod(rv[i], 10)
rv[i] = digit
rv[i + 1] += carry
# print('new rv', rv)
rv = [chr(ord('0') + i) for i in reversed(rv)] # 注意这里是reversed(rv)
rv = "".join(rv).lstrip('0')
return rv
- 执行用时：260 ms, 在所有 Python3 提交中击败了24.53%的用户
- 内存消耗：13.7 MB, 在所有 Python3 提交中击败了5.88%
First Try
2020-07-27
竟然不能转化为int处理，那就按照乘法草稿，逐位进行处理。
拆建为几个小函数:
chr(ord('0') + int)把单个数字转化为字符，ord(str)把单个字符转化为数字。multi_one把两个数字的乘法拆分为一个数字乘以单一位数的过程，是十位和百味之类采取对第一个数字补零处理。add函数实现在不同位数的乘法结果之间进行加法汇总。由于长度不等的数字加法判断挺繁琐，提前将两个数字补零对齐。然后考虑逐位加法的时候carry进位的特殊作用即可。- 使用上面的小函数攒起来，就是一个标准的草稿乘法操作。
其实就是琐碎的拆解，一波写完后贡献了几个bug终于搞定，只是没想到速度排名这么后。。。
"""
failed test case:
"9133" "0" -> "0000",应该是"0"
"""
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# 这是要实现乘法和加法吗
def atoi(a):
return ord(a) - ord('0')
def itoa(i):
return chr(ord('0') + i)
def add(di, dj):
"""先补齐位数，然后逐位加法 """
if len(di) < len(dj):
di = '0' * (len(dj) - len(di)) + di
elif len(di) > len(dj):
dj = '0' * (len(di) - len(dj)) + dj
rv = ""
carry = 0
for i in reversed(range(len(di))):
t = atoi(di[i]) + atoi(dj[i]) + carry
carry, digit = divmod(t, 10)
rv = itoa(digit) + rv
if carry:
rv = itoa(carry) + rv
return rv
def multi_one(di, d):
"""只考虑任意大小的数字di，乘以只有一位的d"""
rv = ""
carry = 0
for i in reversed(range(len(di))):
t = atoi(di[i]) * atoi(d) + carry
carry, digit = divmod(t, 10)
rv = itoa(digit) + rv
if carry:
rv = itoa(carry) + rv
rv = rv.lstrip("0")
# 规避"25" * "0"或者"0" * "25"导致结果为"00"的问题
return rv if len(rv) else "0"
def multi(di, dj):
rv = ""
for i in reversed(range(len(dj))):
padding_zeros = len(dj) - 1 - i
t = multi_one(di + '0' * padding_zeros, dj[i])
rv = add(rv, t)
return rv
rv = multi(num1, num2)
return rv
- 执行用时：568 ms, 在所有 Python3 提交中击败了5.04%的用户
- 内存消耗：13.7 MB, 在所有 Python3 提交中击败了5.88%的用户