LeetCode 66. 加一（数组进位处理详解 + Java Python 实现）-拓冰企业网站定制

LeetCode 66. 加一（数组进位处理详解 + Java/Python 实现）

题目链接

66. 加一 - 力扣（LeetCode）

题目描述

给定一个表示大整数的整数数组digits，其中digits[i]是整数的第i位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导0。

将大整数加1，并返回结果的数字数组。

示例

示例 1

输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。 加 1 后得到 123 + 1 = 124。 因此，结果应该是 [1,2,4]。

示例 2

输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321。 加 1 后得到 4321 + 1 = 4322。 因此，结果应该是 [4,3,2,2]。

示例 3

输入：digits = [9] 输出：[1,0] 解释：输入数组表示数字 9。 加 1 得到了 9 + 1 = 10。 因此，结果应该是 [1,0]。

提示

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits不包含任何前导0

解题思路

这道题的核心是模拟数字加法的进位过程。我们需要从最低位（数组末尾）开始，逐位加 1，处理可能出现的进位。

关键点分析

从右往左遍历：因为加 1 操作从最低位开始，所以要从数组末尾开始遍历。
遇到非 9 的数字：直接加 1 并返回，因为不会产生进位。
遇到 9：将当前位设为 0，继续向前遍历，因为需要进位。
全是 9 的情况：如果遍历完所有位都是 9，说明需要增加一位，新数组长度为digits.length + 1，首位为 1，其余位为 0。

举例说明

例子 1：digits = [1,2,3]

从末尾开始：index = 2，digits[2] = 3，不是 9，加 1 变成 4，返回[1,2,4]。

例子 2：digits = [1,9,9]

index = 2，digits[2] = 9，设为 0。
index = 1，digits[1] = 9，设为 0。
index = 0，digits[0] = 1，不是 9，加 1 变成 2，返回[2,0,0]。

例子 3：digits = [9,9,9]

index = 2，digits[2] = 9，设为 0。
index = 1，digits[1] = 9，设为 0。
index = 0，digits[0] = 9，设为 0。
循环结束，创建新数组[1,0,0,0]，返回。

代码实现

Java 最优写法（推荐）

classSolution{publicint[]plusOne(int[]digits){for(intindex=digits.length-1;index>=0;index--){if(digits[index]!=9){digits[index]+=1;returndigits;}digits[index]=0;}int[]newArr=newint[digits.length+1];newArr[0]=1;returnnewArr;}}

Python 版本

classSolution(object):defplusOne(self,digits):""" :type digits: List[int] :rtype: List[int] """index=len(digits)-1whileindex>=0:ifdigits[index]!=9:digits[index]+=1returndigits digits[index]=0index-=1digits.insert(0,1)returndigits

代码说明

Java 版本

从末尾开始遍历：for (int index = digits.length - 1; index >= 0; index--)。
遇到非 9 的数字：
```
if(digits[index]!=9){digits[index]+=1;returndigits;}
```
直接加 1 并返回，因为不会产生进位，后面的高位不需要改变。
遇到 9：
```
digits[index]=0;
```
当前位设为 0，继续向前遍历，处理进位。
循环结束仍未返回：说明所有位都是 9，例如[9,9,9]。此时需要：
```
int[]newArr=newint[digits.length+1];newArr[0]=1;returnnewArr;
```
创建新数组，长度为原长度加 1，首位为 1，其余位默认为 0。

Python 版本

Python 版本思路与 Java 版本完全一致，只是语法不同：

使用while循环代替for循环。
使用digits.insert(0, 1)在列表头部插入元素 1，这比 Java 创建新数组更简洁。

复杂度分析

时间复杂度：O(n)，最坏情况下需要遍历整个数组（全是 9 的情况）。
空间复杂度：O(1)，除了全是 9 的情况需要创建��数组外，其余情况都是原地修改。即使创建新数组，空间复杂度也是O(n)，但这是必要的。

常见错误写法分析

有些同学可能会写出下面这样的代码：

publicint[]plusOne(int[]digits){for(intindex=digits.length-1;index>=0;index--){intc=digits[index];if(index==0&&c==9){// return1returndigitals;// 错误：变量名写错，应该是 digits}if(c!=9){// return2returndigits;// 错误：这里没有加 1}else{digits[index]=0;}}// 语法兜底，逻辑永远执行不到returndigits;}

这段代码存在几个问题：

变量名拼写错误：digitals应该是digits。
逻辑错误：在c != 9的分支中，直接返回了digits，但没有执行digits[index] += 1操作。这样即使遇到非 9 的数字，也不会加 1。
特殊情况处理不当：当index == 0 && c == 9时，应该创建新数组返回，但代码只是返回了原数组，没有处理进位。

正确思路对比

最优写法之所以简洁，是因为它抓住了问题的本质：

遇到非 9 就加 1 返回：这是最常见的情况，直接处理。
遇到 9 就设为 0 继续：处理进位。
循环结束仍未返回：说明全是 9，需要扩展数组。

这种写法不需要额外的变量，也不需要特殊的边界判断，逻辑非常清晰。

Java 和 Python 实现对比

Java 的特点

数组长度固定，需要创建新数组来处理全 9 的情况。
使用for循环，语法更紧凑。
返回值类型是int[]。

Python 的特点

列表是动态的，可以使用insert方法在头部插入元素。
使用while循环，控制更灵活。
返回值类型是List[int]。

共同点

两者的核心逻辑完全一致：

从右往左遍历
非 9 加 1 返回
9 设为 0 继续
全 9 处理进位

总结

这道题虽然简单，但很好地考察了对数组操作和进位处理的理解。核心要点：

从右往左遍历：模拟加法的进位过程。
遇到非 9 直接加 1 返回：这是最普遍的情况。
遇到 9 设为 0 继续：处理进位。
全是 9 的特殊情况：需要创建新数组，长度为原长度加 1，首位为 1。

关键点回顾：

遍历方向：从数组末尾到开头
非 9 处理：digits[index] += 1; return digits;
9 的处理：digits[index] = 0;
全 9 处理：创建新数组，首位为 1（Java）或insert(0, 1)（Python）

这道题的思路也可以扩展到其他进位相关的题目，比如字符串相加、二进制加法等。掌握这个模板对解决类似问题很有帮助。

资讯详情

LeetCode 66. 加一（数组进位处理详解 + Java Python 实现）