0043. 字符串相乘 #
- 标签:数学、字符串、模拟
- 难度:中等
题目大意 #
给定两个以字符串形式表示的非负整数 num1
和 num2
。
要求:返回 num1
和 num2
的乘积,它们的乘积也表示为字符串形式。
注意:
num1
和num2
的长度小于110
。num1
和num2
只包含数字0
~9
。num1
和num2
均不以零开头,除非是数字0
本身。- 不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。
解题思路 #
我们可以使用数组来模拟大数乘法。长度为 len(num1)
的整数 num1
与长度为 len(num2)
的整数 num2
相乘的结果长度为 len(num1) + len(num2) - 1
或 len(num1) + len(num2)
。所以我们可以使用长度为 len(num1) + len(num2)
的整数数组 nums
来存储两个整数相乘之后的结果。
整个计算流程的步骤如下:
- 从个位数字由低位到高位开始遍历
num1
,取得每一位数字digit1
。从个位数字由低位到高位开始遍历num2
,取得每一位数字digit2
。 - 将
digit1 * digit2
的结果累积存储到nums
对应位置i + j + 1
上。 - 计算完毕之后从
len(num1) + len(num2) - 1
的位置由低位到高位遍历数组nums
。将每个数位上大于等于10
的数字进行进位操作,然后对该位置上的数字进行取余操作。 - 最后判断首位是否有进位。如果首位为
0
,则从第1
个位置开始将答案数组拼接成字符串。如果首位不为0
,则从第0
个位置开始将答案数组拼接成字符串。并返回答案字符串。
代码 #
|
|