加一

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

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

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

示例 1:

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

示例 2:

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

很明显，这道题需要考虑 9+1=10，即类似于“进位”的情况。我一开始想的一种较笨的算法：

    public static int[] plusOne(int[] digits) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < digits.length; i++) {
            list.add(digits[i]);
        }
        Collections.reverse(list);

        boolean isContinue = true;
        for (int i = 0; i < list.size(); i++) {
            if (isContinue) {
                if ((list.get(i) + 1) > 9) {
                    list.set(i, 0);
                    if (i + 1 == list.size()) {
                        list.add(1);
                        isContinue = false;
                    } else {
                        isContinue = true;
                    }
                } else {
                    list.set(i, list.get(i) + 1);
                    isContinue = false;
                }
            }
        }

        Collections.reverse(list);
        int[] arrNew = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arrNew[i] = list.get(i);
        }
        return arrNew;
    }

参考别人的的算法：

    public static int[] plusOne2(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }

注意一个关键的细节，就是当你 new 一个int[] 后，每一个数组元素初始值皆为 0，这刚好符合这道题中遇到需要“进位”的情况，第二种算法正好利用了这一特点。