跳转至

66.加一

题目描述

原题

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

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

你可以假设除了整数 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，并取得进位值carry。然后再遍历剩余的数字。并依次赋新值。遍历判断carry是否为0，如果不为0，则需要创建一个比原数组长度+1的新数组，并全部向右移位，0的位置赋值1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public static int[] plusOne(int[] digits){
    int len = digits.length;
    int carry = 1;
    for (int i = len - 1; i >= 0; i--) {
        digits[i] += carry;
        if(digits[i] == 10){
            carry =1;
            digits[i] = 0;
        }else{
            return digits;
        }
    }
    //全是9的情况
    digits = new int[len +1];
    digits[0] = 1;
    return digits;
}

优化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public int[] plusOne(int[] digits) {
    int len = digits.length;//数组长度
    for (int i = len - 1; i >= 0; i--) {
        //digits[len-1]是+1操作，其他是进位操作
        //这一步比较不好理解，如果遇到不是0的直接return了
        //如果是等于0，则需要进位每一位都++，直到遇到不需要进位的
        digits[i]++;
        digits[i] %= 10;
        //等于0，说明需要进位，
        //不等于0，则说明不需要进位直接返回数组
        if (digits[i] != 0) {
            return digits;
        }
    }
    //创建新的数组，其实不需要移位，因为其他位都是0
    //所以直接创建新数组并把首位赋值为0
    digits = new int[len + 1];
    digits[0] = 1;
    return digits;
}