LeetCode 题目 65：有效数字（Valid Number）【python】

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在列表的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

输入格式

• digits：一个整数数组。

输出格式

• 返回一个数组，表示加一后的结果。

示例

示例 1

输入: digits = [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
1
2
3

示例 2

输入: digits = [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
1
2
3

示例 3

输入: digits = [9]
输出: [1,0]
解释: 输入数组表示数字 9。
1
2
3

---

方法一：模拟进位

解题步骤

1. 从最低位开始遍历：遍历数组的最后一个元素，即数字的最低位。
2. 处理进位：如果当前位加一后等于10，则设置当前位为0，并将进位带到下一位。
3. 终止条件：如果没有进位发生，直接返回数组。如果遍历完所有元素仍有进位，需要在数组最前面添加一个元素1。

完整的规范代码

def plusOne(digits):
    """
    使用模拟进位法对数组表示的数字进行加一操作
    :param digits: List[int], 代表数字的数组
    :return: 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  # 处理全部为9的情况

# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

算法分析

• 时间复杂度：(O(n))，在最坏的情况下需要遍历整个数组。
• 空间复杂度：(O(1))，除了输出数组外，额外使用的空间是常数级别的。

方法二：转换为数字

解题步骤

1. 数组转换为数字：将数组转换为整数。
2. 加一操作：对该数字加一。
3. 数字转回数组：将结果数字转换回数组形式。

完整的规范代码

def plusOne(digits):
    """
    将数组转换为数字进行加一，然后再转换回数组
    :param digits: List[int], 代表数字的数组
    :return: List[int], 加一后的数组
    """
    num = 0
    for digit in digits:
        num = num * 10 + digit
    num += 1
    return [int(i) for i in str(num)]

# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

算法分析

• 时间复杂度：(O(n))，转换过程中涉及到线性时间的操作。
• 空间复杂度：(O(n))，需要存储转换后的数字和结果数组。

方法三：字符串处理

解题步骤

1. 数组转字符串：将数组中的数字转换成字符串并连接。
2. 字符串转数字加一：将字符串转换为数字进行加一操作。
3. 数字转字符串再转数组：将加一后的数字转换为字符串，然后将每个字符转换为整数数组。

完整的规范代码

def plusOne(digits):
    """
    使用字符串处理的方法进行加一操作
    :param digits: List[int], 代表数字的数组
    :return: List[int], 加一后的数组
    """
    s = ''.join(map(str, digits))
    num = int(s) + 1
    return [int(x) for x in str(num)]

# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

算法分析

• 时间复杂度：(O(n))，涉及字符串和数字的转换。
• 空间复杂度：(O(n))，需要额外的空间来存储字符串和结果数组。

方法四：递归处理

解题步骤

1. 定义递归函数：递归处理加一和进位。
2. 边界条件：当处理到第一个数字且需要进位时，在数组前添加一个1。
3. 递归逻辑：从后向前处理每个数字，处理进位。

完整的规范代码

def plusOne(digits):
    """
    使用递归处理数组加一的操作
    :param digits: List[int], 代表数字的数组
    :return: List[int], 加一后的数组
    """
    def helper(index):
        if index < 0:
            digits.insert(0, 1)
            return
        if digits[index] == 9:
            digits[index] = 0
            helper(index - 1)
        else:
            digits[index] += 1
    
    helper(len(digits) - 1)
    return digits

# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

算法分析

• 时间复杂度：(O(n))，最坏情况下需要递归遍历整个数组。
• 空间复杂度：(O(n))，递归深度可能达到数组长度。

方法五：迭代优化

解题步骤

1. 从最后一个元素开始迭代：处理每个元素的加一和进位。
2. 处理进位：如果当前位置变为10，则设置为0并继续处理前一位。
3. 处理全部为9的特殊情况：如果首位也进位，则数组前添加1。

完整的规范代码

def plusOne(digits):
    """
    使用迭代优化的方法处理加一操作
    :param digits: List[int], 代表数字的数组
    :return: List[int], 加一后的数组
    """
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] == 9:
            digits[i] = 0
        else:
            digits[i] += 1
            return digits
    digits.insert(0, 1)
    return digits

# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

算法分析

• 时间复杂度：(O(n))，遍历数组进行处理。
• 空间复杂度：(O(1))，除了结果外，几乎不使用额外空间。

不同算法的优劣势对比

应用示例

会计软件：
在处理财务数据时，经常需要对大量的数字序列进行加减操作。这些算法可用于实现一些基本的数字操作功能，如自动递增发票号或处理交易记录。特别是在需要快速响应和高效计算的场景中，选择合适的算法可以显著提高软件性能和用户满意度。