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 1000 digits[i] 9digits不包含任何前导0解题思路这道题的核心是模拟数字加法的进位过程。我们需要从最低位数组末尾开始逐位加 1处理可能出现的进位。关键点分析从右往左遍历因为加 1 操作从最低位开始所以要从数组末尾开始遍历。遇到非 9 的数字直接加 1 并返回因为不会产生进位。遇到 9将当前位设为 0继续向前遍历因为需要进位。全是 9 的情况如果遍历完所有位都是 9说明需要增加一位新数组长度为digits.length 1首位为 1其余位为 0。举例说明例子 1digits [1,2,3]从末尾开始index 2digits[2] 3不是 9加 1 变成 4返回[1,2,4]。例子 2digits [1,9,9]index 2digits[2] 9设为 0。index 1digits[1] 9设为 0。index 0digits[0] 1不是 9加 1 变成 2返回[2,0,0]。例子 3digits [9,9,9]index 2digits[2] 9设为 0。index 1digits[1] 9设为 0。index 0digits[0] 9设为 0。循环结束创建新数组[1,0,0,0]返回。代码实现Java 最优写法推荐classSolution{publicint[]plusOne(int[]digits){for(intindexdigits.length-1;index0;index--){if(digits[index]!9){digits[index]1;returndigits;}digits[index]0;}int[]newArrnewint[digits.length1];newArr[0]1;returnnewArr;}}Python 版本classSolution(object):defplusOne(self,digits): :type digits: List[int] :rtype: List[int] indexlen(digits)-1whileindex0: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 并返回因为不会产生进位后面的高位不需要改变。遇到 9digits[index]0;当前位设为 0继续向前遍历处理进位。循环结束仍未返回说明所有位都是 9例如[9,9,9]。此时需要int[]newArrnewint[digits.length1];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(intindexdigits.length-1;index0;index--){intcdigits[index];if(index0c9){// 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 处理创建新数组首位为 1Java或insert(0, 1)Python这道题的思路也可以扩展到其他进位相关的题目比如字符串相加、二进制加法等。掌握这个模板对解决类似问题很有帮助。 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 1000 digits[i] 9digits不包含任何前导0解题思路这道题的核心是模拟数字加法的进位过程。我们需要从最低位数组末尾开始逐位加 1处理可能出现的进位。关键点分析从右往左遍历因为加 1 操作从最低位开始所以要从数组末尾开始遍历。遇到非 9 的数字直接加 1 并返回因为不会产生进位。遇到 9将当前位设为 0继续向前遍历因为需要进位。全是 9 的情况如果遍历完所有位都是 9说明需要增加一位新数组长度为digits.length 1首位为 1其余位为 0。举例说明例子 1digits [1,2,3]从末尾开始index 2digits[2] 3不是 9加 1 变成 4返回[1,2,4]。例子 2digits [1,9,9]index 2digits[2] 9设为 0。index 1digits[1] 9设为 0。index 0digits[0] 1不是 9加 1 变成 2返回[2,0,0]。例子 3digits [9,9,9]index 2digits[2] 9设为 0。index 1digits[1] 9设为 0。index 0digits[0] 9设为 0。循环结束创建新数组[1,0,0,0]返回。代码实现Java 最优写法推荐classSolution{publicint[]plusOne(int[]digits){for(intindexdigits.length-1;index0;index--){if(digits[index]!9){digits[index]1;returndigits;}digits[index]0;}int[]newArrnewint[digits.length1];newArr[0]1;returnnewArr;}}Python 版本classSolution(object):defplusOne(self,digits): :type digits: List[int] :rtype: List[int] indexlen(digits)-1whileindex0: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 并返回因为不会产生进位后面的高位不需要改变。遇到 9digits[index]0;当前位设为 0继续向前遍历处理进位。循环结束仍未返回说明所有位都是 9例如[9,9,9]。此时需要int[]newArrnewint[digits.length1];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(intindexdigits.length-1;index0;index--){intcdigits[index];if(index0c9){// 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 处理创建新数组首位为 1Java或insert(0, 1)Python这道题的思路也可以扩展到其他进位相关的题目比如字符串相加、二进制加法等。掌握这个模板对解决类似问题很有帮助。