66. Plus One
這是加一系列的第一題，其實最好想這道題目的方法就是小學時候學的直式加法，直式加法就是從最末位開始加，並且不斷的把進位帶進去下一個位數。
在程式裡面要做直式加法，可以將題目給的陣列反過來遍歷，這個題目的問題很簡單，只有加一而已，所以我們就在最後一個位數加一。
既然我們是反著遍歷，答案會從最後一位的開始取得，題目的要求是回傳後的答案也是要用陣列來表示，所以我先不考慮取得答案的順序是不是我們要的，我只要先按照順序記錄起來就好。
在遍歷的時候，有哪些情況要考量呢？
- 最後一位數要加一
- 如果前面遍歷的的運算有造成進位要加一
- 運算完上面兩種情況，判斷下一次遍歷是否需要進位？（條件二的進位就是從這裡來的）
以上的一和二可以一起來看，因為任何一個條件滿足，要做的事情都是加一，加完一後要做的事情也都是一樣的，所以最後的程式碼如下：
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
m = len(digits)
res = []
carry = False
for i in reversed(range(m)):
if carry or i == m - 1:
digit = digits[i] + 1
res.append(digit % 10)
carry = digit > 9
else:
res.append(digits[i])
if carry:
res = res + [1]
return reversed(res)
最後有一種例外狀況要記得處理，那就是遇上 9, 99, 999, 9999….這種輸入全是九的情況，因為這樣的情況，會造成迴圈跑完後，最後一個進位沒有處理到，因此迴圈結束後要再做最後一次的進位判斷。
這個方法的時間複雜度是 $$O(n)$$ 和最優解相同，只要一次遍歷，不過空間複雜度也是 $$O(n)$$ 。
下面的一個方法是 LeetCode 上別人提出的解法，這個解法只針對這個題目，不過想法很聰明，很值得一看，我覺得不要太奇淫技巧的解法都可以幫助思考，在面試時腦袋可以比較靈活。
這個題目有其自身的限制，我們最需要擔心的，就是「最右邊」的數字是不是九，如果不是九的話，其實加一後就沒有事情了，但如果是九，加一後就要進位，繼續看看「左邊」一個數字是不是九。例如：[9,9,9] 這樣的情況，遍歷的方法和直式加法一樣。
最後的程式碼需要花一點時間理解，不過真的非常簡潔。
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in reversed(range(len(digits))):
if digits[i] == 9:
## 連續遇到 9 就是一直加
digits[i] = 0
else:
# 因為是反著遍歷，所以說很有可能一開始就直接加一就返回
# 如果或是上一次是 9 這次不是 9 ，所以直接加一
digits[i] += 1
return digits
# 遇到全部都是 9 的情況，只好再加一
return [1] + digits