LeetCode.066.Plus One 数组加一

题目描述

66 Plus One
https://leetcode-cn.com/problems/plus-one/

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

---

解题过程

把数组表示的整数加1，注意类似 999 的情况，最高位进位1会出现长度大于原数组的情况。
时间复杂度 O(n)，空间复杂度 O(n)
其实有个很明显的剪枝优化，当进位carry为0时，可以立即结束。

看题解，排名第一的有个非常巧妙的方法，在原数组操作，不需要额外空间。
因为只求+1求余数，余数不等于0，说明没有进位，直接返回。如果余数等于0，说明有进位，遍历前一个数字，加1再求余数，以此循环。

private static class SolutionV2020 {
    public int[] plusOne(int[] digits) {
        if (null == digits || 0 == digits.length) {
            return digits;
        }
        int[] res = new int[digits.length + 1];
        int carry = 1, remain = 0;
        for (int i = digits.length -1; i >= 0; i--) {
            remain = (digits[i] + carry) % 10; // 余数
            carry = (digits[i] + carry) / 10; // 进位
            digits[i] = remain;
            res[i] = remain;
        }
        if (carry != 0) {
            res[0] = carry;
            return res;
        } else {
            return digits;
        }
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_066_PlusOne.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_066_PlusOne.java

---