leetcode415 大数相加

题目

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。返回的形式是字符串

解法一：split+reverse+竖式加法

使用split将字符串分割成数组，并使用reverse进行数组翻转，进行竖式相加，注意进位。将每次个位数计算结果保存至结果数组中，最后翻转输出。

举个例子来描述处理过程：

num1 "123459" ;

num2 "123"

两个数组翻转后:

num1 "954321"

num2 "321"

此时个位对齐，直接相加，注意保存进位即可。

当两个字符串长度有两种情况，一致、不一致，需要分情况考虑。

1. 当一致时，直接对齐相加，最后判断add是否等于0，不为0存入结果数组。

2. 当不一致时，需要对更长的字符串进行特殊处理：

   1. 当前处于最后一个字符，当前数+ add存入结果数组
   2. 不处于最后一个数组，（当前数组+ add）%10 存入结果数组，计算进位。

var addStrings = function (num1, num2) {
  var arr1 = num1.split('').reverse();
  var arr2 = num2.split('').reverse();
  var len1 = arr1.length;
  var len2 = arr2.length;
  var shortArr, shortLen, longArr, longLen;
  var result = [];
  var add = 0;
  if (len1 < len2) {
    shortArr = arr1;
    shortLen = len1;
    longArr = arr2;
    longLen = len2;
  } else {
    shortArr = arr2;
    shortLen = len2;
    longArr = arr1;
    longLen = len1;
  }
  for (let i = 0; i < shortLen; i++) {
    var cal = parseInt(shortArr[i]) + parseInt(longArr[i]) + add;
    var temp = cal % 10;
    result.push(temp);
    add = Math.floor(cal / 10);
  }
  if (longLen === shortLen) {
    if (add !== 0) {
      result.push(add);
    }
  } else {
    for (let i = shortLen; i < longLen; i++) {
      if (i === longLen - 1) {
        var temp = parseInt(longArr[i]) + add;
        result.push(temp);
      } else {
        var cal = parseInt(longArr[i]) + add
        var temp = cal % 10;
        result.push(temp);
        add = Math.floor(cal / 10);
      }
    }
  }
  return result.reverse().join('');
};


console.log(addStrings("123", "123"));

解法二：reverse + 竖式加法 + 缺位补零

竖式加法：相同数位对齐，从低到高逐位相加，如果当前位和>10，则向高位进位。

代码实现：

1. 我们定义两个指针i 和 j分别指向两个字符串的末尾，即最低位。
2. 同时定义一个变量add 维护当前是否有进位，然后从末尾到开头逐位相加即可。
3. 因为两个字符串长度不一定相同，故我们采取当前下标处于负数的时候自动补零的方法，处理位数不同的问题。

var addStrings = function (num1, num2) {
  var i = num1.length - 1; j = num2.length - 1;
  var add = 0;
  var result = [];
  while (i >= 0 || j >= 0 || add !== 0) {
    //补位
    var x = i >= 0 ? num1[i] - '0' : 0;
    var y = j >= 0 ? num2[j] - '0' : 0;
    var temp = x + y + add;
    result.push(temp % 10);
    add = Math.floor(temp / 10);
    i -= 1;
    j -= 1;
  }
  return result.reverse().join('');
}

总的来说，2比1优雅，且快。