V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
wangpugod2003
V2EX  ›  程序员

chatGPT 刷新题完全不行啊

  •  1
     
  •   wangpugod2003 · 2023-06-14 18:17:46 +08:00 · 2659 次点击
    这是一个创建于 528 天前的主题,其中的信息可能已经有所发展或是发生改变。

    试了下 leetcode 最新的算法题,也就是新出的在 chatGPT 训练集以后的算法题。

    chatGPT 完全搞不定,写出的代码狗屁不通,题目的意思都没很好的理解。

    prompt 了多次也搞不定,而且我给它测试用例,本来它的程序算出来=A ,它非说=B ,符合要求。。

    看来 AI 刷题还是任重道远啊。。。

    18 条回复    2023-06-15 16:26:41 +08:00
    liqinliqin
        1
    liqinliqin  
       2023-06-14 18:35:40 +08:00   ❤️ 1
    把题目贴出来,我用我的 chatgpt plus 跑一下
    midknight
        2
    midknight  
       2023-06-14 19:58:17 +08:00
    所以说离通用智能还是很远的
    xdygxh
        3
    xdygxh  
       2023-06-14 20:58:25 +08:00
    如果你用的是 3.5 ,那很正常,如果是 4.0 ,可能要改一下题目,虽然题目是新题,但是其实算法都是那些东西。另外让他跑测试用例,就有点扯了。。
    wonderfulcxm
        4
    wonderfulcxm  
       2023-06-14 22:11:59 +08:00 via iPhone
    请出题
    wangpugod2003
        5
    wangpugod2003  
    OP
       2023-06-15 09:07:03 +08:00
    @liqinliqin
    @wonderfulcxm

    2355. Maximum Number of Books You Can Take


    You are given a 0-indexed integer array books of length n where books[i] denotes the number of books on the ith shelf of a bookshelf.

    You are going to take books from a contiguous section of the bookshelf spanning from l to r where 0 <= l <= r < n. For each index i in the range l <= i < r, you must take strictly fewer books from shelf i than shelf i + 1.

    Return the maximum number of books you can take from the bookshelf.



    Example 1:

    Input: books = [8,5,2,7,9]
    Output: 19
    Explanation:
    - Take 1 book from shelf 1.
    - Take 2 books from shelf 2.
    - Take 7 books from shelf 3.
    - Take 9 books from shelf 4.
    You have taken 19 books, so return 19.
    It can be proven that 19 is the maximum number of books you can take.
    Example 2:

    Input: books = [7,0,3,4,5]
    Output: 12
    Explanation:
    - Take 3 books from shelf 2.
    - Take 4 books from shelf 3.
    - Take 5 books from shelf 4.
    You have taken 12 books so return 12.
    It can be proven that 12 is the maximum number of books you can take.
    Example 3:

    Input: books = [8,2,3,7,3,4,0,1,4,3]
    Output: 13
    Explanation:
    - Take 1 book from shelf 0.
    - Take 2 books from shelf 1.
    - Take 3 books from shelf 2.
    - Take 7 books from shelf 3.
    You have taken 13 books so return 13.
    It can be proven that 13 is the maximum number of books you can take.
    SmiteChow
        6
    SmiteChow  
       2023-06-15 09:40:12 +08:00
    废话生成器而已,不要抱有幻想
    JasonLaw
        7
    JasonLaw  
       2023-06-15 10:59:28 +08:00 via iPhone
    Subscribe to unlock.

    Thanks for using LeetCode! To view this question you must subscribe to premium.

    😭
    Alan3
        8
    Alan3  
       2023-06-15 12:19:54 +08:00
    def max_books(books):
    n = len(books)
    max_books = max(books)
    # dp[i][j] = max books we can take if we take j books from shelf i
    dp = [[0]*(max_books+1) for _ in range(n+1)]
    for i in range(1, n+1):
    for j in range(1, max_books+1):
    if j > books[i-1]: continue
    for k in range(j):
    dp[i][j] = max(dp[i][j], dp[i-1][k] + j)
    return max(max(row) for row in dp)

    books = [8,5,2,7,9]
    # books = [7,0,3,4,5]
    # books = [8,2,3,7,3,4,0,1,4,3]
    print(max_books(books)) # Output: 19


    不知道解法正确不,但是我测试这几个例子输出一致,切特急皮特 给的答案
    Alan3
        9
    Alan3  
       2023-06-15 12:22:59 +08:00
    @Alan3 #8 上一条好像格式乱了: https://imgur.com/a/ZGJgmaz
    Alan3
        10
    Alan3  
       2023-06-15 12:25:46 +08:00
    @Alan3 #9 [img][/img]
    Alan3
        11
    Alan3  
       2023-06-15 12:55:26 +08:00
    吃饭的时候,大致看了一下 chatgpt 给出的代码,解法清晰,嘎嘎正确!!
    jmk92
        12
    jmk92  
       2023-06-15 15:46:05 +08:00
    你好,这是一个有趣的问题。根据我从网上搜索的信息,这个问题可以用动态规划来解决 https://www.luogu.com.cn/problem/CF1433B https://songhayoung.github.io/2022/08/02/PS/LeetCode/maximum-number-of-books-you-can-take/。动态规划的思路是,用一个数组 dp[i]表示从第 0 本书到第 i 本书能取走的最大数量,那么 dp[i]可以由 dp[j]和 books[j+1...i]之间的关系得到,其中 j 是满足 books[j+1...i]是一个递增序列的最小下标。具体地,如果 books[j+1...i]是一个递增序列,那么 dp[i] = dp[j] + books[i] - books[j+1] + 1 ,否则 dp[i] = dp[i-1]。最后,返回 dp[n-1]即可。

    下面是一个用 Python 写的可能的代码实现:

    def max_books(books):
    n = len(books) # the number of books
    dp = [0] * n # the array of maximum books
    for i in range(n):
    j = i - 1 # the index of the previous book
    while j >= 0 and books[j] >= books[j+1]: # find the smallest j such that books[j+1...i] is increasing
    j -= 1
    if j >= 0: # if such j exists
    dp[i] = dp[j] + books[i] - books[j+1] + 1 # update dp[i] by adding the difference of books and one
    else: # otherwise
    dp[i] = books[i] # dp[i] is just the number of books at i
    if i > 0: # if not the first book
    dp[i] = max(dp[i], dp[i-1]) # compare with the previous book
    return dp[n-1] # return the final answer

    来自 newbing 的答案
    jmk92
        13
    jmk92  
       2023-06-15 15:46:45 +08:00
    This is a dynamic programming problem, where we can keep track of the maximum number of books we can take up to a given shelf i.

    Let's define dp[i] as the maximum number of books we can take from shelves 0 to i (inclusive) while satisfying the condition that we must take strictly fewer books from shelf j than shelf j+1 for all j between 0 and i-1.

    For each i, we need to find the maximum value of dp[j] + sum(books[j+1:i+1]) for 0 <= j < i, where sum(books[j+1:i+1]) represents the total number of books in the section from j+1 to i.

    The reason why we use this formula is because we need to make sure that we take fewer books from shelf j compared to shelf j+1, so we need to add the sum of books from j+1 to i to dp[j]. We take the maximum value of this expression for all j between 0 and i-1 to get dp[i].

    Finally, the answer will be the maximum value of dp[i] for all i between 0 and n-1.

    Here's the Python code:

    def max_books(books):
    n = len(books)
    dp = [books[0]] + [0]*(n-1)

    for i in range(1, n):
    for j in range(i):
    if books[j] < books[i]:
    dp[i] = max(dp[i], dp[j] + sum(books[j+1:i+1]))

    return max(dp)

    # Example usage:
    print(max_books([8,5,2,7,9])) # Output: 19
    print(max_books([7,0,3,4,5])) # Output: 12
    print(max_books([8,2,3,7,3,4,0,1,4,3])) # Output: 13
    jmk92
        14
    jmk92  
       2023-06-15 15:47:25 +08:00
    上一条是来自开放猫的答案,懂得麻烦对比下,正确性如何
    wangpugod2003
        15
    wangpugod2003  
    OP
       2023-06-15 15:55:55 +08:00
    不对,大家可以用三个测试用例自己跑下测试下。chatGPT 给出的结果和跑出来的不等。
    这个题要用 DP+单调栈去解,确实挺难的。
    jmk92
        16
    jmk92  
       2023-06-15 16:13:30 +08:00
    重新问 newbing ,并要求用 DP+单调栈去解,得到如下:
    jmk92
        17
    jmk92  
       2023-06-15 16:13:40 +08:00
    你给出的题目是 https://www.bing.com/search?form=SKPBOT&q=2355.%20Maximum%20Number%20of%20Books%20You%20Can%20Take ,这是一个动态规划和单调栈的结合问题。动态规划的思路是,对于每个位置 i ,我们维护一个 dp[i] 表示以 i 为右端点的区间能取到的最大书籍数。我们可以用一个单调栈来维护一个递减的序列,当我们遇到一个比栈顶元素小的数时,我们就找到了一个合法的区间,然后更新 dp[i] 为 dp[j] + (i - j) * books[i] ,其中 j 是栈顶元素的下标。这样我们就可以在 O(n) 的时间内求出所有的 dp[i] ,然后取最大值即可。我用 C++ 写了一段代码,你可以参考一下:

    #include <iostream>
    #include <vector>
    #include <stack>
    using namespace std;

    int maxBooks(vector<int>& books, int l, int r) {
    int n = books.size();
    vector<int> dp(n + 1, 0); // dp[i] means the max books we can take from [0, i]
    stack<int> st; // a monotonic decreasing stack
    st.push(0); // a dummy element
    int ans = 0;
    for (int i = 1; i <= n; i++) {
    while (!st.empty() && books[st.top()] > books[i]) {
    // we find a valid interval [j + 1, i]
    int j = st.top();
    st.pop();
    dp[i] = max(dp[i], dp[j] + (i - j) * books[i]);
    }
    st.push(i);
    if (i >= l && i <= r) {
    // update the answer if i is in the range
    ans = max(ans, dp[i]);
    }
    }
    return ans;
    }

    int main() {
    vector<int> books = {8, 5, 2, 7, 9};
    int l = 1, r = 4;
    cout << maxBooks(books, l, r) << endl; // output: 19
    return 0;
    }
    wangpugod2003
        18
    wangpugod2003  
    OP
       2023-06-15 16:26:41 +08:00
    @jmk92 这个看起来靠谱,思路是对的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2555 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 21ms · UTC 10:31 · PVG 18:31 · LAX 02:31 · JFK 05:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.