题目:
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
输入: num1 = "2", num2 = "3"
输出: "6"
输入: num1 = "123", num2 = "456"
输出: "56088"
抛砖引玉
思路
实现
特殊情况
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function (num1, num2) {
if (num1 === '0' || num2 === '0') return '0'
let n = num1.length,
m = num2.length
dp = new Array(n + m).fill(0)
for (let i = n - 1; i >= 0; i--) {
for (let j = m - 1; j >= 0; j--) {
// dp[i+j+1] 包含上一轮该乘积
let sum = dp[i + j + 1] + parseInt(num1[i] * num2[j], 10)
// 当前位i+j+1
dp[i + j + 1] = parseInt(sum % 10, 10)
// 上一位
dp[i + j] = dp[i + j] + parseInt(sum / 10, 10)
}
}
return dp.join('').replace(/^0*/, '')
}
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function (num1, num2) {
if (num1 === '0' || num2 === '0') return '0'
let n = num1.length,
m = num2.length,
_result = '0'
for (let i = m - 1; i >= 0; i--) {
let dp = [],
jin = 0
for (let j = m - 1; j > i; j--) {
// 已处理位填充0
dp.push(0)
}
for (let j = n - 1; j >= 0; j--) {
// 单个位乘积
let sum = parseInt(num2[i] * num1[j], 10) + jin
dp.push(parseInt(sum % 10, 10))
// 进位
jin = parseInt(sum / 10, 10)
}
// 剩余进位
if (jin) {
dp.push(parseInt(jin % 10, 10))
}
// 累加
_result = addStrings(_result, dp.reverse().join(''))
}
return _result
// 字符串累加
function addStrings(a, b) {
let i = a.length - 1,
j = b.length - 1,
jin = 0,
wei = 0,
result = ''
while (i >= 0 || j >= 0 || jin != 0) {
const x = i >= 0 ? a.charAt(i) - '0' : 0
const y = j >= 0 ? b.charAt(j) - '0' : 0
wei = x + y + jin
result = (wei % 10).toString() + result
jin = parseInt(wei / 10, 10)
i -= 1
j -= 1
}
return result
}
}