66. 加一
题目描述
输入整数数组 digits，它按从高位到低位的顺序存放一个非负大整数的每一位，每个元素是 0 到 9 之间的一位数字。这个数没有前导零。
把这个数加上 1，并用同样的形式返回结果数组。
示例 1
输入：digits = [1,2,3] 输出：[1,2,4]
解释：123 + 1 = 124。
示例 2
输入：digits = [4,3,2,1] 输出：[4,3,2,2]
解释：4321 + 1 = 4322。
示例 3
输入：digits = [9] 输出：[1,0]
解释：9 + 1 = 10，产生进位，结果多出一位。
数据范围
1 <= digits.length <= 1000 <= digits[i] <= 9digits表示的数没有前导零。
解题思路
从最低位往高位扫。如果当前位小于 9，加 1 后不会进位，直接返回；如果是 9，它变成 0 并把进位传给更高一位。如果所有位都是 9，最后在最前面补一个 1。
为什么正确
扫到下标 i 时，i 右边的位已经全部是 0（原来都是 9），并且还有一个进位 1 要加到第 i 位。
复杂度分析
时间 O(n)，空间 O(1)（全 9 时新建数组除外）。
易错点
不要把数组拼成整数再加 1，长度可达 100 位，会溢出。全 9 的情况要记得数组长度加 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits
digits[i] = 0
return [1] + digitsclass Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i] += 1;
return digits;
}
digits[i] = 0;
}
int[] res = new int[digits.length + 1];
res[0] = 1;
return res;
}
}class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
for (int i = (int)digits.size() - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i] += 1;
return digits;
}
digits[i] = 0;
}
digits.insert(digits.begin(), 1);
return digits;
}
};func plusOne(digits []int) []int {
for i := len(digits) - 1; i >= 0; i-- {
if digits[i] < 9 {
digits[i] += 1
return digits
}
digits[i] = 0
}
return append([]int{1}, digits...)
}var plusOne = function(digits) {
for (let i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i] += 1;
return digits;
}
digits[i] = 0;
}
return [1, ...digits];
};function plusOne(digits: number[]): number[] {
for (let i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i] += 1;
return digits;
}
digits[i] = 0;
}
return [1, ...digits];
}