題目描述

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

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

你可以假設除了整數 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;
};

畫解