今天是紀錄LeetCode解題的第六十六天

第六十六題題目：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.

給定一個大的整數，以整數數組的形式表示每個digits，其中每個元素digits[i]代表該整數的一位數字，這些數字按從左到右的順序排列，從最高有效位到最低有效位，該大整數不包含任何前導零

將整數加一並回傳所得的數字數組

解題思路

取digits的最後一個位元加一，要考慮到進位的問題，所以我們設定i = len(digits) - 1 ~ 0，每一次檢查digits[i] 是否等於10，如果等於10表示要進位，那麼把digits[i]設為0，並把他的前一位digits[i - 1]加一，如果i = 0時有進位，那麼我們要在索引0的位置插入1(例如999 + 1，當i = 0時還要進位，所以要額外插入1在索引0的位置)

程式碼

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        if not digits:
            return []
        digits[-1] += 1
        i = len(digits) - 1
        while i >= 0 and digits[i] == 10:
            digits[i] = 0
            if i == 0:  #最左邊還要進位
                digits.insert(0, 1)
            else:
                digits[i - 1] += 1
            i -= 1
        return digits

執行過程(digits = [9,9,9])

初始狀態

• digits[-1] += 1 → 9 + 1 = 10 → digits = [9,9,10]
• i = 2

第一次迴圈

• digits[i] = 0 → digits[2] = 0 → digits = [9,9,0]
• digits[i - 1] += 1 → digits[1] += 1 → digits = [9,10,0]
• i -= 1 → i = 1

第二次迴圈

• digits[i] = 0 → digits[1] = 0 → digits = [9,0,0]
• digits[i - 1] += 1 → digits[0] += 1 → digits = [10,0,0]
• i -= 1 → i = 0

第三次迴圈

• digits[i] = 0 → digits[0] = 0 → digits = [0,0,0]
• if i == 0 → digits.insert(0, 1) → digits = [1,0,0,0]
• i -= 1 → i = -1
• 跳出迴圈

最後回傳digits = [1,0,0,0]就是答案了