题目:
难度:Middle
相关话题:数学
、字符串
给定两个以字符串形式表示的非负整数 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) 或直接将输入转换为整数来处理 。
思路:
按照小学算乘法的步骤,关键点是使用数组来保存进位值,数组的长度最长不会超过num1.length+num2.length
。
例如: 计算18*45
1 8
4 5
---------
4 0 [0,0,4,0]
5 [0,0,9,0]
3 2 [0,4,1,0]
4 [0,8,1,0]
----------
8 1 0
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function(num1, num2) {
if(num1 === '0' || num2 === '0') return '0';
let pos = new Array(num1.length+num2.length).fill(0);
for(let i = num1.length - 1; i >= 0; i --) {
let n = +(num1[i]);
for (let j = num2.length - 1; j >= 0; j --) {
let m = +(num2[j]);
let mul = m * n;
let p1 = i + j;
let p2 = i + j + 1;
let sum = mul + pos[p2];
pos[p1] += Math.floor(sum / 10);
pos[p2] = sum % 10;
}
}
let res = pos.join('');
return res[0] === '0' ? res.slice(1) : res
};