加1个leetcode

Question

我在leetcode上做一道题，66.加一。

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

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

实施例1

• 输入：digits = [1,2,3]

• 输出：[1,2,4]

  解释：该数组代表整数 123。
  加 1 得到 123 + 1 = 124。
  因此，结果应该是[1,2,4]。

我的解决方案是：

class Solution {  
    public int[] plusOne(int[] digits) {  
        int num = 0;  
        for (int a : digits) {  
            num = 10*num + a;  
        }  
        int n=num+1;  
        String str=String.valueOf(n);  
        int arr[]=new int[str.length()];  
        for(int i=0;i<str.length();i++){  
            arr[i]=str.charAt(i)-'0';  
        }  
        return arr;  
    }
}

我遇到很多测试用例失败，其中之一是：

Input:
[9,8,7,6,5,4,3,2,1,0]  
Output:
[1,2,8,6,6,0,8,6,1,9]  
Expected:
[9,8,7,6,5,4,3,2,1,1]  

有人可以帮我吗？

Answer 1

跳跃之前要三思。并考虑边缘。

为什么他们会做出看似愚蠢的举动，将数字逐位存储在 int 数组中？没有意义，对吧？

除了...计算机不是魔法。int不能代表任何数字。计算机的存储空间不是无限的。具体来说，anint涵盖 32 位（4 字节），因此最多只能表示 2^32 个不同的数字。int 通过将其均匀划分为正数和负数来“使用”其分配的 2^32 空间，但负数会多一（因为“0”位于正空间中）。换句话说，从 -2^31 到 +2^31-1（含）的所有数字。

9876543210 比那个大。

你试图将数字数组转换为 an int，这是一个死胡同。一旦你这样做了，你就会得到错误的答案，并且无法解决这个问题。你的算法是错误的。你可以弄清楚这些东西，并且你应该总是通过首先仔细阅读作业来解决 leetcode 风格的问题。该作业涵盖了限制。它说明了这些数组可以有多大，而且我确信它说明了它们可以非常大；足够大，使得里面的数字大于 2^31-1。可能大于2^63-1（along可以达到）。

然后你就知道你需要编写的算法不能涉及“将其变成int第一个”。这通常就是重点（许多问题如果很小的话就会变得微不足道，但一旦把事情变大就会变得有趣）。

他们希望您编写的算法不得涉及任何转换。就地增加数组。这并不难（只要想一下：在不转换任何东西的情况下，如何将 [1, 2, 3] 变成 [1, 2, 4]？那应该很简单。然后想想如何处理 [1, 9, 9]。最后，想想如何处理[9, 9, 9]。那么你已经涵盖了所有情况，你就有了答案。