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

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

例如：

"111" + ”2222“ = ”2333“

注意：

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

附赠leetcode地址：leetcode

上代码

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+/, '')
}

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
};

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('')
};

解答：从低位开始相加

从 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

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;
};

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;
}

// 模拟小时候学习两个数相加时， 逢十进一
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
};

/**
 * 力扣415. 字符串数字相加
 * https://leetcode-cn.com/problems/add-strings/
 */
let str1 = '111'
let str2 = '2393'
const addStr = function (str1, str2) {
    let res = []
    let carry = 0
    for (let i = str1.length - 1, j = str2.length - 1; i >= 0 || j >= 0 || carry != 0; i--, j--) {
        let num1 = i < 0 ? 0 : str1[i] - '0'
        let num2 = j < 0 ? 0 : str2[j] - '0'
        let sum = (num1+num2+carry)%10
        res.unshift(sum)
        carry = Math.floor((num1+num2+carry)/10)
    }
    return res.join('')
}
console.log(addStr(str1,str2))

function charSum(num1,num2){
    let i = num1.length-1;
    let j = num2.length-1;
    let k = ''
    while(i>=0&&j>=0){
        let n1 = num1.charAt(i)%10
        let n2 = num2.charAt(j)%10
        let total =n1+n2
        k = total+k
        i--,
        j--
    }
    if(i>=0){
        k = num1.slice(0,i+1)+k
    }
    if(j>=0){
        k = num2.slice(0,j+1)+k
    }
    return k
}

console.log(charSum("111111",'2222'))

function twoSumStr(str1,str2){
    let i = str1.length-1,j=str2.length-1
    let total = ''
    while(i>=0&&j>=0){
        let c1 = (str1.charAt(i))%10
        let c2 = (str2.charAt(j))%10
        let t = c1+c2
        total=t+total
        i--
        j--
    }
    if(i>=0){
        total = str1.slice(0,i+1)+total
    }
    if(j>=0){
        total = str2.slice(0,j+1)+total
    }
    return total
}

console.log(twoSumStr("111","2222"))

Navigation Menu

Repository navigation

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

解答：从低位开始相加

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

ricosmall commented on May 6, 2020

mingju0421 commented on May 6, 2020

hecun0000 commented on May 6, 2020

sisterAn commented on May 6, 2020

解答：从低位开始相加

13001920223 commented on May 7, 2020

itxuye commented on May 8, 2020

qianlongo commented on Aug 16, 2020

xllpiupiu commented on Oct 6, 2021

AlexZhang11 commented on May 24, 2024

AlexZhang11 commented on May 31, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions