66. Plus One 数组加1

［抄题］：

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

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

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

给定 [1,2,3] 表示 123, 返回 [1,2,4].

给定 [9,9,9] 表示 999, 返回 [1,0,0,0].

[暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道对进不进位如何分类。提前return就无忧了

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

不需要对answer数组的后面若干位赋值了，初始化时自动=0。感觉是针对此题特殊的
有角标循环的时候，提前备注：0- n-1，无论正序、倒序

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

备注0 to n -1

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }else {
                digits[i] = 0;
            }
        }

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

369. Plus One Linked List dummynode要想到，两根指针也行我还是太天真

[代码风格] ：

public class Solution {
    /**
     * @param digits: a number represented as an array of digits
     * @return: the result
     */
    public int[] plusOne(int[] digits) {
        //not carry
        int n = digits.length;
        //0 to n-1 whenever
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }else {
                digits[i] = 0;
            }
        }
        //carry, need new array
        int[] answer = new int[n + 1];
        answer[0] = 1;
        return answer;
    }
}

View Code