【题目】

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入： digits = [0]
输出： [1]

提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

【题目解析】

解决算法: 数组操作

• 方法描述: 从数组的最后一位开始，逐位加一并处理进位。如果最高位产生进位，需要在数组最前面插入新的一位。

• 具体步骤:

  1. 从数组最后一位开始，即个位数开始处理加一操作。
  2. 如果该位加一后小于10，则直接返回结果，因为不会影响到更高位的数字。
  3. 如果该位加一后等于10（产生进位），则该位变为0，并向前一位继续处理加一操作。
  4. 如果循环结束都没有返回结果，说明最高位也产生了进位，此时在数组最前面插入一位1。

算法特点:

• 直观简单：直接在输入的数组上操作，易于理解和实现。
• 高效：最多遍历一次数组，时间复杂度为O(n)。

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
        
        # 处理全是9的情况，例如[9,9,9]变成[1,0,0,0]
        return [1] + digits

执行效率

image.png

【总结】

适用问题类型:

这类方法适用于涉及数字逐位操作和进位处理的问题，尤其当处理的数字大小超出了语言的标准整型范围或者需要直接在数字的序列表示上进行操作时。这不仅限于简单的加法运算，还包括但不限于大数运算、二进制运算、以及任何需要精细控制数字每一位操作的场景。此外，这种方法也适合处理那些涉及序列和数字直接相互转换的问题，例如将数字转换为数组形式以便进行某些特定的操作，或者在一些算法实现中模拟硬件级别的运算处理。

解决算法: 数组逐位加法与进位处理

算法特点:

• 直接操作与灵活性: 算法直接在数组表示的数字上操作，无需将数字转换为其他形式或使用高级数据结构，提供了操作的灵活性。
• 适应性强: 可以很容易地适应各种大小的数字，特别是对于大数运算，这种方法避免了数字溢出的问题。
• 简洁性与高效性: 算法结构简单，一次遍历即可完成操作，使得算法既简洁又高效。

时间复杂度与空间复杂度:

• 时间复杂度: O(n)，其中n是数组的长度。在最坏的情况下，即数组中所有的数字都是9且需要进位时，算法需要遍历整个数组。
• 空间复杂度: O(1)。算法在原数组上操作，除了最终可能需要在数组前面增加一位以处理全部是9的数组外，不需要额外的存储空间。即使在最坏的情况下，额外空间的需求也是常数级别的。

实践意义:

• 大数处理能力: 在实际应用中，尤其是在金融、科学计算和加密算法等领域，经常会遇到需要处理超出标准数据类型范围的大数。这种方法能够提供一种简单而有效的解决方案。
• 深入理解数字表示和运算: 通过直接操作数字的数组表示，可以帮助开发者更深入地理解数字在计算机中的存储和运算方式，这对于深入学习计算机科学的基础知识非常有益。
• 算法教育和面试准备: 这类问题常见于算法面试和编程竞赛中，掌握这种方法不仅可以帮助解决实际问题，也是对算法能力的一种展示。
• 基础算法能力培养: 实现和理解这种算法可以作为进一步学习更复杂算法和数据结构的基础，比如学习如何处理链表中的数位操作等。

题目链接

加一