给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明:
最开始的思路是把字符串分别转成数字,然后相乘,会出现数字溢出的情况。同时题目要求不能使用现成的api来处理。所以放弃这个一开始就能想到的思路。
分析竖式相乘的步骤,转成代码的思维来解决。
num1的第 i 位(高位从0开始 和 num2 的第 j 位相乘的结果在乘积中的位置是 [i + j, i+ j + 1];
例如 123 45, 123的第1位 2和 45的第0位4乘积 08存放在结果的第 [1, 2]位中
index: 0 1 2 3 4
1 2 3
* 4 5
---------
1 5
1 0
0 5
---------
0 6 1 5
1 2
0 8
0 4
----------
0 5 5 3 5
这样我们就可以单独对每一位进行相乘计算把结果存入相应的index中
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*
*/
var multiply = function(num1, num2) {
if(num1 === '0' || num2 === '0') {
return '0';
}
let m = num1.length;
let n = num2.length;
let res = new Array(m + n).fill(0);
for(let i = m - 1; i >= 0; i--) {
for(let j = n - 1; j >= 0; j--) {
let sum = res[ i + j + 1] + +num1[i] * +num2[j]
res[ i + j + 1] = sum % 10;
res[ i + j ] += (sum / 10) | 0;
}
}
// 如果最开始有0,则需要移除
if(res[0] === 0) {
res.shift();
}
return res.join('');
};