如何实现两个大数相乘

思路：开始有点懵，之前做过两个数相加，但是还真没遇到到相乘的情况， 顺着相加的思路做。 采用模拟竖式的方式写算法

1. 常规乘法是，第二个数的从后往前每个数和第一个数从后往前相乘，然后取模放到对应位置，如果有进位，下次乘完再加上上次的进位
2. 第二个数二位乘完之后的结果正好比上一个结果要向前错一位，依此类推
3. 将每次乘完的结果相加，这里就转换成了多个大数相加，此时可以乘完一轮就加，就变成两数相加了

算法实现

1. 对字符串分割，便于遍历

由于两个数量可能不等，所以要取两个数最大的位数，不满足的需要补充0，以便遍历的时候位数可以对齐，相关代码如下

  const max = Math.max(num1.length, num2.length);
  const arr1 = `${num1}`.padStart(max, "0").split("");
  const arr2 = `${num2}`.padStart(max, "0").split("");

2. 模拟相乘，循环两个数的位数，双层循环，遍历所有位

  for (let i = arr1.length - 1; i >= 0; i--) {
    const oneResult = [];//存放每一轮的计算结果
    pre = 0;
    for (let k = arr2.length - 1; k >= 0; k--) {
      let total = ~~arr1[i] * ~~arr2[k] + ~~pre;//这里要加上上一轮的进位pre
      const mod = total % 10;
      pre = ~~(total / 10);
      oneResult.unshift(mod);//放到计算结果里，从前面插入
      if (k == 0 && pre) {//考虑到最后可能还是有进位，所以最后一次遍历如果还有进位则需要把进位插入到最前面
        oneResult.unshift(pre)
      }
    }
    // ...略
  }

3. 下一次循环要向前错一位

所以错过之后，后面的位数要补0

因为循环是从后往前循环，所以索引是递减，但是错位的0是递增，所以补0的索引要用当前总索引数减去当前循环的索引值，得到需要补充0的个数，然后遍历补充0

   let j = arr1.length - 1 - i;
    while (j != 0) {
      oneResult.push("0"); //尾部补0 为了错位叠加
      j--;
    }

4. 将上一次得到的结果和本轮结果叠加，得到最终结果

    result = add(result.join(""), oneResult.join("")).split("");

叠加的算法就是两数之和了，是另外一个题 了

两数之和与两数之积不同的是，只有一次循环

两数之和算法如下：

 const add = (num1, num2) => {
  const max = Math.max(num1.length, num2.length);
  const arr1 = `${num1}`.padStart(max, "0").split("");
  const arr2 = `${num2}`.padStart(max, "0").split("");
  const result = [];
  let pre = 0;//每次循环之后一定要重制一下进位
  for (let i = arr1.length - 1; i >= 0; i--) {
    const total = ~~arr1[i] + ~~arr2[i] + ~~pre;
    const mod = total % 10;
    pre = ~~(total / 10);
    result[i] = mod;
  }
  if (pre) {
    result.unshift(pre);
  }

  //去除前缀0
  for (let i = 0; i < result.length; i++) {
    if (~~result[i] == 0) {
      result.shift();
      i--;
    } else {
      break;
    }
  }
  return result.join("");
};

待改进

算法效率不高，比较耗时

完整代码请参考：

手写实战github仓库

leetcode原题