题目: 加一

分析

方法一：暴力法

这是最简单直接的方法，直接将整个数组当做一个数字来处理，加一后再将其转化为数组。但是需要考虑到进位的情况。

Python 代码实现：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        num = 0
        for i in range(len(digits)):
            num += digits[i] * 10 ** (len(digits) - 1 - i)
        num += 1
        return [int(x) for x in str(num)]

时间复杂度为 O(n)，其中 n 为数组长度。

方法二：进位法

从数组最后一位开始遍历，依次进行加一操作，如果遇到进位则向前一位继续加一。如果遍历完数组所有元素后还需要进位，则需要在数组头部插入一个 1。

Python 代码实现：

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] = 0
            else:
                digits[i] += 1
                return digits
        digits.insert(0, 1)
        return digits

时间复杂度为 O(n)，其中 n 为数组长度。

方法三：递归法

递归法也可以解决加一问题，从数组的最后一位开始加一，如果需要进位，则继续递归。

Python 代码实现：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        def helper(digits, i):
            if i == -1:
                digits.insert(0, 1)
            elif digits[i] == 9:
                digits[i] = 0
                helper(digits, i - 1)
            else:
                digits[i] += 1
            return digits

        return helper(digits, len(digits) - 1)

时间复杂度为 O(n)，其中 n 为数组长度。