66. Plus One

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        if len(digits) == 0:
            return []
        
        # since the question is to increment 1 to the integer, set default carry to 1
        carry = 1
        # iterate the list in reverse order
        for i in range(len(digits) - 1, -1, -1):
            # new_value represents i-th element + carry
            new_value = digits[i] + carry
            # if new_value equals to 10, this means we need to add 1 to the next digit
            if new_value == 10:
                digits[i] = 0
                carry = 1
            else:
                # carry = 0 now, done with iteration and return the list
                digits[i] = new_value
                return digits
        if carry == 1:
            # append 1 in front of the list
            digits.insert(0, carry)
        return digits

Time Complexity: O(N)

Space Complexity: O(N)

Notes:

程式流程

• 因為題目提到 the most significant digit是這個list的開始，所以在做加1運算的時候，要從list的最後一個位置開始跑起
• 理論上一開始的carry應該是0，但是我們只需要在最後一個數字加1，為了簡化流程，把一開始預設的carry值設成1
• 在iterate list的時候，每次都先把目前的數值加上carry，並存到一個暫存的變數 (new_value)
  • 如果 new_value 等於10，表示需要進位：把該位數設成0且carry = 1
  • 如果 new_value 不等於10，表示不需要進位，直接把 new_value 寫回該位數。因為不會有進位，所以可以直接回傳結果
• 最後如果carry等於1，表示原本的位數不夠表示這個數字，因此要在這個list前面加上1 (進位)

紀錄

• 10分鐘寫下題目大綱、需要的假設、method的input與output
• 10分鐘寫下pseudo code，並轉成Python code (因為這題相對簡單，pseudo code與最終可執行的程式碼相差不大)，舉幾個例子用手寫(模擬)的方式跑過一次程式
• 3-5分鐘把手寫的程式碼輸入Leetcode並執行

備註

• 手寫的版本是對的，但是輸入到Leetcode後有typo。之後在Leetcode上執行前，可能需要再核對一次
• 在寫流程解釋的時候，發現其實原本程式碼的倒數第4行不需要再做一次判斷，其實可以直接做insert