刷题之旅从数组类型的题目开始。第六道题目是加一，对应leetcode的题号为66。

image

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

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

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

示例 1:

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

示例 2:

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

解题思路

一开始琢磨半天，没看懂是啥玩意。不过如果再写一个示例就明确了：

1
2
3
输入: [1,9,9]
输出: [2,0,0]
解释: 输入数组表示数字 200。
1
2
3
输入: [9,9,9]
输出: [1,0,0,0]
解释: 输入数组表示数字 1000。

其实就是说，一个数组表示的非负整数去加一后的结果再去以一个数组来表示。由于是非负整数，那么如果第一位就是0的话，那必定就是0了，这题的难点就在于可能某个数在加一之后会增加一位，比如999是三位数，加一后就变成四位数了。那么原来长度为3的数组就不能容纳下这个长度为4的数据了。

这一道题目的思路比较巧妙，我们从最后一个数字来判断是否为9，如果不是，那么直接最后一位加一即可结束，如果最后一位是9，那么就需要改为0，然后继续判断倒数第二位，同理，倒数第二位如果不是9则加一结束，否则置为0继续往前判断。

如果在for循环中一直没出来，那么就说明提供的数字全是9，此时就需要新建一个数组了，长度为原数组加一，然后第一位置为1即可，因为其他位默认为0。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] plusOne(int[] digits) {
        //1、非空判断
        if(digits == null || digits.length <= 0){
            return digits;
        }
        for(int i=digits.length-1;i>=0;i--){
            if(digits[i] != 9){
                //2、此时只需要加一就是我们需要的最终结果，直接return
                digits[i]++;
                return digits;
            }else{
                //3、走到这里说明此时第i个元素是9，那么按照进位加一则为0，进行下一轮的判断
                digits[i] = 0;
            }
        }
        //4、如果走到这里，说明digits里面所有元素都是9，则新建数组
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}