月度归档： 2023年2月

ChatGPT最近大火，趁热让它做做LeetCode每日一题看看。

https://leetcode.com/problems/add-to-array-form-of-integer/

“问题描述

The array-form of an integer num is an array representing its digits in left to right order.

    For example, for num = 1321, the array form is [1,3,2,1].

Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.


Example 1:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: num = [2,7,4], k = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: num = [2,1,5], k = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Constraints:

    1 <= num.length <= 104
    0 <= num[i] <= 9
    num does not contain any leading zeros except for the zero itself.
    1 <= k <= 104

我的解答

这个问题是Easy题，只要一个个累加就可以了，但注意不能将num展开为整数，再和k相加，因为会整数溢出。

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        int carry = 0;
        for(int i=num.length-1; i >= 0 || k > 0 || carry > 0; i--) {
            int d1 = i>=0 ? num[i] : 0;
            int d2 = k % 10;
            k /= 10;
            
            result.add((d1+d2+carry) % 10);
            carry = (d1+d2+carry) / 10;
        }
        Collections.reverse(result);
        return result;
    }
}

然后我把我的Solution给ChatGPT让它优化下

ChatGPT给的回答如下

The given implementation looks already quite efficient in terms of both time and space complexity. However, one possible improvement to consider is to use a LinkedList instead of an ArrayList for the result list. This is because the LinkedList implementation offers constant time complexity for appending elements at the beginning or end of the list, whereas the ArrayList implementation may require copying the entire array when it reaches its capacity. Since we are appending digits to the end of the list in this implementation, using a LinkedList can help to avoid potential performance bottlenecks when working with large input arrays.

Another possible improvement is to use bit manipulation instead of the division and modulus operations to extract the least significant digit of k. Specifically, we can use the bitwise AND operator with the value 0x1 to obtain the least significant bit of k, and then use the bitwise right shift operator to remove this bit and shift the remaining bits to the right by one position. This can offer a small speedup in some cases, as bit manipulation operations are generally faster than division and modulus operations.

Here is an updated implementation that incorporates these improvements:

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        LinkedList<Integer> result = new LinkedList<>();
        
        int carry = 0;
        for(int i = num.length - 1; i >= 0 || k > 0 || carry > 0; i--) {
            
            int d1 = i >= 0 ? num[i] : 0;
            int d2 = k & 0x1;
            k >>= 1;
            
            result.addFirst((d1 + d2 + carry) % 10);
            carry = (d1 + d2 + carry) / 10;
        }
        
        return result;
    }
}

ChatGPT说了两个改进点，但是给的解答是错的。因为k是十进制的，没法用 k & 0x1 得到k的最低位。可能是它做过这个题的二进制形式的？

我们直接把原问题抛给他看看ChatGPT怎么回答。

ChatGPT的方案如下

public List<Integer> addToArrayForm(int[] num, int k) {
    int n = 0;
    for (int i = 0; i < num.length; i++) {
        n = n * 10 + num[i];
    }
    n += k;

    List<Integer> res = new ArrayList<>();
    while (n > 0) {
        int r = n % 10;
        res.add(r);
        n /= 10;
    }
    if (res.isEmpty()) {
        res.add(0);
    }
    Collections.reverse(res);
    return res;
}

这里ChatGPT犯了最开始说的错误，它直接把num展开为一个整数了，由于num的长度最多10000位，所以会溢出。

大家暂时不用害怕失业了。ChatGPT大致思路是OK的，但在处理边缘条件时，是会犯错的。lol