leetcode算法-给定两个字符串形式的非负整数 num1 和

说明

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

解题：

初次看到这个题目，没有考虑到大数相加问题，所以直接的思路是：

• 字符串转化为数组，然后反转
• 循环遍历数组，从数组第二位开始，依次乘以Math.pow(10, i)

具体实现如下：

var addStrings = function (num1, num2) {
    const num1Arr = num1.split('').reverse()
    const num2Arr = num2.split('').reverse()
    let sum1 = 0
    let sum2 = 0
    for (let i = 0; i < num1Arr.length; i++) {
        if (!i) {
            sum1 += parseInt(num1Arr[i])
        } else {
            sum1 += parseInt(num1Arr[i]) * Math.pow(10, i)
        }
    }
    for (let i = 0; i < num2Arr.length; i++) {
        if (!i) {
            sum2 += parseInt(num2Arr[i])
        } else {
            sum2 += parseInt(num2Arr[i]) * Math.pow(10, i)
        }
    }
    const total = sum1 + sum2
    return total + ''
}

但是执行leetcode的测试用例，没有通过，挂在了addStrings('9333852702227987', '85731737104263')这两个数据的计算上。如下图所示：

看到这里，让我想到了这应该是大数相加的问题，那我们一起再学习一下大数相加的问题吧，然后我们再解题：

大数相加问题

因为JavaScript的Number类型是遵循IEEE 754规范表示的，这就意味着JavaScript能精确表示的数字是有限的，JavaScript可以精确到个位的最大整数是9007199254740992，也就是2的53次方，超过这个范围就会精度丢失，造成JavaScript无法判断大小，从而会出现下面的现象

Math.pow(2, 53);    // 9007199254740992
Math.pow(2, 53) === Math.pow(2, 53) + 1;    // true
9007199254740992 === 9007199254740992 + 1;    // true

在网上找了一张图，表示的比较形象，也不知道来源是哪里的，很多人的博客里都有这张图，我们也借来参考下：

从图中可以看到当正数大于2^53时，已经无法精确的表示到个位。

解决方案

解决方案思路其实比较简单，就是将字符串转换为数组，末尾对齐，数组的两两元素相加得到total，如果total大于10的话，就往下一位进1，本次计算这一位对10求余数(temp % 10) + res做拼接。最后得到的结果就是精确的。通过这个思路，可以实现下leetcode这道题，本质也是大数相加问题：

var addStrings = function (num1, num2) {
    // 数组的两两元素相加得到total，如果total大于10的话，就往下一位进total-10
    let res = ''
    let carry = 0
    let i = num1.length - 1
    let j = num2.length - 1
    while (i >= 0 || j >= 0) {
        let temp = Number(num1[i]) + Number(num2[j]) + carry
        if (i < 0) {
            temp = Number(num2[j]) + carry
            i = 0
        }
        if (j < 0) {
            temp = Number(num1[i]) + carry
            j = 0
        }
        // 从后往前记录数组的两两元素相加得到total，如果total大于10的话，下一次计算需要进1
        carry = temp >= 10 ? 1 : 0
        // 数组的两两元素相加得到total，如果total大于10的话，当前位就保留total-10(temp % 10)
        res = (temp % 10) + res
        i--
        j--
    }
    return carry > 0 ? `${carry}${res}` : `${res}`
}

执行效率如下图所示：