leetcode 66）加一.Array内存分配和BigInteger问题

Question

我是一名初学java程序员，在leetCode的第66）加一题中对数组内存分配和BigInteger有疑问。问题陈述如下：

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

将大整数加一并返回结果数字数组。

示例1：

输入：数字 = [1,2,3] 输出：[1,2,4] 说明：该数组代表整数 123。 加 1 得到 123 + 1 = 124。 因此，结果应该是[1,2,4]。 示例2：

输入：数字 = [4,3,2,1] 输出：[4,3,2,2] 说明：该数组代表整数 4321。 加 1 得到 4321 + 1 = 4322。 因此，结果应该是[4,3,2,2]。 例3：

输入：数字= [9] 输出：[1,0] 说明：该数组代表整数 9。 加 1 得到 9 + 1 = 10。 因此，结果应该是[1,0]。

限制：

1 <= digits.length <= 100 0 <= digits[i] <= 9 digits does not contain any leading 0's.

我使用 BigInteger 来解决这个问题，但所需的时间显示为 13-16 秒。我的解决方案：

import java.math.BigInteger;
class Solution 
{
    public int[] plusOne(int[] digits) 
    {
       String s=ArrtoString(digits);
       BigInteger n=new BigInteger(s);
       BigInteger n1 = n.add(new BigInteger("1"));
       int c=n1.toString().length();
       int[] d=new int[c];
       String result=n1.toString();
       d=StringToArr(result);
       return d;
    }
    public String ArrtoString(int[] arr)
    {
       String s="";
       for(int i=0;i<arr.length;i++)
       {
           s=s+arr[i];
       }
       return s;
    }
    public int[] StringToArr(String s)
    {
       int[] arr= new int[s.length()];
       for(int i=0;i<s.length();i++)
       {
           arr[i]=s.charAt(i)-'0';
       }
       return arr;
    }
}

我找到了一个替代解决方案，所需时间为0-1秒。解决方案是这样的：

class Solution 
{
    public int[] plusOne(int[] digits)
    {
      boolean carry = true;
      for (int i = digits.length - 1; carry==true &&  i >= 0; i--) 
      {
        carry = digits[i] == 9;
        if(carry)
        {   
            digits[i] = 0 ;
        }
        else
        {
            digits[i] =digits[i] + 1;;
        }
      }

      if (carry) 
      {
        int[] tmp = new int[digits.length + 1];
        tmp[0] = 1;
        System.arraycopy(digits, 0, tmp, 1, digits.length);
        digits = tmp;
      }
    return digits;
   }
}

我有两个疑问：

1）为什么使用BigInteger时需要这么长的时间。有什么办法可以优化吗

2）最后的第二个解决方案中写着

digits = tmp

。这个声明的目的是什么？是否将 tmp[] 数组的所有元素复制到digits[] 数组？如果是这样那怎么办？因为 tmp[] 数组的大小比digits[] 数组大1，如果我没记错的话，那么数组大小一旦声明就无法更改。还是我错了？请随时纠正我。我们将非常感谢您的帮助。

Answer 1

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        int[] result = new int[len + 1];
        if(len == 0){
            result[0] = 1;
            return result;
        }
        int carry = 0;
        result[len] = (digits[len - 1] + 1) % 10;
        carry = (digits[len - 1] + 1) / 10;
        for(int i = len - 2; i >= 0; i--){
            result[i + 1] = (digits[i] + carry ) % 10;
            carry = (digits[i] + carry ) / 10;
        }
        if(carry == 1){
            result[0] = 1;
            return result;
        }else{
            return Arrays.copyOfRange(result, 1, len + 1);
        }
    }
}