LeetCode-字符串相乘

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the input>integer directly.

---

这道题乍一看不难，只是将两个以字符串表示的数字相乘并返回字符串表示的结果而已。
开始想法是，从低位往高位循环扫描两组数字，同时累乘以10进位，边相乘边向结果累加，最后将结果通过.toString()转为字符串类型。很快代码如下：

var multiply = function(num1, num2) {
  if(num1 === '0' || num2 === '0') {
    return "0";
  }
  var res=0,tmp1,tmp2,pos1=1,pos2=1;
  for(var i=num1.length-1;i>=0;i--) {
    tmp1=parseInt(num1[i])*pos1;
    pos2=1;
    for(var j=num2.length-1;j>=0;j--) {
      tmp2=parseInt(num2[j])*pos2;
      res+=tmp1*tmp2;
      pos2=pos2*10;
    }
    pos1=pos1*10;
  }
  return res.toString();
};

不过提交时报错：

最后一位出错，又在终端确认了遍，不是程序本身计算错误：

> 123456789*987654321
121932631112635260

应该是大数已经超出JS能表达的精度了，《JavaScript权威指南》3.1小节中指出

JavaScript中所有的数字用浮点数值表示，其采用64位浮点格式表示数字，能表示的最大值 ±1.7976931348623157 x 10^308，最小值为 ±5 x 10^-324。
对于整数而言，其按照54位计算最大最小数，否则会丧失精度，表示的整数范围是-−9007199254740992 ~ 9007199254740992（即-2^52~2^53） 。对于某些操作（数组索引和位操作）是按照32位处理的。

对于题目中的case，已经超出JavaScript能表示的整数范围，故必须用数组或字符串来直接存储计算结果，另外参考github中牛人的代码，以数组存储相乘结果，i+j+1位存储对应位相乘的各位，i+j位存储进位，每次进行累加，最后将第一位非零数以后的数组转化为字符串返回，代码如下：

var multiply = function(num1, num2) {
  if(num1 === '0' || num2 === '0') {
    return "0";
  }
  var num1Len = num1.length, num2Len=num2.length;
  var result = new Array(num1Len+num2Len).fill(0);
  // use res[i+j+1] to store the single digits, num[i+j] to store carry
  var tmp;
  for(var i=num1Len-1;i>=0;i--) {
    for(var j=num2Len-1;j>=0;j--) {
      tmp = parseInt(num1[i])*parseInt(num2[j]);
      result[i+j+1] += tmp;
      if(result[i+j+1]>=10) {
        result[i+j] += parseInt(result[i+j+1]/10);
        result[i+j+1] = parseInt(result[i+j+1]%10);
      }
    }
  }
  var resultString = "";
  for(i=0;i<result.length;i++) {
    if(resultString==="" && result[i] === 0) {
      continue;
    }
    resultString += result[i];
  }

  return resultString;
};

该题主要是注意JavaScript大数范围会超限，需要以其他数据结构来存储结果。