01.plus-one.md

66.加一

https://leetcode-cn.com/problems/plus-one

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

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

思路

在数组上做竖式加法，用 carry 来表示进位，反向遍历数组即可。

遍历结束条件：

1. 数组所有元素都遍历过了
2. 当 carry 为 0 的时候

需要注意的点：

如果遍历结束后 carry 大于 0，还需要在数组前面补一位。

复杂度

• 时间复杂度：$O(N)$, N 为数组长度。
• 空间复杂度：$O(1)$。

代码

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
    let carry = 1,
        sum = 0,
        index = digits.length - 1;

    while (carry > 0 && index > -1) {
        sum = digits[index] + 1;
        carry = Math.floor(sum / 10);
        digits[index] = sum % 10;
        index--;
    }

    carry && digits.unshift(carry);

    return digits;
};