题目：字符串相乘

题目内容：

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

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

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

计算原理

转换为字符串形式的乘法，和之前非负整数求和的思想类似。

https://blog.csdn.net/Medlar_CN/article/details/128590679

即采用字符串乘法的形式，可以极大的扩展乘数的范围，而不采用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

竖式乘法计算规则（摘自百度经验）

竖式指的是每一个数都是由上一个数变化而来,上一个数的个位数乘以2,如果需要进位,则往前面进1,然后个位升十位,以此类推,而个位上补上新的运算数字。

情况1：多位数乘一位数的竖式计算 ：

相同数位对齐，用这个数分别去乘多位数每一个数位上的数，从个位数乘起，即从右往左乘 ，乘到哪一位就把积写在对应哪位数位的下面。

情况2：多位数乘两位数

把数位较多的数写在上面数位较少的写在下面，然后下面的因数要与写在上面的因数的数位要对齐，后第二个因数的个位数与写在上面的数的个位相乘，然后把相乘得到的积的末位写在个位上，再与十位上的数相乘写在十位上，以此类推。

reversed 函数的作用

类似于：while x > 0:#循环取x的最低位r = x % 10#反序输出原数据y = y*10+r#将低位至高位顺次截断，便于下次循环取x的最低位x = int(math.floor(x/10))

以迭代器的形式，返回反转后的数组。

示例代码：

class Solution(object):def multiply(self, num1, num2):if num1 == '0' or num2 == '0':return '0'res = ''ls1, ls2, = len(num1), len(num2)ls = ls1 + ls2arr = [0] * lsfor i in reversed(range(ls1)):for j in reversed(range(ls2)):arr[i + j + 1] += int(num1[i]) * int(num2[j])for i in reversed(range(1, ls)):#此处根据计算规则应为//，求余。原答案中的/为求商计算，计算结果为小数，有误。arr[i - 1] += arr[i] // 10arr[i] %= 10pos = 0if arr[pos] == 0:pos += 1while pos < ls:res = res + str(arr[pos])pos += 1return res
if __name__ == '__main__':s = Solution()print (s.multiply("98", "9"))

Ps: Python3 reversed 函数

摘自Python3 reversed 函数 | 菜鸟教程

描述

reversed 函数返回一个反转的迭代器。

语法

以下是 reversed 的语法:

reversed(seq)

参数

• seq -- 要转换的序列，可以是 tuple, string, list 或 range。

返回值

返回一个反转的迭代器。

实例

以下展示了使用 tuple 的实例：

实例

#!/usr/bin/env python3# 字符串
seqString = 'Runoob'
print(list(reversed(seqString)))# 元组
seqTuple = ('R', 'u', 'n', 'o', 'o', 'b')
print(list(reversed(seqTuple)))# range
seqRange = range(5, 9)
print(list(reversed(seqRange)))# 列表
seqList = [1, 2, 4, 3, 5]
print(list(reversed(seqList)))

以上实例输出结果为：

['b', 'o', 'o', 'n', 'u', 'R']

['b', 'o', 'o', 'n', 'u', 'R']

[8, 7, 6, 5]

[5, 3, 4, 2, 1]