LeetCode解题记录（六）

由浅入深，由易到难

数组篇 （简单）五
66.加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

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

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

示例 1:

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

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

看到题目后第一感觉是有两种方案。
1.直接在数组里改变。对于不需要进位的数组，直接在最末尾加1，但碰到需要进位的就很麻烦。。。
2.把数组变成数字，加1，再转回数组。下附算法。

class Solution {
    public int[] plusOne(int[] digits) {      
     int sum=0,multiply=1, l=digits.length-1;
     while(l>-1)
     {
         sum=sum+digits[l]*multiply;
         l--;
         multiply=multiply*10;
     }                                     //sum是数组转换后的数字
        sum++;
        int len=0,copy=sum; //计数
        while(copy>=1) 
        {
             copy/=10; 
             len++;                    //len是新数字的位数，记录下来用于设置新数组
        }                
        int[] a=new int [len];
        while(len>0)
        {
            
            a[len-1]=sum%10;
            sum=sum/10;
            len--;
        }
        return a;
    }
}

尴尬的是这种方法貌似有局限性，当数组位数太大的时候数字似乎就溢出了。。。over

正解：

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;        //用来处理数组元素为10的时候，让它变成0，等于digits[i]=digits[t]==10？0:digits[t]
            if (digits[i] != 0) return digits;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

其实还是和我的第一种想法一样，不过我没想到怎么处理进位的问题。题解很巧妙，最简单的情况，如1,2,3不需要进位，执行完加1，在if语句里判断元素不等于0，直接跳出循环。要进位，但不需要增加位数的情况，如1，0，9，9，会多执行几次for循环，到第三次执行的时候，if也为真了，跳出循环。最极端的情况是需要进位，如9,9，这时候for循环执行完毕，数组变成了0,0，新定义长一位的数组，并使最高位为1。