交流｜面向 ChatGPT 学习算法

10182

2023.03.05

2023.03.20

发布于未知归属地

我最近已经对 ChatGPT 产生了依赖性，有了问题已经不是第一时间去搜索引擎找答案，而是下意识想一下这个问题是应该先问搜索引擎还是先问 ChatGPT …… 而且两种选择基本已经达到五五开的程度了，我感觉 ChatGPT 让弱弱的我变得更快更高更强了！！

毫无疑问，ChatGPT 可以帮助我们更好地学习算法，可具体是在哪些方面呢？下面我将给出几个亲身体会的案例，希望能够给到各位一些路子和灵感。

算法题目解答
算法题解辅导
修正错误代码
代码翻译
规范代码
题单推荐
快乐玩耍

「算法题目解答」

最直接地，我们可以向 ChatGPT 提问算法题，并针对某些细节或疑问展开讨论。

以 51. N 皇后为例，ChatGPT 不仅可以给出完整解法，还可以根据我们的步步追问来给出对应的解答。

=== User ===

请给出以下算法题的解题思路和代码，并满足以下需求：

代码可以在 LeetCode 中国站（力扣）运行；
代码需要包含详细的中文注释，解释各部分代码的含义；
给出复杂度分析；

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

=== ChatGPT ===

解题思路

使用回溯算法，从第一行开始，逐行放置皇后。在每一行中，检查每个位置是否可以放置皇后。如果可以，则将皇后放置在该位置，并递归到下一行。如果不能，则继续检查下一个位置。如果在某一行中找不到可以放置皇后的位置，则回溯到上一行，重新选择一个位置放置皇后。

由于每个皇后都必须位于不同的行、列和对角线上，因此可以使用三个数组分别记录某一列、某一对角线和某一反对角线是否已经放置了皇后。

代码实现

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.')); // 初始化棋盘
        vector<bool> col(n, false); // 列是否已有皇后
        vector<bool> diag(n * 2 - 1, false); // 对角线是否已有皇后
        vector<bool> anti_diag(n * 2 - 1, false); // 反对角线是否已有皇后
        backtrack(res, board, col, diag, anti_diag, 0, n);
        return res;
    }

    void backtrack(vector<vector<string>>& res, vector<string>& board, vector<bool>& col, vector<bool>& diag, vector<bool>& anti_diag, int row, int n) {
        if (row == n) { // 找到一种解法
            res.push_back(board);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !diag[row - i + n - 1] && !anti_diag[row + i]) { // 当前位置可以放置皇后
                board[row][i] = 'Q'; // 放置皇后
                col[i] = true; // 标记列
                diag[row - i + n - 1] = true; // 标记对角线
                anti_diag[row + i] = true; // 标记反对角线
                backtrack(res, board, col, diag, anti_diag, row + 1, n); // 递归到下一行
                board[row][i] = '.'; // 回溯
                col[i] = false; // 回溯
                diag[row - i + n - 1] = false; // 回溯
                anti_diag[row + i] = false; // 回溯
            }
        }
    }
};

时间复杂度为 O(n!)，其中 n 是皇后数量。在回溯过程中，每个皇后可以放置在 n 个位置中的任意一个位置，因此总共有 n^n 种可能的方案。但是，由于每个皇后必须位于不同的行、列和对角线上，因此实际上只有 n! 种不同的方案。在回溯过程中，每个皇后最多可以放置在 n-1 个位置中，因此回溯的时间复杂度为 O(n!)。

=== User ===

空间复杂度呢？

=== ChatGPT ===

空间复杂度为 O(n)，其中 n 是皇后数量。需要使用四个数组，每个数组的长度都是 n。在回溯过程中，需要使用递归调用栈，递归深度最大为 n，因此空间复杂度为 O(n)。

=== User ===

详细解释一下这三行的工作原理：

col[i] = true; // 标记列
diag[row - i + n - 1] = true; // 标记对角线
anti_diag[row + i] = true; // 标记反对角线

=== ChatGPT ===

这三行代码的作用是标记当前皇后放置的位置所在的列、对角线和反对角线已经有皇后了。

具体来说，对于当前皇后放置的位置 (row, i)，它所在的列的下标为 i，它所在的对角线的下标为 row - i + n - 1，它所在的反对角线的下标为 row + i。因此，分别将 col[i]、diag[row - i + n - 1] 和 anti_diag[row + i] 设置为 true，表示它们已经有皇后了。

这样做的目的是为了在放置下一个皇后时，可以快速判断该皇后是否与已经放置的皇后在同一列、对角线或反对角线上。如果是，则该位置不可放置皇后。

=== User ===

为什么"它所在的对角线的下标为 row - i + n - 1，它所在的反对角线的下标为 row + i"？

=== ChatGPT ===

在一个 n 皇后问题中，每个皇后所在的行、列和对角线都是不同的。

对于对角线，它们可以分为两类：正对角线和反对角线。

对于正对角线，它们的特点是行下标和列下标之和相等。例如，在一个 4 皇后问题中，(0, 0) 和 (3, 3) 在同一条正对角线上，它们的行下标和列下标之和都为 0。

对于反对角线，它们的特点是行下标和列下标之差相等。例如，在一个 4 皇后问题中，(0, 3) 和 (3, 0) 在同一条反对角线上，它们的行下标和列下标之差都为 3。

因此，对于一个位置 (row, i)，它所在的正对角线的下标为 row + i，它所在的反对角线的下标为 row - i。但是，由于数组下标不能为负数，因此需要将 row - i 转换为非负数，即 row - i + n - 1。这样，对于任意一个位置 (row, i)，它所在的正对角线和反对角线的下标都可以用 row + i 和 row - i + n - 1 表示。

「算法题解辅导」

看不懂题解是经常遇到的情况，我们可以把题解文章或代码喂给 ChatGPT ，让他给出更加详实的解释。同时，我们也可以针对某个难点、某几行代码提出针对性的提问，ChatGPT 也能够根据上下文来给你解答。并且，可以让 ChatGPT 来推荐几道相关题目，通过练习提升熟练度。

下面我们以我在剑指 Offer 38. 字符串的排列写的题解为例。

=== User ===

以下是一个算法题目：

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

以下是上述题目的解答代码：

class Solution:
    def permutation(self, s: str) -> List[str]:
        c, res = list(s), []
        def dfs(x):
            if x == len(c) - 1:
                res.append(''.join(c))   # 添加排列方案
                return
            dic = set()
            for i in range(x, len(c)):
                if c[i] in dic: continue # 重复，因此剪枝
                dic.add(c[i])
                c[i], c[x] = c[x], c[i]  # 交换，将 c[i] 固定在第 x 位
                dfs(x + 1)               # 开启固定第 x + 1 位字符
                c[i], c[x] = c[x], c[i]  # 恢复交换
        dfs(0)
        return res

能给我解释一下吗？并给代码添加完整的注释。

=== ChatGPT ===

当我们需要求一个字符串的所有排列时，可以使用回溯算法来解决。这个算法的基本思路是，从第一个字符开始，依次将每个字符放到第一个位置，然后递归求解剩下的字符的排列，直到所有字符都被固定在某个位置上，得到一个排列方案。

具体来说，对于一个长度为 n 的字符串，我们可以从第一个字符开始，依次将每个字符固定在第一个位置上，然后递归求解剩下的 n-1 个字符的排列。这个递归过程可以使用 DFS 来实现。在 DFS 过程中，我们需要记录哪些字符已经被固定在某个位置上，以避免重复计算。

以下是上述题目的解答代码的详细解释：

class Solution:
    def permutation(self, s: str) -> List[str]:
        c, res = list(s), []  # 将字符串转换为字符列表，初始化结果数组
        def dfs(x):
            if x == len(c) - 1:  # 如果已经固定了所有字符，得到一个排列方案
                res.append(''.join(c))   # 添加排列方案
                return
            dic = set()  # 使用集合来记录哪些字符已经被固定在某个位置上
            for i in range(x, len(c)):  # 枚举所有可能的字符
                if c[i] in dic: continue # 如果该字符已经被固定在某个位置上，跳过
                dic.add(c[i])  # 将该字符添加到集合中
                c[i], c[x] = c[x], c[i]  # 交换，将 c[i] 固定在第 x 位
                dfs(x + 1)               # 开启固定第 x + 1 位字符的递归
                c[i], c[x] = c[x], c[i]  # 恢复交换
        dfs(0)  # 从第一个字符开始递归
        return res  # 返回所有的排列方案

在上面的代码中，我们使用了一个集合 dic 来记录哪些字符已经被固定在某个位置上。在枚举可能的字符时，如果该字符已经被固定在某个位置上，就跳过，以避免重复计算。在交换字符时，我们将当前字符 c[i] 固定在第 x 位上，然后递归求解剩下的字符的排列。在递归结束后，我们需要恢复交换，以便进行下一次枚举。

最后，我们将所有的排列方案添加到结果数组 res 中，并返回。

=== User ===

c[i], c[x] = c[x], c[i]  # 交换，将 c[i] 固定在第 x 位
dfs(x + 1)               # 开启固定第 x + 1 位字符的递归
c[i], c[x] = c[x], c[i]  # 恢复交换

这里的交换与恢复交换是什么意思？为什么要恢复交换？

=== ChatGPT ===

在这个回溯算法中，我们需要将字符列表 c 中的某个字符固定在某个位置上，以便递归求解剩下的字符的排列。为了实现这个目的，我们需要交换字符列表中的两个字符，将当前字符固定在某个位置上。具体来说，我们将当前字符 c[i] 与位置 x 上的字符 c[x] 交换，将 c[i] 固定在第 x 位上。

在递归求解剩下的字符排列时，我们需要将当前字符 c[i] 固定在第 x 位上，并递归求解剩下的字符排列。当递归返回后，我们需要恢复交换，将字符列表 c 恢复到递归前的状态。具体来说，我们需要再次交换字符 c[i] 和 c[x] 的位置，以便进行下一次枚举。

为什么要恢复交换？因为在递归求解剩下的字符排列时，我们需要将当前字符 c[i] 固定在第 x 位上，并递归求解剩下的字符排列。如果不恢复交换，那么固定在第 x 位上的字符将会一直存在于字符列表 c 中，影响后续的排列计算。因此，在递归返回后，我们需要恢复交换，将字符列表 c 恢复到递归前的状态，以便进行下一次枚举。

=== User ===

该代码的时间复杂度是多少？如何推算？

=== ChatGPT ===

该代码的时间复杂度是 $O (n \times n!)$ ，其中 $n$ 是字符串的长度。

在这个回溯算法中，我们需要枚举所有可能的字符排列，因此时间复杂度至少是 $O (n!)$ 。对于每个排列，我们需要将其添加到结果数组中，这需要 $O (n)$ 的时间。因此，总时间复杂度是 $O (n \times n!)$ 。

在具体的实现中，我们使用了一个集合来记录哪些字符已经被固定在某个位置上，以避免重复计算。集合的大小最多为 $n$ ，因此每次操作集合的时间复杂度是 $O (1)$ 。因此，集合操作的时间复杂度为 $O (n \times n!)$ 。

综上所述，该算法的时间复杂度是 $O (n \times n!)$ 。

=== User ===

能给我推荐几道类似的题目吗？

=== ChatGPT ===

当然可以，以下是几道与字符串排列相关的题目：

全排列问题：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。LeetCode 题目链接：https://leetcode-cn.com/problems/permutations/
字符串的排列：输入一个字符串，打印出该字符串中字符的所有排列。LeetCode 题目链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
电话号码的字母组合：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。LeetCode 题目链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
括号生成：生成所有由 n 对括号组成的有效组合。LeetCode 题目链接：https://leetcode-cn.com/problems/generate-parentheses/
N 皇后问题：在 n x n 的棋盘上，放置 n 个皇后，并使它们互相攻击不到。LeetCode 题目链接：https://leetcode-cn.com/problems/n-queens/

「修正错误代码」

如果不清楚代码为什么无法通过、运行超时等问题，可以直接让 ChatGPT 帮你勘误并修正。

下面以一位扣友在剑指 Offer 12. 矩阵中的路径中的提问为例。

=== User ===

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

针对以上算法问题，以下代码为什么无法通过，会运行超时？

class Solution {
public:
    bool process(vector<vector<char>> board, string word , int x , int y , int step){
        if(x<0||x==board.size()||y<0||y==board[0].size()||board[x][y]=='0'||board[x][y]!=word[step])return false;
        if(step==word.size()-1)return true;
        board[x][y] = '0';
        return process(board , word , x-1 , y , step+1)||process(board , word , x , y+1 , step+1)||process(board , word , x+1 , y , step+1)||process(board , word , x , y-1 , step+1);
    }
 
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0 ; i<board.size() ; i++){
            for(int j = 0 ; j<board[0].size() ; j++){
                if(process(board , word , i , j , 0))return true;
            }
        }
        return false;
    }
};

=== ChatGPT ===

这段代码的时间复杂度为 $O ((mn)^{4})$ ，因为对于每个起点 $(i, j)$ ，都会进行一次深度优先搜索，而在每一次搜索中，都会尝试向四个方向进行搜索，所以最多会进行 $(mn)^{4}$ 次搜索。这样的时间复杂度非常高，导致程序无法通过测试用例，出现超时的情况。

为了优化这段代码，可以考虑使用剪枝来减少搜索次数。具体来说，可以在搜索过程中，对于已经搜索过的字符进行标记，避免重复搜索。这样可以避免在同一个单元格内的字母被重复使用的情况，从而减少搜索次数，提高程序的效率。同时，也可以在搜索过程中，对于已经搜索到的路径长度进行判断，如果已经超过了目标单词的长度，就可以直接返回 false，避免继续搜索无用的路径。

下面是优化后的代码：

class Solution {
public:
    bool process(vector<vector<char>>& board, string& word, int x, int y, int step) {
        if (step == word.size()) return true;
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] != word[step]) return false;
        char temp = board[x][y];
        board[x][y] = '0';
        bool res = process(board, word, x+1, y, step+1) || process(board, word, x-1, y, step+1)
                   || process(board, word, x, y+1, step+1) || process(board, word, x, y-1, step+1);
        board[x][y] = temp;
        return res;
    }

    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (process(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
};

在优化后的代码中，我们首先判断当前搜索的路径长度是否已经等于目标单词的长度，如果是，就直接返回 true。否则，我们判断当前搜索的位置是否越界，或者当前位置的字符是否与目标单词中对应位置的字符不同，如果是，就返回 false。如果当前位置的字符与目标单词中对应位置的字符相同，我们就将当前位置的字符标记为已经搜索过，然后向四个方向进行搜索。搜索完之后，我们将当前位置的字符恢复原来的值，然后返回搜索结果。这样，我们就可以通过剪枝来减少搜索次数，提高程序的效率。

「代码翻译」

ChatGPT 不仅能够翻译各国语言，还可以翻译编程语言。比如某个题解没有提供我们写的语言，则可以求助 ChatGPT 来翻译，并且可以提出多个附加条件，按照需求“定制化”代码。

下面以剑指 Offer 41. 数据流中的中位数为例。我们注意到，虽然 Pyhton 的 heap 语法和 C++ 差距很大，但 ChatGPT 依然可以很好地翻译出可一键运行的代码。

=== User ===

请帮忙把以下代码从 Python 翻译至 C++ ，并且满足以下条件：

代码可以在 LeetCode 中国站（力扣）运行；
将下划线命名替换为驼峰命名；
保留原代码中的注释；

from heapq import *

class MedianFinder:
    def __init__(self):
        self.A = [] # 小顶堆，保存较大的一半
        self.B = [] # 大顶堆，保存较小的一半

    def addNum(self, num: int) -> None:
        if len(self.A) != len(self.B):
            heappush(self.A, num)
            heappush(self.B, -heappop(self.A))
        else:
            heappush(self.B, -num)
            heappush(self.A, -heappop(self.B))
     
    def findMedian(self) -> float:
        return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0

=== ChatGPT ===

#include <queue>
using namespace std;

class MedianFinder {
public:
    priority_queue<int, vector<int>, greater<int>> A; // 小顶堆，保存较大的一半
    priority_queue<int, vector<int>, less<int>> B;    // 大顶堆，保存较小的一半

    void addNum(int num) {
        if (A.size() != B.size()) {
            A.push(num);
            B.push(A.top());
            A.pop();
        } else {
            B.push(num);
            A.push(B.top());
            B.pop();
        }
    }
    
    double findMedian() {
        if (A.size() != B.size()) return A.top();
        else return (A.top() + B.top()) / 2.0;
    }
};

「规范代码」

如果我们想要知道自己编写的代码是否规范，在哪个部分可以提升，那么 ChatGPT 可以给出非常好的 clean code 建议。

我们以剑指 Offer 12. 矩阵中的路径的解题代码为例。

=== User ===

请评判一下这段 Python 代码的规范性，以及有什么可改进之处？

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True
            board[i][j] = ''
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = word[k]
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False

=== ChatGPT ===

这段 Python 代码的规范性还不错，但还有一些可改进之处：

函数和变量名：函数名和变量名应该具有描述性，让人容易理解其作用。在这段代码中，函数名 dfs 可以改为更具描述性的名称，比如 search_word。变量名 i、j、k 不错，但建议在代码中加上注释，以便更好地理解其作用。
注释：在代码中加上注释可以帮助其他人更好地理解代码的作用和逻辑。在这段代码中，可以在函数定义前加上注释，解释函数的作用和输入输出参数的含义。
代码格式：在这段代码中，缩进和空格使用得很好。但建议在二元运算符两侧加上空格，以提高代码的可读性。例如，将 i + 1 改为 i+1。
异常处理：在这段代码中，没有对输入参数进行异常处理。建议在函数开头加上参数检查，以避免出现异常情况。
可读性：在这段代码中，可以通过拆分长表达式和加上空行来提高代码的可读性。例如，可以将 res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1) 改为：

res = dfs(i + 1, j, k + 1) or \
      dfs(i - 1, j, k + 1) or \
      dfs(i, j + 1, k + 1) or \
      dfs(i, j - 1, k + 1)

并在函数定义和循环之间加上空行，以提高代码的可读性。

综上所述，这段 Python 代码的规范性还不错，但还有一些可改进之处。通过优化函数和变量名、加上注释、改进代码格式、增加异常处理和提高可读性，可以让代码更易于理解和维护。

「题单推荐」

我们可以让 ChatGPT 推荐各类算法学习资料。然而，根据我的测试，ChatGPT 可能会给出一些并不存在的学习资源，或者与提问方向有一定差距的材料。

=== User ===
请推荐力扣网站上适合初学者的算法题单。

=== ChatGPT ===
当然可以！力扣网站上有很多适合初学者的算法题单，以下是我为你推荐的几个：

算法基础课程：这个题单是力扣官方推荐的，它包含了一些基础的算法题目，适合初学者入门。这些题目的难度较低，但涵盖了一些基本的算法思想，比如递归、分治、贪心等。
数据结构基础课程：这个题单也是力扣官方推荐的，它包含了一些基础的数据结构题目，比如数组、链表、栈、队列等。这些题目的难度较低，但可以帮助初学者掌握数据结构的基本概念和操作。
LeetCode 101：这个题单是一位 LeetCode 用户整理的，它包含了一些比较经典的算法题目，适合初学者练习。这些题目的难度较低，但可以帮助初学者熟悉算法的常见思想和技巧。
剑指 Offer：这个题单是一本算法面试指南的题目集合，适合初学者练习。这些题目的难度较低，但可以帮助初学者了解算法面试的常见题型和要求。

希望这些题单能够帮助你入门算法，加油！

「快乐玩耍」

随便问，ChatGPT 来者不拒！

=== User ===

写一个"数据结构"和"算法"之间的 Rap 对战。

=== ChatGPT ===

Yo，这里有个数据结构和算法的Rap对战，
两者互相较量，看谁更强。

首先，数据结构出场，它是程序的基础，
像数组、链表、栈、队列、树、图，
这些都是它的代表，让程序更加有力。

然而，算法也不甘示弱，它是程序的灵魂，
像贪心、分治、动态规划、回溯、搜索，
这些都是它的代表，让程序更加精准。

数据结构说：“我是程序的基础，没有我，算法一无所用。
我的存储和操作，让程序更加高效。”

算法回应：“我是程序的灵魂，没有我，数据结构无从施展。
我的思路和算法，让程序更加优秀。”

数据结构说：“我有数组，顺序存储，操作随心所欲。
我有链表，链式存储，插入删除自如。”

算法回应：“我有贪心，局部最优，全局最优不在话下。
我有分治，问题分解，递归求解效率高。”

数据结构说：“我有树，层次结构，遍历有技巧。
我有图，复杂结构，搜索有套路。”

算法回应：“我有动态规划，状态转移，最优解不可挡。
我有回溯，状态回溯，穷举求解效果佳。”

数据结构和算法，两者互相协作，
像火药和炮弹，一起才能爆发。
数据结构是炮弹的身体，算法是火药的灵魂，
一起才能让程序更加完美。

所以，数据结构和算法，没有谁更强，
只有相互搭配，才能让程序更加优秀。

「一则思考」

对于基础科学家来讲，“提出问题”的能力比“解决问题”的能力更加关键。ChatGPT 的出现让我感到这一点对工程师群体同样适用，因为以前遇到问题都是问老师、问同学，我们已经习惯了对方强大的理解能力和对不清不楚问题描述的适应性；或者一般找不到人问，就自己搜索消化问题。

在与 ChatGPT 交流的体验过程中，我发现提问有许多技巧，包括准确描述问题、排除无效信息、给足上下文、说清楚限定条件等。ChatGPT 大模型肚子里的墨水足够多，问题是我们不一定能将它们勾出来。

当然，随着 ChatGPT 不断演进，模型的统计能力、单 token 成本都会得到进一步优化，对于提问者的要求也会越来越低。从当前的体验和 OpenAI 的更新发布频率来看，我感觉钢铁侠中 Jarvis 诞生的那一天不会到来的太晚。