字符串相乘

题目

大数相乘, 本题为 415-大数相加 的进阶版.

提示:

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成
• num1 和 num2 都不包含任何前导零, 除了数字 0 本身.

题解

  1  2  3
     6  4
----------
  4  8  12
6 12 18
----------
6 16 26 12

1. 按上图声明一个数组, 数组初始化的长度为 num1.length + num2.length - 1
2. 双循环按位相乘, 并加和把结果存到数组中: arr[i + j] += +num2[i] * +num1[j]
3. 使用两数相加的套路完成数字字符串的组装

JavaScript

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {
  // 排除等于 0 的情况, 就不往下折腾了
  if (num1 === '0' || num2 === '0') return '0'

  const m = num1.length
  const n = num2.length

  const arr = new Array(m + n - 1).fill(0)

  // 做双循环, 保证每个位置都能乘在一起
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      // 按位加和, 注意这里的加和可能会超过 10, 甚至更多. 不过暂时不用 care, 下面再处理进位问题
      arr[i + j] += +num2[i] * +num1[j]
    }
  }

  let str = ''
  let carry = 0

  // 处理进位
  for (let k = arr.length - 1; k >= 0; k--) {
    const sum = arr[k] + carry

    // 将小于 10 的部分作为最终该位的结果
    str = (sum % 10) + str

    // 将大于 10 的部分作为 carry 往前赶
    carry = (sum / 10) | 0
  }

  // 考虑结束循环仍有进位的情况, 把 carry 放到最前面即可
  return carry > 0 ? carry + str : str
}

Rust

pub fn multiply(num1: String, num2: String) -> String {
    if num1 == String::from("0") || num2 == String::from("0") {
        return String::from("0");
    }

    let (m, n) = (num1.len(), num2.len());
    let mut arr = vec![0;  m + n - 1];

    for (i, byte1) in num1.as_bytes().iter().enumerate() {
        for (j, byte2) in num2.as_bytes().iter().enumerate() {
            arr[i + j] += (byte1 - b'0') as i32 * (byte2 - b'0') as i32;
        }
    }

    let mut str = String::from("");
    let mut carry = 0;
    for k in (0..=(arr.len() - 1)).rev() {
        let sum = arr[k] + carry;
        str = (sum % 10).to_string() + &str;
        carry = sum / 10;
    }

    if carry != 0 {
        carry.to_string() + &str
    } else {
        str
    }
}