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;

    }

}

巴特西

66. Plus One 数组加1

最新文章

热门文章