leetcode 66. Plus One 加一运算_66n.one

今天本来想做三道题目，无奈拖延症效率太低。。。
66. Plus One
Description：
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.

一开始我的思路是将数组转为数，然后加1，再拆分为新数组输出。可当数组长度太长时会超出数据范围：
int：2147483648～-2147483647 （-2^31至 2^31 - 1）；
long：-9,223,372,036,854,775,808至9,223,372,036,854,775,807(-2^63 至2^63-1)。
注意：long类型的整数常数总是以大写L或小写l结尾。

简单记录一下在用此方法时用到的求某数位数的方法：
法一：数字分割法

int num,s=0;
    scanf("%d",&num);
    while(num>0)
    {
        num=num/10;
        s++;
    }
1
2
3
4
5
6
7

法二：log10法

int num,s=0;
    scanf("%d",&num);
    s=(int)(log10(n))+1;

1
2
3
4

其实在数据变大时也想过用BigInteger,但不知为何在leetcode上好像不能用？？
下面步入正题。。。
比较好的思路是，直接对数组操作。不用把数组转为数然后在转回（增加了步骤想想就觉得麻烦，但如果数组长度不长的话这确实是一种不用动脑子的方法。。我以后要多动脑子emm…）
首先要考虑末尾进位的问题，不进位（小于9）还好说直接末尾加1返回；如果加1后进位的话还要考虑前一位. . . . .一直到首位。
分三种情况 ：

1. 例如 101 不进位加1返回
2. 例如 119 1199 进位不至首位
3. 例如 999 进至首位，还要加一位

直接上代码:

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length-1;
        for(int i=n;i>=0;i--){
            if(digits[i]<9){
                digits[i]++;
                return digits;
            }
            digits[i]=0;
        }
        int[] digits1 = new int[n+2];
        digits1[0]=1;
        return digits1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

return digits与digits[i]=0配合巧妙。