字符串相乘
JavaScript实现LeetCode第43题：字符串相乘
题目描述
给定两个以字符串形式表示的非负整数 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）或直接将输入转换为整数来处理。
解题方法
最开始的思路是把字符串分别转成数字，然后相乘，会出现数字溢出的情况。同时题目要求不能使用现成的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('');
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-05-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
