43.multiply-strings.md

字符串相乘

题目

思路

num1和num2的长度小于110, 说明这两个数可能会非常大, 很容易会超出范围计算.

因此需要一个基于字符串的数字相加和相乘, 保证数字范围不超出最大值.

乘法的思路大致如下, 以下用 12 * 34 来做例子

1. 将 12, 34 两个字符串分为 (1 * 10 + 2) * (3 * 10 + 4)
2. 按照乘法分配律和结合律, 得到以下算法, 得到以下内容
3. (1 * 3) * 10 * 10 + 1 * 4 * 10 + 2 * 3 * 10 + 2 * 4
4. 得到最终的结果 408

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
  const num1Arr = num1.split('')
  const num2Arr = num2.split('')

  num1Arr.reverse()
  num2Arr.reverse()

  const num1Length = num1Arr.length
  const num2Length = num2Arr.length

  let result = '0'

  for (let i = 0; i < num1Length; i++) {
    for (let j = 0; j < num2Length; j++) {
      let tmp = Number(num1Arr[i]) * Number(num2Arr[j])
      if (tmp > 0) {
        tmp = tmp + ''.padEnd(i + j, '0')
      }

      result = addStrings(tmp + '', result)
    }
  }

  return result
};
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
  const num1Length = num1.length
  const num2Length = num2.length
  const maxLength = num1Length > num2Length ? num1Length : num2Length
  const num1Arr = num1.split('')
  const num2Arr = num2.split('')
  /** 数组反转. 之后好操作 */
  num1Arr.reverse()
  num2Arr.reverse()
  /** 进位 */
  let carry = false
  let results = []
  for (let i = 0; i < maxLength; i++) {
    const tmp = Number(num1Arr[i] || 0) + Number(num2Arr[i] || 0) + (carry ? 1 : 0)
    carry = tmp > 9
    /** 直接将值传到数组头部. 省去反转操作 */
    results.unshift(carry ? tmp - 10 + '' : tmp + '')
  }
  if (carry) {
    /** 进位符号如果还存在, 还得推送个1进来 */
    results.unshift('1')
  }
  return results.join('')
};