題目描述

給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。

最高位數字存放在數組的首位， 數組中每個元素只存儲一個數字。

你可以假設除了整數 0 之外，這個整數不會以零開頭。

示例 1:

輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數組表示數字 123。

示例 2:

輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數組表示數字 4321。

解題方案

思路

• 標簽：數組遍歷

• 這道題需要整理出來有哪幾種情況，在進行處理會更舒服

1. 末位無進位，則末位加一即可，因為末位無進位，前面也不可能產生進位，比如45 => 46

2. 末位有進位，在中間位置進位停止，則需要找到進位的典型標志，即為當前位%10后為0，則前一位加1，直到不為0為止，比如499 => 500

3. 末位有進位，并且一直進位到最前方導致結果多出一位，對于這種情況，需要在第2種情況遍歷結束的基礎上，進行單獨處理，比如999 => 1000

• 在下方的Java和JavaScript代碼中，對于第三種情況，對其他位進行了賦值0處理，Java比較tricky直接new數組即可，JavaScript則使用了ES6語法進行賦值

• 時間復雜度：O(n)

代碼

• Java版本

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        for(int i = len - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if(digits[i]!=0)
                return digits;
        }
        digits = new int[len + 1];
        digits[0] = 1;
        return digits;
    }
}

• JavaScript版本

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    const len = digits.length;
    for(let i = len - 1; i >= 0; i--) {
        digits[i]++;
        digits[i] %= 10;
        if(digits[i]!=0)
            return digits;
    }
    digits = [...Array(len + 1)].map(_=>0);;
    digits[0] = 1;
    return digits;
};

畫解