Problem

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Example

Given [1,2,3] which represents 123, return [1,2,4].

Given [9,9,9] which represents 999, return [1,0,0,0].

Note

进位法：设置carry位，初值为1。从digits的最低位开始循环，用当前位digits[i]与进位carry相加，结果存入cur。若cur等于10，则当前位digits[i]置0，进位carry置1，否则当前位digits[i]等于cur，carry置0，break。可以用cur % 10和cur / 10灵巧地表示digits[i]和carry。
然后讨论for循环完成或break后的carry是否为1。若为1，就是例子中[9,9,9]情况，需要更改数组长度，建立新数组res，最高位置1，剩余位按digits逐位存入；若为0，就不用讨论。

逢9化0法：从最低位开始判断该位是否为9，如果是9，化为0，继续判断上一位；如果不是9，跳出。while循环里用一个移位符号i进行标记，i等于最高位-1。只有循环到最高位0时，i才会减为-1。所以当i为－1时，意味着所有位都是9，此时和进位法一样处理，更改数组长度，建立新数组res，最高位置1，剩余位按digits逐位存入。

Solution

进位法：

public class Solution {
    public int[] plusOne(int[] digits) {
        int carry = 1;
        for (int i = digits.length-1; i >= 0; i--) {
            int cur = digits[i] + carry;
            carry = cur / 10;
            digits[i] = cur % 10;
            if (carry == 0) break;
        }
        if (carry == 1) {
            int[] res = new int[digits.length+1];
            res[0] = 1;
            return res;
        }
        return digits;
    }
}

逢9化0法：

public class Solution {
    public int[] plusOne(int[] digits) {
        int last = digits.length-1;
        while (last >= 0 && digits[last] == 9) {
            digits[last] = 0;
            last--;
        }
        if (last == -1) {
            int[] res = new int[digits.length+1];
            res[0] = 1;
            return res;
        }
        else {
            digits[last] += 1;
            return digits;
        }
    }
}