【算法】【线性表】Plus One-526互联

1 题目

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.

2 解答

主要是考虑进位：

class Solution {
    public int[] plusOne(int[] digits) {
        // 参数校验
        if (digits == null || digits.length <= 0) {
            return digits;
        }
        // 取出末尾数字 + 1
        int len = digits.length;
        int lastNum = digits[len - 1] + 1;
        // 如果小于10 那么直接塞回去返回
        if (lastNum < 10) {
            digits[len - 1] = lastNum;
            return digits;
        }
        // 这里就是大于10 要进位
        // 先设置末尾为0
        digits[len - 1] = 0;
        // 是否需要前插1
        boolean firstAddFlag = false;
        // 如果数组长度为1 那么需要
        if (len == 1) {
            firstAddFlag = true;
        } else {
            // 如果长度大于1，就遍历, 从倒数第二位开始
            for (int i = len - 2; i >= 0; i--) {
                int num = digits[i] + 1;
                // 如果超过10
                if (num >= 10) {
                    // 当前位置设置为 0
                    digits[i] = 0;
                    // 如果到头了，那么就需要前插1，否则继续向前
                    if (i == 0) {
                        firstAddFlag = true;
                    } 
                } else {
                    digits[i] = num;
                    break;
                }
            }
        }
        // 需要前插1
        if (firstAddFlag) {
            int[] res = new int[len + 1];
            res[0] = 1;
            for (int i = 1; i <= len; i++) {
                res[i] = digits[i-1];
            }
            return res;
        } 
        return digits;
    }
}

有个小毛病，就是最后的前插 1，没必要后边的再遍历赋值= = 因为末尾+1，最后如果需要前插1说明都是9= =，哈哈哈，所以新数组创建完，只需要赋值0号索引为1即可，其他默认为0的。也就是最后不需要遍历 digits。调整后的：

class Solution {
    public int[] plusOne(int[] digits) {
        // 参数校验
        if (digits == null || digits.length <= 0) {
            return digits;
        }
        // 取出末尾数字 + 1
        int len = digits.length;
        int lastNum = digits[len - 1] + 1;
        // 如果小于10 那么直接塞回去返回
        if (lastNum < 10) {
            digits[len - 1] = lastNum;
            return digits;
        }
        // 这里就是大于10 要进位
        for (int i = len - 1; i >= 0; i--) {
            int num = digits[i] + 1;
            if (num < 10) {
                digits[i] = num;
                break;
            }
            // 如果超过10 当前位置设置为 0
            digits[i] = 0;
            // 如果到头了，那么就需要前插1，否则继续向前
            if (i == 0) {
                int[] res = new int[len + 1];
                res[0] = 1;
                return res;
            } 
        }
        return digits;
    }
}

加油。