算法题3-加一

题目链接：https://leetcode-cn.com/problems/plus-one/
第一种：
这个题要考虑三种情况：
1.加1之后一直到最高位都产生了进位。例如99→100。
2.加1之后产生了进位，但是在中途中断了。例如209→210
3.最简单的一种情况：当前位数值加1之后，没有产生进位。例如20→21
考虑这三种情况，我们可以写出代码：

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        int index = len-1;
        while(true) {
            //一直到第一位都有进位的情况，比如9,99,999……
            if(index == 0 && digits[index] ==9) {
                digits = new int[len+1];
                digits[0] = 1;
                return digits;
            }
            //有进位就将此下标对应值设为0，循环到前一位进行加1
            else if (digits[index]  == 9) {
                digits[index] = 0;
                index--;
            }
            //当前位没有进位的情况
            else  {
                digits[index]++;
                return digits;
            }
        }
    }
}

第二种：
我们可以考虑利用for循环，当末位加1之后，对10进行取余，
如果余数不为0，说明没有进位，直接返回结果即可；
如果余数为0，说明产生了进位，那么循环到前一位进行加1，再取余判断是否有进位。
如果直到最高位加1之后都有进位，那么可以申请一个长度为length+1的数组，将最高位设为1，其他为默认为0.

class Solution {
    public int[] plusOne(int[] digits) { 
        int len=digits.length;
        for(int i=len-1;i>=0;i--) {
            digits[i]++;
            //对10取余数
            digits[i] %= 10;
            //如果余数不为0，说明没有进位，返回digits即可，
            //如果余数为0，下一个循环将前一位加1，再判断有无进位
            if(digits[i] != 0){
                return digits;
            }    
        }
        //如果一直到第一位都有进位，比如9,99,999……这些情况
        //申请一个length+1大小的数组，将第一位置为1，其他为默认为0
        digits = new int[len+1];
        digits[0] = 1;
        return digits;
    }
}

时间复杂度都是O(n).