Facebook&字节&leetcode415：字符串相加

[sisterAn]

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

例如：

"111" + ”2222“ = ”2333“

注意：

• num1 和 num2 的长度都小于 5100
• num1 和 num2 都只包含数字 0-9
• num1 和 num2 都不包含任何前导零
• 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

附赠leetcode地址：leetcode

[ricosmall]

上代码

function add(str1, str2) {
  let result = ''
  let tempVal = 0
  let arr1 = str1.split('')
  let arr2 = str2.split('')

  while (arr1.length || arr2.length || tempVal) {
    tempVal += ~~arr1.pop() + ~~arr2.pop()
    result = tempVal % 10 + result
    tempVal = ~~(tempVal / 10)
  }

  return result.replace(/^0+/, '')
}

[mingju0421]

var addStrings = function(num1, num2) {
    let a = num1.length, b = num2.length, result = '', sum = 0
    while(a || b) {
        a ? sum += +num1[--a] : ''
        b ? sum +=  +num2[--b] : ''
        
        result = sum % 10 + result
        if(sum > 9) sum = 1
        else sum = 0
    }
    if (sum) result = 1 + result
    return result
};

[hecun0000]

var addStrings = function (num1, num2) {
  var arr1 = num1.split('').reverse()
  var arr2 = num2.split('').reverse()
  var length = Math.max(num1.length, num2.length)

  var res = []
  for (var i = 0; i < length; i++) {
    var item1 = Number(arr1[i]) || 0
    var item2 = Number(arr2[i]) || 0
    var num = res[i] || 0

    var sum = item1 + item2 + num

    res[i] = sum % 10

    var zheng = Math.floor(sum / 10)
    if (zheng > 0) res.push(zheng)
  }

  return res.reverse().join('')
};

[sisterAn]

解答：从低位开始相加

• 从 num1 ，num2 的尾部开始计算，模拟人工加法，保存到 tmp 中；

• 计算 tmp 的个位数，并添加到 result 的头部，这里的 result 是 string 类型，不是 number 类型；

• 计算进位，改成 tmp，进行下次循环

• 索引溢出处理：循环结束，根据 tmp 判断是否有进位，并在 result 头部添加进位 1

• 返回 result

代码实现：

var addStrings = function(num1, num2) {
    let a = num1.length, b = num2.length, result = '', tmp = 0
    while(a || b) {
        a ? tmp += +num1[--a] : ''
        b ? tmp +=  +num2[--b] : ''
        
        result = tmp % 10 + result
        if(tmp > 9) tmp = 1
        else tmp = 0
    }
    if (tmp) result = 1 + result
    return result
};

复杂度分析：

• 时间复杂度 O(max(M,N))
• 空间复杂度 O(1)

leetcode

[13001920223]

1、新建立双指针 i 、j，倒序循环两个数组
2、判断两数相加是否大于10，大于则进1，缓存 (result % 10)
3、循环结束判断move是否有值，有则加上，没有直接return
空间复杂度: 循环num1， num2，则空间复杂度O(n)
空间复杂度: result缓存结果，常数级复杂度O(1)

var addStrings = function(num1, num2) {
    var i = num1.length - 1,
        j = num2.length - 1,
        move = 0,
        result = '';
    while (i >= 0 || j >= 0) {
        n1 = i >= 0 ? num1[i] : 0;
        n2 = j >= 0 ? num2[j] : 0;
        var tmp = +n1 + +n2 + move;
        move = tmp >= 10 ? 1 : 0;
        result = (tmp % 10) + result;
        i--;
        j--
    }
    return move ? move + result : result;
};

[itxuye]

function add(num1, num2) {
  const alength = num1.length;
  const blength = num2.length;
  const maxLength = Math.max(alength, blength);
  if (alength > blength) {
    num2 = `${new Array(alength - blength).fill('0').join('')}${num2}`;
  } else {
    num1 = `${new Array(blength - alength).fill('0').join('')}${num1}`;
  }
  let t = 0;
  let f = 0;
  let sum = '';
  for (let i = maxLength - 1; i >= 0; i--) {
    t = parseInt(num1[i]) + parseInt(num2[i]) + f;
    f = Math.floor(t / 10);
    sum = (t % 10) + sum;
  }
  if (f == 1) {
    sum = '1' + sum;
  }
  return sum;
}

[qianlongo]

// 模拟小时候学习两个数相加时， 逢十进一
var addStrings = function(num1, num2) {
  let result = ''
  let i = num1.length - 1
  let j = num2.length - 1
  let flag = 0 // 进位
  let sum = 0

  while (i >=0 || j >= 0 || flag) {
    let n1 = +num1[ i-- ] || 0
    let n2 = +num2[ j-- ] || 0

    sum = n1 + n2 + flag

    if (sum >= 10) {
      sum -= 10
      flag = 1
    } else {
      flag = 0
    }

    result = sum + '' + result
  }

  return result
};