Python世界：力扣题43大数相乘算法实践
Python世界：力扣题43大数相乘算法实践
- 任务背景
- 思路分析
- 方案1
- 方案2
- 方案3
- 方案4
- 无测试套主调
- 测试套主调
- 本文小结
任务背景
问题来自力扣题目43：字符串相乘，大意如下：
Given two non-negative integers
num1andnum2represented as strings, return the product ofnum1andnum2, also represented as a string.
翻译下，需求是：实现大数相乘，字符串乘法
- 输入为非负整数两个字符串
- 要求输出该大数值的乘积
思路分析
方案1
自然的想法是，模拟乘法运算，考验对实际问题的计算机转换，先手动模拟下计算过程，提炼其中算法，如果最高位相乘及低位相加无累进，则提前退出。
99*99=9801 2*2=4
10*10=100 2*2=3
以下示例，运行时间击败32%：
# sol1：暴力法遍历
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# corner case
if num1 == "0" or num2 == "0":
return "0"
elif num1 == "1":
return num2
elif num2 == "1":
return num1
# common case
len1 = len(num1)
len2 = len(num2)
len_sum = len1 + len2
len_max = max(len1, len2)
len_min = min(len1, len2)
# 从低位往高位相互进位，个、十、百、千、……
n1_rev = num1[::-1]
n2_rev = num2[::-1]
multi_res_list = []
base = 10
c = 0 # carrier
# 暴力法
for b in range(len_sum + 1):
val = 0
res = 0
# 获取一个阶的结果，如百、十、千
for i in range(len1):
if i > b or b - i >= len2: # i,j比目标进位大，已到头
continue
j = b - i # j>=0 && j<len2
n1 = int(n1_rev[i])
n2 = int(n2_rev[j])
res += n1 * n2
# 处理一个阶的结果
res += c
c = res // base
val = res - c * base
assert(val < base)
if (c == 0 and val == 0 and b > len_max): # 去除冗余前导零
continue
multi_res_list.append(str(val))
# 将列表逆序并转化为字符串输出
# multi_res_list = multi_res_list.reverse() # 未按预期运行，输出结果为None
multi_res_list = multi_res_list[::-1]
non_zero_idx = 0
for val in multi_res_list:
if (val == "0"):
non_zero_idx += 1
else:
break
multi_res_list = multi_res_list[non_zero_idx:]
multi_res_str = "".join(multi_res_list) # 列表转字符串
return multi_res_str
方案2
尝试进一步改进：
- 通过限制上下界，降低内外for循环次数
- 内循环len1选两者较小的长度
- 如果i大于b时，直接break
- 外循环b设计提前退出条件，当前导都是零时，无计算必要
- 不整体逆序，直接从末尾字符低位往高位移动（TBD）
# sol2：beat 42.5%
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# corner case
if num1 == "0" or num2 == "0":
return "0"
elif num1 == "1":
return num2
elif num2 == "1":
return num1
# common case
len1 = len(num1)
len2 = len(num2)
len_sum = len1 + len2
len_max = max(len1, len2)
len_min = min(len1, len2)
# 从低位往高位相互进位，个、十、百、千、……
n1_rev = num1[::-1]
n2_rev = num2[::-1]
multi_res_list = []
base = 10
c = 0 # carrier
# 暴力法
for b in range(len_sum): # b [0, len_sum-1]
val = 0
res = 0
# 获取一个阶的结果，如百、十、千
for i in range(len1):
if i > b:
break
if b - i >= len2: # i,j比目标进位大，已到头
continue
j = b - i # j>=0 && j<len2
n1 = int(n1_rev[i])
n2 = int(n2_rev[j])
res += n1 * n2
# 处理一个阶的结果
res += c
c = res // base
val = res - c * base
assert(val < base)
if (c == 0 and val == 0 and b > len_max): # 去除冗余前导零
continue
multi_res_list.append(str(val))
if (b + 1 == len_sum and c == 0):
break # 最高位相乘无进位
# 将列表逆序并转化为字符串输出
# multi_res_list = multi_res_list.reverse() # 未按预期运行，输出结果为None
multi_res_list = multi_res_list[::-1]
non_zero_idx = 0
for val in multi_res_list:
if (val == "0"):
non_zero_idx += 1
else:
break
multi_res_list = multi_res_list[non_zero_idx:]
multi_res_str = "".join(multi_res_list) # 列表转字符串
return multi_res_str
方案3
网上参考的一种实现，运行时间对比：
# # sol3：beat 29.9%
# # 参考解法：https://blog.csdn.net/huqinweI987/article/details/88797663
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':#有0就不用乘了。
return '0'
res = ''
carry = 0#初始化
# 两个数的长度，分别都减1
m = len(num1) - 1
n = len(num2) - 1
# m和n都是len减1，是因为，15*15中，不算被动进位，能用来主动计算乘法的，最高位就是百位，10*10=100，是主动计算的最高位。
# k就在[0,m+n]的区间：代表主动计算乘法的位（最后多出来的进位单独给出）。k=0，i和j都是0,5*5，对应个位结果。
# k=1，i和j分别是0、1和1、0组合，是10和5或者5和10，对应十位的结果，
# k=2，i和j分别是1、1（其他组合不满足筛选条件，我计算的就是百位，不能把5也拿来用吧，把乘法写一下就出来了），代表10和10相乘，对应百位结果。
for k in range(m + n + 1):
print('k:',k)
# i是所有输出位，包括k=m+n，不包括m+n+1，其实就是遍历所有可能的num1和num2的单独一位，做一个总的累加
# i、j他俩是严格针对k的互补关系。i = 时，j = 1；i = 1时，j = 0，他们都对应结果的“下标”k=1，也就是“十位”
sum = carry#先把进位计算进来（这个顺序其实无所谓，但是如果不是先进位，就要给sum清零了）
for i in range(k + 1):#k其实就是结果位。i和j是根据k做的互补，严格对应一个结果底位。
j = k - i
if i <= m and j <= n:
index_i = m - i# 转换，字符串形式，i=0其实代表的是最大的那个数，不是最小的，index_i才是最小的数。
index_j = n - j
sum += int(num1[index_i]) * int(num2[index_j])#
# 拼接结果字符串，遍历完当前k对应的所有i和j的组合，当前位的结果已经出炉，可以拼接了。比如15*15的最后一位5*5，是由当前位停留结果5和进位2组成的，当前结果就留在这。
res = str(sum % 10) + res#从低位向高位迭代，使用新的sum模，后加res的拼接方式。
carry = sum // 10#进位，5*5=25，进位2
if carry:#最后一位了，k迭代的是乘法计算，当然可能发生进位，比如33*44中，k是0到2，最高位3*4肯定要进位的
res = str(carry) + res
return res
方案4
参考烧脑版的第二个直观优雅的思路，进行python实现：先乘，再进位，代码如下：
# sol4：beat 34%
# 参考烧脑版的第二个思路进行python实现：先乘，再进位
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# corner case
if num1 == "0" or num2 == "0":
return "0"
elif num1 == "1":
return num2
elif num2 == "1":
return num1
# common case
len1 = len(num1)
len2 = len(num2)
len_sum = len1 + len2
# 从低位往高位相互进位，个、十、百、千、……
n1_rev = num1[::-1]
n2_rev = num2[::-1]
multi_res_list = []
# 整体乘完放1个数组
num_rev_list = [0]*(len_sum)
for i in range(len1):
for j in range(len2):
n1 = int(n1_rev[i])
n2 = int(n2_rev[j])
num_rev_list[i + j] += n1 * n2
base = 10
# 统一处理进制问题
for i in range(len(num_rev_list) - 1):
num_rev_list[i+1] += num_rev_list[i] // base
num_rev_list[i] = num_rev_list[i] % base
# 处理最高位的corner case
# if (num_rev_list[len_sum - 1] == 0):
multi_res_list = num_rev_list[::-1]
non_zero_idx = 0
for val in multi_res_list:
if (val == 0):
non_zero_idx += 1
else:
break
multi_res_list = multi_res_list[non_zero_idx:]
multi_res_str = "".join((str(i) for i in multi_res_list)) # 列表中的每个数字转字符串
return multi_res_str
无测试套主调
无测试套版本主调：
# 无测试套版本主调
if __name__ == '__main__':
print('start!')
# num1 = "2"
# num2 = "3"
# ret = "6"
# num1 = "99"
# num2 = "99"
# ret = "9801"
num1 = "10"
num2 = "10"
ret = "100"
# num1 = "1"
# num2 = "123456789"
# ret = "123456789"
# num1 = "123456789"
# num2 = "0"
# ret = "0"
# num1 = "123"
# num2 = "456"
# ret = "56088"
# num1 = "37689269854"
# num2 = "12548698156"
# ret = "472951271117876189224"
# num1 = "6"
# num2 = "501"
# ret = "3006"
problem = Solution()
res = problem.multiply(num1, num2)
assert(res == ret)
print(res, "right!")
print('done!')
测试套主调
编写含单元测试的主调：
# 导入单元测试
import unittest
# function...
# 编写测试套
class TestSol(unittest.TestCase):
def test_bound1(self):
num1 = "2"
num2 = "3"
ret = "6"
sol = Solution()
self.assertEqual(sol.multiply(num1, num2), ret)
def test_bound2(self):
num1 = "37689269854"
num2 = "12548698156"
ret = "472951271117876189224"
sol = Solution()
self.assertEqual(sol.multiply(num1, num2), ret)
def test_bound3(self):
num1 = "1"
num2 = "123456789"
ret = "123456789"
sol = Solution()
self.assertEqual(sol.multiply(num1, num2), ret)
def test_bound4(self):
num1 = "123456789"
num2 = "0"
ret = "0"
sol = Solution()
self.assertEqual(sol.multiply(num1, num2), ret)
def test_special1(self):
num1 = "6"
num2 = "501"
ret = "3006"
sol = Solution()
self.assertEqual(sol.multiply(num1, num2), ret)
def test_special2(self):
num1 = "10"
num2 = "10"
ret = "100"
sol = Solution()
self.assertEqual(sol.multiply(num1, num2), ret)
def test_special3(self):
num1 = "99"
num2 = "99"
ret = "9801"
sol = Solution()
self.assertEqual(sol.multiply(num1, num2), ret)
def test_common_case(self):
num1 = "123"
num2 = "456"
ret = "56088"
sol = Solution()
self.assertEqual(sol.multiply(num1, num2), ret)
# 含测试套版本主调
if __name__ == '__main__':
print('start!')
unittest.main() # 启动单元测试
print('done!')
本文小结
为便于深入理解进制转换和乘法原理，同时提高编程能力，demo程序中新增单元测试代码实现。
卡壳点：
- 陷入复杂算法细节，而不是以终为始。在没明确思路前，先实现再优化，用笨办法/暴力法解决了，再尝试改进。
- corner case处理不当。 结尾中，输出字符串前导0场景。 中间乘积结果为0，进位符为0场景未考虑周全。
总的来说，推荐solution4方法进行解题。
此外，进阶想一想，如果将其变成大数加法，这个程序能否只改两三行代码，即可输出正确结果？再如，改成八进制乘法，如何搞？
题解参考
- 暴力法分解为单数相乘：LeetCode:43 multiply 大数乘法的数学直观理解
- 暴力法分解为字符串相加：字符串相乘（大数相乘、相加）
- 进阶烧脑版高效算法实现：博客园版本、CSDN版本
涉及知识点
- python 纯数字list转化为字符串，link
- Python字符串中添加、插入特定字符，link
- Python 列表逆序排列的 3 种方式，link
- 廖雪峰，Python自带单元测试，unittest