12.大数相乘

题目

给定两个以字符串形式表示的非负整数 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）或直接将输入转换为整数来处理。

code1（竖式乘法）

// 经典竖式乘法：
// 999
// 234
//------------------
// 999 * 4  -->      3996
// 999 * 3  -->     29970
// 999 * 2  -->  + 199800
//--------------------------------
//                 result

/**
 * 实现一个字符串和一个字符的乘法
 * @param {*} s1 
 * @param {*} ch 
 */
function simpleMultiply(s1, ch) {
  // 保存字符与字符的乘积
  let product = 0
  // 保存进位
  let carry = 0
  // 保存结果的数组
  const res = []
  for (let i = s1.length - 1; i >= 0; i--) {
    product = +s1[i] * +ch + carry
    if (product > 9) {
      carry = parseInt(product / 10)
    } else {
      carry = 0
    }
    res.unshift(product % 10)
  }
  if (carry)  res.unshift(carry)

  return res.join('')
}

/**
 * 实现两个字符串的加法
 * @param {*} s1 
 * @param {*} s2 
 */
function twoNumberSum(s1, s2) {
  // 这个下标用来辅助补0
  let cur = 0
  while (cur < s1.length || cur < s2.length) {
    if (!s1[cur]) {
      s1 = '0' + s1
    }
    if (!s2[cur]) {
      s2 = '0' + s2 
    }
    cur++
  }
  // 保存进位
  let carry = 0
  // 保存结果的数组
  const res = []
  // 一次计算的和
  let sum = 0
  for (let i = s1.length - 1; i >= 0; i--) {
    sum = +s1[i] + +s2[i] + carry
    if (sum > 9) {
      carry = 1
    } else {
      carry = 0
    }
    res.unshift(sum % 10)
  }
  if (carry)  res.unshift(carry)
  return res.join('')
}

/**
 * 实现两个字符串的乘法
 * @param {*} s1 
 * @param {*} s2 
 */
function multiply(s1, s2) {

  if (s1 === '0' || s2 === '0') return '0'

  s2 = s2.split('')

  let ch = ''
  // 乘积
  let product = ''
  // 进位
  let carry = ''
  // 上一次乘积 + 当前这次乘积的结果
  let total = ''
  while ((ch = s2.pop()) !== undefined) {
    product = simpleMultiply(s1, ch) + carry
    total = twoNumberSum(total, product)
    carry = '0' + carry
  }
  return total
}

code2 （优化版竖式乘法）

test.png

function multiply(s1, s2) {
  if (s1 === '0' || s2 === '0') return '0'
  // 结果数组最多有 s1.length + s2.length 位
  const res = new Array(s1.length + s2.length).fill(0)
  let sum = 0

  for (let i = s1.length - 1; i >= 0; i--) {
    let a = +s1[i]
    for (let j = s2.length - 1; j >= 0; j--) {
      let b = +s2[j]
       // 核心算法
      sum = res[i + j + 1] + a * b
      res[i + j + 1] = sum % 10
      // `| 0` 在这里的意思是对前面的数值进行取整
      res[i + j] = res[i + j] + sum / 10 | 0
    }
  } 

  if (res[0] === 0) res.shift() 
  
  return res.join('')
  
}