leetcode66.将数组表示的非负整数加一

发表于 更新于 分类于 ，

题目要求：一个非负整数被表示为一个数组，数组中每一个元素代表该整数的一个位。数组的下标越小，代表的位数越高。现在对该数组做加一运算，请返回结果数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @author rale
 *
 * Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
 * You may assume the integer do not contain any leading zero, except the number 0 itself.
 * The digits are stored such that the most significant digit is at the head of the list.
 */
public class PlusOne {

    public int[] plusOne(int[] digits) {
        //此处可以直接将carry（进位）设置为1，优化程序
        //carry = 0
        //digits[digits.length-1] += 1 ;
        int carry = 1;
        int temp = 0;
        for(int i=digits.length-1 ; i>=0 ; i--){
            temp = digits[i] + carry;
            digits[i] = temp%10;
            carry = temp/10;
        }
        if(carry>0){
            int[] result = new int[digits.length+1];
            result[0] = 1;
            for(int j = 1 ; j<result.length ; j++){
                result[j] = digits[j-1];
            }
            return result;
        }
        return digits;
    }
}

继续优化
只有当需要进位的时候，加法才需要继续下去，否则加法则可以在当前位停止。
可以在循环中添加判断，若carry==0，则提前跳出循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @author rale
 *
 * Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
 * You may assume the integer do not contain any leading zero, except the number 0 itself.
 * The digits are stored such that the most significant digit is at the head of the list.
 */
public class PlusOne {

    public int[] plusOne(int[] digits) {
        //此处可以直接将carry（进位）设置为1，优化程序
        //carry = 0
        //digits[digits.length-1] += 1 ;
        int carry = 1;
        int temp = 0;
        for(int i=digits.length-1 ; i>=0 ; i--){
            temp = digits[i] + carry;
            digits[i] = temp%10;
            carry = temp/10;
            if(carry==0){
                break
            }
        }
        if(carry>0){
            int[] result = new int[digits.length+1];
            result[0] = 1;
            for(int j = 1 ; j<result.length ; j++){
                result[j] = digits[j-1];
            }
            return result;
        }
        return digits;
    }
}

再再再次优化
此处优化最高位进位的情况
最高位出现进位，当且仅当其他位都产生进位且为0
优化后的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @author rale
 *
 * Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
 * You may assume the integer do not contain any leading zero, except the number 0 itself.
 * The digits are stored such that the most significant digit is at the head of the list.
 */
public class PlusOne {

    public int[] plusOne(int[] digits) {
        int carry = 1;
        int temp = 0;
        for(int i=digits.length-1 ; i>=0 ; i--){
            temp = digits[i] + carry;
            digits[i] = temp%10;
            carry = temp/10;
        }
        if(carry>0){
            int[] result = new int[digits.length+1];
            result[0] = 1;
//          最高位进位的情况只有一种，即其它位均进位且为0，无需再循环一次
//            for(int j = 1 ; j<result.length ; j++){
//                result[j] = digits[j-1];
//            }
            return result;
        }
        return digits;
    }    
}