求助：无法解决LeetCode中Plus One的Java实现问题

问题描述 #

给定一个整数数组digits表示非负大整数（高位到低位排列，无前导零），将其加1后返回对应的数字数组。例如输入[1,2,3]，输出[1,2,4]。

当前代码在处理长数组时出错：预期输出[9,8,7,6,5,4,3,2,1,1]，实际输出[9,8,7,6,5,4,3,2,1,9]。

错误代码 #

class Solution {
    public int[] plusOne(int[] digits) {
        long temp=0;
        int c=0;
        for(int i:digits){
            temp=temp*10+i;
        }
        temp+=1;
        long copy=temp;
        while(copy>0){
            copy/=10;
            c++;
        }
        int[] result=new int[c];
        for(int i=c-1;i>=0;i--){
            result[i]=(int)temp%10;
            temp/=10;
        }
        return result;
    }
}

错误原因 #

你的代码依赖long类型存储整个数字，但long的最大值是9223372036854775807（19位），当输入的digits长度超过18位时，temp会溢出，导致数值被截断，后续加1和数字提取都会出错。比如你遇到的测试用例，原数字是9876543210，加1后应该是9876543211，但因为temp溢出后变成了错误值，提取个位时得到9而非1。

正确解决方案 #

直接在数组上处理进位，避免使用数值类型存储大数：

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        // 从最后一位开始加1，处理进位
        for (int i = n - 1; i >= 0; i--) {
            digits[i]++;
            // 如果当前位加1后不是10，说明没有进位，直接返回
            if (digits[i] != 10) {
                return digits;
            }
            // 否则当前位设为0，继续向前处理进位
            digits[i] = 0;
        }
        // 如果所有位都进位了，说明原数组全是9，需要新建数组
        int[] newDigits = new int[n + 1];
        newDigits[0] = 1;
        return newDigits;
    }
}

方案说明 #

• 从数组末尾（个位）开始遍历，逐位加1
• 若当前位加1后不等于10，无进位，直接返回数组
• 若等于10，设为0并继续向前处理进位
• 若遍历完所有位仍有进位（比如原数组是[9,9,9]），则新建长度+1的数组，首位设为1，其余为0

内容的提问来源于stack exchange，提问作者Ankit Biswas