LeetCode66——加一

LeetCode66——加一

题目描述：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

示例：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123

输入：digits = [1,9]
输出：[2,0]
解释：输入数组表示数字 19

输入：digits = [8 ,9，9, 9]
输出：[9 ,0，0 ,0]
解释：输入数组表示数字 8999

输入：digits = [9 ,9，9, 9]
输出：[1，0 ,0，0 ,0]
解释：输入数组表示数字 9999

思路：

1.末尾没有9——直接末尾元素加一即可加一

2.末尾有9——逆序找第一个不为9的元素并且将其加一 ，后面都变成0

3.全是9——新建个长度为原来数组长度+1的新数组{1,0,0,0,0…}即可

4.模拟实现数字进位

Result01

   public static int[] addOne(int[] arr){
        //初始i指向数组最后一个元素  逆序找第一个不为9的数字
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] != 9) {//找到了不为9的元素 加一即可
                arr[i]++;
                //加一之后    后面全部置为0
                for (int j = i + 1; j < arr.length; j++) {
                    arr[j] = 0;
                }
                return arr;
            }
        }
        //执行到这的时候说明未执行if (arr[i] != 9) return arr，证明数组中的元素全都是9
        // arr 中所有的元素均为 9 加一之后 新创建一个数组返回即可
        int[] ans = new int[arr.length + 1];
        ans[0] = 1;
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行结果;

Result02

public static int[] addOne(int[] arr) {
        //模拟现实数字进位的机制
        for (int i = arr.length - 1; i >= 0; i--) {
            arr[i]++;
            //这一步对 10 取模 因为数组中每个元素只存储单个数字 所以只有9+1 模 10 ==0 其余的数字加一之后模10 都还是其本身
            arr[i] = arr[i] % 10;
            //如果进位之后模10不等于0 证明其是小于9的数 直接返回数组
            if (arr[i] != 0){
                return arr;
            }
        }
        //运行到这里的时候 说明进位后全为0 ，即原来数组的元素全是9 ，所以要新建数组
        arr = new int[arr.length + 1];
        arr[0] = 1;
        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16