Plus One
一个非负整数以其十进制数字组成的数组 digits 存储，最高位在前：472 表示为 [4, 7, 2]。将这个数加 1，并以相同形式返回结果的各位数字。这个数最多可以有 100 位，远超 64 位整数的表示范围。
函数
- digitsinteger-array
- 这个数字的各位数，按从高位到低位排列
- 返回值integer-array
- 数字的各位加 1，按从高位到低位的顺序排列
约束条件
1 ≤ digits.length ≤ 1000 ≤ digits[i] ≤ 9digits没有前导零，数字 0 本身除外，它是[0]。
示例
- 输入
- digits = [4, 3, 9]
- 输出
- [4, 4, 0]
- 解释
- 这个数字是 439，439 + 1 = 440。个位数 9 变成 0，并向 3 进位，使它变成 4。
- 输入
- digits = [9, 9]
- 输出
- [1, 0, 0]
- 解释
- 99 + 1 = 100。两个 9 都变成了 0，剩下的进位成为新的最高位，所以答案比输入多一位。
- 输入
- digits = [0]
- 输出
- [1]
- 解释
- 数字 0 写作
[0]，并且 0 + 1 = 1。
进阶
如果要改为减去 1，且数字至少为 1，该怎么做？结果会在什么时候失去最高位数字，就像 [1, 0, 0] 这样？
提示
逐个打开提示，每个都会多透露一点。
这个数字也可以有 100 位，超出了任何内置整数类型的范围。像在纸上计算一样，逐位相加。进位的 1 最先放在哪里？
给小于 9 的数字加 1 不会产生进位，因此左边的数字不会改变。只有 9 会变成 0，并向左进位。
从最后一位开始向左遍历。把每个 9 变成 0；遇到第一个小于 9 的数字时，将它加 1 并返回。如果一直找不到这样的数字，说明每一位都是 9：答案是 1 后面跟着若干个 0。
题解
一个 100 位数会超出所有 64 位整数的范围，64 位整数的上限约为 1.8 × 10^19，所以你无法将它转换成整数再相加。要像在纸上计算那样，从最后一位开始相加，并处理进位。加 1 只会改变末尾连续的 9，这些 9 会变成 0，它们左边的那一位也会改变。
逐位进行带进位的加法
思路
从进位 1 开始，也就是你要加上的那个数。从右边开始处理每一位，列的总和等于这一位的数字加上进位：total % 10 放入答案，total / 10 作为下一次的进位。总和最多为 9 + 1 = 10，所以进位始终是 0 或 1。处理完第一位后若还有进位，就把它作为新的最高位，就像 999 + 1 = 1000 一样。
你是从答案的最后一位开始生成的，所以要按这个顺序收集数字，并在最后将其反转。时间复杂度为 O(n)，并且会创建一个最多包含 n + 1 位数字的新数组。
算法
- 将
carry设为 1，并创建一个空列表来存放答案。 - 从最后一位到第一位，依次处理每个数字，计算
total = digit + carry。 - 将
total % 10添加到答案中，并将carry设为向下取整后的total / 10。 - 循环结束后，如果
carry为 1，就将它添加到答案中。 - 反转答案并返回。
def plusOne(digits):
result = [] # the answer, last digit first
carry = 1 # the one you are adding
for i in range(len(digits) - 1, -1, -1):
total = digits[i] + carry
result.append(total % 10)
carry = total // 10
if carry > 0:
result.append(carry)
result.reverse()
return result在小于 9 的第一个数字处停止
思路
小于 9 的数字会吸收进位 1：它加 1，左边的每个数字都保持不变。只有 9 会变成 0，并把进位继续传下去。因此，你可以在遇到第一个小于 9 的数字时停止，并返回已在原数组中修改的输入数组。对于 [2, 9, 0, 9]，最后一个 9 变成 0，0 变成 1，然后返回 [2, 9, 1, 0]，无需读取前两个数字。
如果没有小于 9 的数字，那么这个数就是 10^n - 1，答案是 1 后面跟着 n 个 0。只有这种情况需要创建新数组，因此其他情况下额外空间为 O(1)。
算法
- 从最后一个索引开始，依次遍历到第一个索引。
- 如果数字小于 9，就将它加 1，然后返回数组。
- 否则，该数字是 9：将它设为 0，然后向左移动一位。
- 如果循环结束，说明每个数字都是 9：返回 1，后面跟着
n个 0。
def plusOne(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1 # no carry leaves this digit, so the rest stays as it is
return digits
digits[i] = 0 # 9 + 1 = 10: write 0 and carry one to the left
# Every digit was 9: the answer is 1 followed by zeros.
return [1] + digits
易错点和边界情况
- 把数组转换成整数，再转换回来。64 位整数最多只能容纳 19 或 20 位数字，因此 100 位数字会溢出，而浮点数会更早丢失末尾的数字。
- 忘记处理多出来的那一位。
[9, 9, 9]必须变成[1, 0, 0, 0]；只重写现有位数的代码会返回[0, 0, 0]。 - 给第一位数字加 1。数组按最高位在前的顺序排列，因此个位数是最后一个元素。
- 当小于 9 的数字吸收进位后，没有立即返回。这样循环会修改本应保持不变的数字：
[1, 9, 3]必须变成[1, 9, 4]。 - 在 Lua 和 R 中，数组从 1 开始索引，因此最后一位的索引是
n，而不是n - 1。
常见问题3
Plus One 的时间复杂度是多少？
对于 n 位数字，这两种方法的运行时间都是 O(n)，因为全是 9 的情况需要处理每一位数字。提前退出的版本会在处理完末尾的 9 后停止，并且只使用 O(1) 的额外空间，但答案需要新增一位最高位数字时除外。
为什么不把这些数字转换为整数？
这个数字可以有 100 位，而 64 位整数的上限约为 1.8 × 10^19，也就是 20 位。Python 和 Ruby 支持无限大的整数，所以这种转换在这两种语言中都能正常工作，但这段代码无法移植到其他语言中。逐位处理永远不会溢出。
如何将两个以数字数组形式存储的数相加？
使用列式计算法，并在每个数组末尾设置一个索引。每一列都将两个数字相加，缺少的数字按 0 处理，再加上进位。两个数组都处理完且进位为 0 时停止，然后将收集到的数字反转。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def plusOne(digits):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
digits = [4, 3, 9]
预期输出
[4, 4, 0]