加一算法 - wpsshop博客

题目：


给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
 
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
 
你可以假设除了整数 0 之外，这个整数不会以零开头。
复制代码

分析：

其实就是用数组来保存 10 进制数，并且实现对这个 10 进制数的加 1 算法。

比如：


输入: [9]
输出：[1, 0]
 
输入: [1, 2, 3]
输出：[1, 2, 4]
复制代码

解题

看到这个题目的时候，我很简单的想把数组转成字符串然后再转成数字进行操作，写了如下代码：


function plusOne (digits) {
    const num = Number(digits.join('')) + 1
    return num.toString().split('')
}
复制代码

代码很简单，简单测试了一下上面的两个测试用例发现没有问题，便提交了。但是，这就是悲剧了，这道题目还是有个很明显陷阱的：


输入： [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3]
输出： [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,0,0,0]
预期： [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,4]
复制代码

我们看到这里数组 [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3] 的长度超过了 js 可表示最大精度的长度 16


Number.MAX_SAFE_INTEGER.toString().length
=> 16
复制代码

所以上面这种单纯的通过数字计算方式并不正确，因而我们还是通过简单遍历数组的方式进行求解。

这里有几个需要注意的点：

要从数组的尾部开始遍历
每一位计算时需要知道上一位是否有进位
每一位值保存个位数
遍历完成之后还需要判断是否顶上一位数字计算也有进位

代码如下：


function plusOne (digits) {
    // 默认最后一位加 1
    let is_plus = true
    const first_index = digits.length - 1
    for (let i = first_index; i >=0; i--) {
        if (is_plus) {
            digits[i]++
        }
        is_plus = digits[i] >= 10
        if (is_plus) {
            digits[i] %= 10
        }
    }
    // 判断是否还有存留进位
    if (is_plus) {
        digits.unshift(1)
    }
    return digits
}
复制代码

总结

解题时不要想当然，面对数字计算问题一定要注意精度丢失问题。