刷題日記（14） Plus One

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Example 3:

Input: digits = [0]
Output: [1]

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

解題思路：

看到加數字就要想到用 %和 /和 carries

如果carries是0，代表沒進位，最後直接回傳

如果carries是1，代表進位了，新增一個空的list，第一位放1，然後後面幾位把加完一的原本list，一個位數一個位數寫進去

(main function)

1. 新增一個int變數叫carries等於1
2. 開始for loop，i等於傳進來的list length-1，當i大於等於0時i減一，從最後面開始計算

2.1 新增一個空的int變數叫sum，然後等於digits[i]+carries

2.2 然後digits[i]等於剛剛加完的 sum再％10(取得餘數的意思)

2.3 接著carries等於sum除以10(這樣就可以得知要進位的數字等於多少了)

2.4 重複一直跑for loop迴圈直到 i小於0

3. for loop迴圈結束後，如果carries等於0，代表沒有進位，位數不變，直接回傳digits

4. 如果carries不等於0，代表有進位數，所以新增一個新的list rst長度等於digits.length+1 (因為要進一位)

5. 然後把rst的[0]設為1，因為進位了（加一一路加下去，最後進位頂多多一）

6. 然後開始另一個for loop，i從1開始，rstp[i]之後的位數一路塞進digits[i-1]的值，(i從0開始是因為，前面因為知道進位已經先在rst[0]設置1了)

7. 最後回傳rst

時間複雜度：O(1);

空間複雜度：O(n)