[LeetCode] 66. 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.

题意是给一个非空数组，表示一个数字，请对其加一。思路是从右往左扫，判断当前位置上的数字digits[i]是不是9，两种情况

第一种情况，如果digits[i]是9，就把当前位digits[i]变为0
第二种情况，就正常对当前位+1，立即退出循环，返回数组

若是第一种情况，就说明for循环一直跑到了最后，所以需要在最后开一个新数组，长度为原数组长度+1。如果是第二种情况，for循环是跑不到最后的，因为程序在做完+1的动作之后立马退出了。同时注意，当遇到9的时候，因为还是在for循环中，所以即使当前位被置为0了，他的下一位还是会被+1。

时间O(n)

空间O(n) - res数组

Java实现

 1 class Solution {
 2     public int[] plusOne(int[] digits) {
 3         // corner case
 4         if (digits == null || digits.length == 0) {
 5             return digits;
 6         }
 7 
 8         // normal case
 9         for (int i = digits.length - 1; i >= 0; i--) {
10             if (digits[i] < 9) {
11                 digits[i]++;
12                 return digits;
13             } else {
14                 digits[i] = 0;
15             }
16         }
17         int[] res = new int[digits.length + 1];
18         res[0] = 1;
19         return res;
20     }
21 }

JavaScript实现

 1 /**
 2  * @param {number[]} digits
 3  * @return {number[]}
 4  */
 5 var plusOne = function(digits) {
 6     // corner case
 7     if (digits == null || digits.length == 0) {
 8         return digits;
 9     }
10 
11     // normal case
12     for (let i = digits.length - 1; i >= 0; i--) {
13         if (digits[i] < 9) {
14             digits[i]++;
15             return digits;
16         } else {
17             digits[i] = 0;
18         }
19     }
20     let res = new Array(digits.length + 1).fill(0);
21     res[0] = 1;
22     return res;
23 };

LeetCode 题目总结