5/2 每日一題

 您將獲得一個表示為整數數組的大整數digits，其中每個digits[i]都是整數的數字。這些數字按從左到右的順序從最高有效位到最低有效位排序。大整數不包含任何前導的。ith0

將大整數遞增 1 並返回結果數組。

 

示例 1：

輸入： digits = [1,2,3]
輸出： [1,2,4]
解釋：數組表示整數 123。
遞增 1 得到 123 + 1 = 124。
因此，結果應該是 [1,2,4]。

示例 2：

輸入： digits = [4,3,2,1]
輸出： [4,3,2,2]
解釋：數組表示整數 4321。
遞增 1 得到 4321 + 1 = 4322。
因此，結果應該是 [4,3,2,2]。

示例 3：

輸入： digits = [9]
輸出： [1,0]
解釋：數組表示整數 9。
遞增 1 得到 9 + 1 = 10。
因此，結果應該是 [1,0]。

 

約束：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits不包含任何前導0的。

def plusOne(self, digits: List[int]) -> List[int]:

    str_=[str(i) for i in digits]

    str_digits=str(int("".join(str_))+1)  #int object不能迭代

    ans=[int(i) for i in str_digits]

    return ans

-------------------------------------------

參考解答

直覺

將開始向列表中元素的末尾添加一個並保留一個進位以繼續將其添加到前一個元素直到它到達第 0 個索引

方法

該函數首先將一個變量初始化sums為列表中最後一位數與 的和1。如果總和大於9，則變量carry設置為1，否則設置為0。如果總和大於 ，則列表的最後一位更新為 0 9，否則更新為 的值sums。

然後，循環以相反的順序迭代剩餘的數字。對於每個數字，如果數字和carry變量之和大於9，則carry變量設置為1，數字設置為0。否則，數字更新為自身與變量之carry和，carry變量設置為0。

最後，如果carry變量仍在1循環之後，1則將 a 追加到列表的末尾，並反轉列表並返回。否則，列表按原樣返回。

複雜

• 時間複雜度：
  O(n)

• 空間複雜度：
  O(1) 平均，O(n+1) 更差

該time complexity算法的 是O(n)，其中 n 是輸入數字列表的長度。這是因為我們只遍歷列表一次。

該space complexity算法的 是O(1)，因為我們正在就地修改輸入列表，而不是創建任何隨輸入大小增長的新數據結構。但是，如果我們需要將附加元素附加到輸入列表，則 將space complexity變為O(n+1)，其中n是輸入列表的長度。

代碼

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        sums = digits[-1] + 1
        carry = 1 if sums > 9 else 0  
        digits[-1] = 0 if sums > 9 else sums

        for i in range(len(digits)-2, -1, -1):
            if digits[i] + carry > 9:
                carry = 1
                digits[i] = 0
            else:
                digits[i] = digits[i] + carry
                carry = 0
        
        if carry == 1:
            digits.append(1)
            return digits[::-1]

        return digits