Leetcode加一解法 Java与Python3实现

LeetCode 加一：数组加一算法详解与边界处理

这道题表面简单，却是许多面试中热衷考察的“边界细节”题目。给你一个非空整数数组，每个元素只存储一位数字，整个数组表示一个非负整数——例如 [1,2,3] 对应数字 123。现在需要在这个整数的基础上加一，并返回加一后的数组结果。

最高位数字存放在数组的首位，并且我们可以假设除了整数 0 本身之外，这个整数不会以零开头——也就是说，输入不会是 [0,1,2] 这类格式。

英文题目描述如下：Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.

下面通过两个示例来直观理解：

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

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

看起来直接转成整数加一就能解决？但别忘了，数组元素可能多达几千位，普通整型根本无法存储。因此必须采用“模拟竖式加法”的思路来逐位处理进位。

Java 解法：

class Solution {
    public int[] plusOne(int[] digits) {
        for( int i=digits.length;i>=0;i--){
            if(digits[i] 1==10){
                digits[i]=0;
            }else {
                digits[i] =1;
                break;
            }
        }
        if(digits[0]==0){
            int[] digits2=new int[digits.length 1];
            digits2[0]=1;
            return digits2;
        }else {
            return digits;
        }
    }
}

解题思路详解：

核心逻辑非常直观：从数组的最右端（即个位）开始向左遍历。如果当前位加一后等于10，说明需要进位，将该位设为0，然后继续处理前一位；若加一后不等于10，则加一操作完成，直接跳出循环。有一个容易被忽略的细节：当所有位都进位时（例如 [9,9,9]），循环结束后数组首位会变成0，此时需要新建一个长度加一的数组，将第一位设为1，其余位全为0。上面Java代码正是按照这个思路实现的——先处理进位，最后判断首位是否为0，若是则扩容数组。

Python3 解法：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        """
        :type digits: int
        :return: int
        """
        num = 0
        for i in range(len(digits)):
            num = num*10   digits[i]
        return [int(i) for i in str(num 1)]

Python3 的解法更加灵活。上面这种写法先将整个数组拼接成一个整数，然后加一，再转回字符数组并拆分为列表。思路简单直接，但需要注意：如果数组长度极大（例如几千位），Python 虽然能处理大整数，但转换成字符串再拆分也算一种取巧方式。当然也可以采用类似 Java 的手动进位处理，或者利用 Python 列表的动态特性。

举个例子：可以将数组反转，使用 reversed(digits)，然后逐项加一并处理进位，若最后一位仍为0（说明仍需进位），则直接在数组末尾追加一个1，最后再反转回来。因为 Python 列表支持动态扩展，无需像 Java 那样新建固定长度数组，代码写起来更为简洁。