AI打LeetCode周赛进入前10%！秘诀：自然语言编程

张晓雅投稿自凹非寺
量子位 | 公众号 QbitAI

还在自己吭哧吭哧打算法平台Leetcode的周赛？为什么不试试神奇的ChatGPT类AI呢！

用AI助手Claude参加第103场周赛，共四道题，均完成了AC，能达到参与者前10%的成绩。

事情的起因是知乎上一位叫萧雅的用户尝试使用AI进行编程，但在测试过程中，她发现直接给出题目让AI进行编程并输出结果的方法，效果并不理想。

于是一种大胆的想法诞生了：使用自然语言配合逐步的思路描述，通过与AI的交互来完成编程。

具体操作中，她选择了Anthropic公司出品的ChatGPT最强竞品——Claude这个AI助手，并选取了Leetcode第103场双周赛来完成实验。

整体的解答过程遵循以下几点要求：

全程使用自然语言进行描述，通过一次沟通完成输出，因此下文所有发给Claude的指令均可以复现。
采用问题描述、解答思路、以及开头书写要求作为提问固定格式。
编程采用python代码输出。

最终测试结果是，可以认为通过自然语言+解答思路发送给AI进行编程是可行的。

以下是测试全过程：

用自然语言让AI打leetcode周赛

Leetcode第103场周赛题目1如下，k个元素的最大和：

发给Claude指令如下：

问题描述如下：
'''
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次，最大化你的得分：
1.从 nums 中选择一个元素 m 。
2.将选中的元素 m 从数组中删除。
3.将新元素 m + 1 添加到数组中。
4.你的得分增加 m 。
请你返回执行以上操作恰好 k 次后的最大得分。
'''
解答思路如下：
'''
由于最大值加一后还是最大值，那么反复利用最大值即可。
设数组的最大值为m，答案就是m+(m+1)+(m+2)+⋯+(m+k−1)= [(2m+k−1)⋅k]/2
'''
请用python3书写，并以下面这行作为开头。
class Solution:def maximizeSum(self, nums: List[int], k: int) -> int:

Claude回复内容如下：

这里是python代码实现:
python
class Solution:def maximizeSum(self, nums: List[int], k: int) -> int:m = max(nums)return (2*m + k - 1) * k // 2
解答思路:
1. 首先找到数组中的最大值m。
2. 然后最大的得分公式为:m + (m+1) + (m+2) + ... + (m+k-1)= (m + (m+k-1)) * k / 2= (2*m + k - 1) * k / 2
3. 直接返回计算结果。
时间复杂度:O(n)。需要遍历数组一次得到最大值。
空间复杂度:O(1)。
这个解法直接利用了最大值与k的关系来得到最终结果,没有实际操作数组。所以时间和空间复杂度都比较低。
请 let me know 如果您有任何疑问或需要解释的地方。我很乐意提供帮助。

代码提交结果：

周赛题目2如下，找到两个数组的前缀公共数组：

发给Claude指令如下：

问题描述如下：
'''
给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。
A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。
请你返回 A 和 B 的 前缀公共数组 。
如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。
'''
解答思路如下：
'''
1.存储公共前缀的大小
2.存储 a 和 b 中已经匹配过的元素
3.同时遍历 a 和 b 中的元素
4.将 a 中的当前元素 x 对应的二进制位置为 1，标记为已匹配
5.将 b 中的当前元素 y 对应的二进制位置为 1，标记为已匹配
6.计算当前公共前缀的大小，即 p 和 q 的二进制数中 1 的个数
7.返回公共前缀大小的列表
'''
请用python3书写，并以下面这行作为开头。
class Solution:def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:

Claude回复内容如下：

这里是优化后的python代码实现:
python
class Solution:def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:p, q = 0, 0res = []for i in range(min(len(A), len(B))):p |= 1 << A[i]q |= 1 << B[i]res.append(bin(p&q).count('1'))return res
解答思路:
1. p和q初始化为0,用来记录A和B数组中出现过的数字。
2. 同时遍历A和B数组的元素。
3. 通过p |= 1 << A[i]将A[i]位置1。
4. 通过q |= 1 << B[i]将B[i]位置1。 
5. p & q得到两个数组公共元素,然后bin(p & q).count('1')计算1的个数,得到公共元素个数c。 
6. 添加c到res。  
7. 重复3-6直到A或B数组遍历结束。
8. 返回res。
时间复杂度:O(m + n)。需要遍历两个数组。
空间复杂度:O(m + n)。需要使用res存储结果。
这种方法无需提前记录每个数字在A和B数组中出现的次数,而是在遍历的同时更新p和q,简洁高效。
请 let me know 如果您有任何疑问或需要解释的地方。我很乐意提供帮助。

代码提交结果：

周赛题目3如下，网格中鱼的最大数目：

发给Claude指令如下：

问题描述如下：
'''
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表示：
如果 grid[r][c] = 0 ，那么它是一块 陆地 。
如果 grid[r][c] > 0 ，那么它是一块 水域 ，且包含 grid[r][c] 条鱼。
一位渔夫可以从任意 水域 格子 (r, c) 出发，然后执行以下操作任意次：
捕捞格子 (r, c) 处所有的鱼，或者
移动到相邻的 水域 格子。
请你返回渔夫最优策略下， 最多 可以捕捞多少条鱼。如果没有水域格子，请你返回 0 。
格子 (r, c) 相邻 的格子为 (r, c + 1) ，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，前提是相邻格子在网格图内。
'''
解答思路如下：
'''
1.获取网格的行数和列数
2.定义深度优先搜索函数
3. 如果下标越界或网格中没有鱼，则返回 0
4.统计当前点的价值为s
5.将当前点标记成访问过，不需要重置其值
6. 四个方向进行深度优先搜索
7.将搜索到的鱼的价值累加到 s 中
8.返回能够获得的最大价值s
9.遍历所有的格子，计算其能够获得的最大价值并返回
'''
请用python3书写，并以下面这行作为开头，按照思路不要添加任何额外细节。
class Solution:def findMaxFish(self, grid: List[List[int]]) -> int:

Claude回复内容如下：

这里是精简的python代码实现:
python
class Solution:def findMaxFish(self, grid: List[List[int]]) -> int:m, n = len(grid), len(grid[0])def dfs(i, j):if not (0 <= i < m and 0 <= j < n and grid[i][j] > 0): return 0s = grid[i][j]  grid[i][j] = 0s += dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1) return sres = 0for i in range(m):for j in range(n): res = max(res, dfs(i, j))return res
解答思路:
1. 获取网格的行数m和列数n。 
2. 定义dfs函数进行深度优先搜索。  
3. 如果下标越界或网格中没有鱼,则返回 0。  
4. 统计当前点grid[i][j]的鱼的数量s。 
5. 将grid[i][j]标记为已访问,不需要重置其值 。
6. dfs搜索四个方向,并将搜索到的鱼的数量累加到s。  
7. 返回s。 
8. 遍历所有的格子,通过dfs计算其能够获得的最大价值,并更新res。 
9. 返回res。
时间复杂度:O(m*n)。需要遍历整个网格。 
空间复杂度:O(m*n)。递归深度可能达到m*n。
这是一道典型的深度优先搜索问题,需要注意状态重置。 
通过不重置grid[i][j]的值,避免了状态重置,简化了代码逻辑。
请 let me know 如果您有任何疑问或需要解释的地方。我很乐意提供帮助。

代码提交结果：

周赛题目4如下，将数组清空：

发给Claude指令如下：

问题描述如下：
'''
给你一个包含若干 互不相同 整数的数组 nums ，你需要执行以下操作 直到数组为空 ：
如果数组中第一个元素是当前数组中的 最小值 ，则删除它。
否则，将第一个元素移动到数组的 末尾 。
请你返回需要多少个操作使 nums 为空。
'''
解答思路如下：
'''
数组 nums 的长度为n
创建一个空的堆列表heap
对nums进行i,nums这个格式的遍历，再将当前元素值和对应索引组成后面格式的元组 (num, i) 加入到堆列表 heap 中，不要对这两个格式顺序做修改。
将 nums 中的所有元素及其下标加入最小堆 heap 中
用sortedcontainers里面的SortedList创建空的有序集合pos，用于存储已经删除的元素的下标
res用于存储清空数组所需的最少操作数，初始化为 0
哨兵li，上一个弹出的数的位置，初始化为-1
获取堆中的最小值，并计算清除该元素所需的步数，重复直到堆为空
如果 i 在上一个弹出元素li的后面，对于每个被弹出的元素，计算从i到li在pos中的有效元素数量d，即计算值在 li的右边且值小于 i 的元素数量。再将从当前位置到i之间的长度减去d，加入总步数 res 中
如果当前元素的位置在上一个被弹出元素 li 的前面，则计算从 li 到数组结尾的有效元素数量d，即集合中小于等于i的元素数量与集合中小于n的元素数量相加，再减去集合中小于li的元素数量为有效元素数量d。再将从当前位置 li 到数组末尾的元素数量加上i，再减去d，加入总步数res中
将元素 i 的下标加入已删除元素的有序集合pos中
更新上一个弹出的数位置
返回清空数组所需的最少操作数res
'''
请用python3书写，并以下面这行作为开头。
class Solution:def countOperationsToEmptyArray(self, nums: List[int]) -> int:

Claude回复内容如下：

这里是python代码实现:
python
from sortedcontainers import SortedListclass Solution:def countOperationsToEmptyArray(self, nums: List[int]) -> int:n = len(nums)heap = []for i, num in enumerate(nums):heappush(heap, (num, i))pos = SortedList()res = 0li = -1while heap:        num, i = heappop(heap)if i > li:                d = pos.bisect_left(i) - pos.bisect_right(li)res += i - li - d     else:             d = pos.bisect_right(n) - pos.bisect_right(li) + pos.bisect_left(i) res += n - li + i - d   pos.add(i)li = ireturn res
解答思路:
1. 数组 nums 的长度为n。 
2. 创建一个空的堆列表heap。
3. 对nums进行i,nums这个格式的遍历,再将当前元素值和对应索引组成后面格式的元组 (num, i) 加入到堆列表 heap 中,不要对这两个格式顺序做修改。
4. 用sortedcontainers里面的SortedList创建空的有序集合pos,用于存储已经删除的元素的下标。  
5. res用于存储清空数组所需的最少操作数,初始化为0。 
6. 哨兵li,上一个弹出的数的位置,初始化为-1。  
7. 获取堆中的最小值,并计算清除该元素所需的步数,重复直到堆为空。  
8. 如果i在上一个弹出元素li的后面,对于每个被弹出的元素,计算从i到li在pos中的有效元素数量d,即计算值在 li的右边且值小于 i 的元素数量。再将从当前位置到i之间的长度减去d,加入总步数res中。 
9. 如果当前元素的位置在上一个被弹出元素li的前面,则计算从li到数组结尾的有效元素数量d,即集合中小于等于i的元素数量与集合中小于n的元素数量相加,再减去集合中小于li的元素数量为有效元素数量d。再将从当前位置li到数组末尾的元素数量加上i,再减去d,加入总步数res中。  
10. 将元素i的下标加入已删除元素的有序集合pos中。   
11. 更新上一个弹出的数位置li = i。  
12. 返回清空数组所需的最少操作数res。 
时间复杂度:O(nlogn)。需要排序。 
空间复杂度:O(n)。需要堆和集合。
这是一道运用堆与有序集合的题目。通过维护哨兵位置和已删除元素,得到最优解。 
请 let me know 如果您有任何疑问或需要解释的地方。我很乐意提供帮助。

代码提交结果：