加一-LeetCode

加一

🎯 问题描述（来源于LeetCode）

描述：
给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。
将大整数加 1，并返回结果的数字数组。
说明：

• 1 <= digits.length <= 100

• 0 <= digits[i] <= 9

• digits 不包含任何前导 0。
  示例：

• 示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
加 1 后得到 123 + 1 = 124。
因此，结果应该是 [1,2,4]。

• 示例 2：

输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

💻 解题思路

思路1：反向遍历

思路1：代码实现

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n=len(digits)
        x=[]
        d=n-1
        digits[n-1]+=1
        while d>-1:
            while digits[d]==10:
                x.append(0)
                if d==0:
                    x.append(1)
                    m=x[::-1]
                    return m          
                d-=1
                digits[d]+=1
            x.append(digits[d])
            d-=1
        m=x[::-1]
        return m

思路1：📊 性能分析

提交结果

• 运行时间：0ms击败100.00%
• 内存消耗：17.30MB击败97.07%

复杂度验证

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

思考

反向遍历数组，判断当前数字+1后是否等于10，返回反转数组

思路2：判断当前数位是否进1（观看灵神的思路）

思路2：代码实现

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n=len(digits)
        for i in range(n-1,-1,-1):
            if digits[i]<9:
                digits[i]+=1
                return digits
            digits[i]=0
        return [1]+digits

思路2：📊 性能分析

提交结果

• 运行时间：0ms击败100.00%
• 内存消耗：17.67MB击败14.25%

复杂度验证

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

思考

反向遍历数组，判断当前数位是否需要进1，直到不进位返回数组