LeetCode 66. 加一（易）

简单的数组操作问题，注意好 9+1 进位的情况即可。

题目

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例

示例 1:

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

示例 2:

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

考察知识点

数组

核心思想

主要是要注意 9+1 产生的进位问题

Python版本

  • 一个 if-else 结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        if digits[-1] < 9:  # 不会进位 相加即可
            digits[-1] += 1
        else:  # 最后一位是9会进位
            i = -1
            while True:
                digits[i] = 0  # 先将最后一位置为0
                if abs(i-1) <= len(digits):  # 然后判断后续是否需要进一步进位
                    if digits[i-1] < 9:  # 进位到此处即可停止
                        digits[i-1] += 1
                        break
                    else:  # 会依次进位 继续循环
                        i = i - 1
                else:  # 到最高位了
                    digits.insert(0, 1)  # 在开始位置前添加1即可 不需要额外空间
                    break

        return  digits

print("leet code accept!!!")
Input = [[9,9], [9], [9, 9, 9], [6, 9, 9]]
Input1 = [2, 3]
Answer = [[1, 0, 0], [1, 0], [1, 0, 0, 0], [7, 0, 0]]



if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.plusOne(Input[i])
        if reslut == Answer[i]:
            print(True)
        else:
            print(False)
            print(Input[i])

时间复杂度：\(O(n)\)，当输入的n个数都是9时，就会循环n遍进行持续进位。
空间复杂度：\(O(1)\)，没有使用额外的空间。
执行用时 :40 ms, 在所有 Python3 提交中击败了50%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.06%的用户