用自然语言让AI打leetcode周赛
还在自己吭哧吭哧打算法平台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, 0
res = []
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 0
s = grid[i][j]
grid[i][j] = 0
s += dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)
return s
res = 0
for 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 SortedList
class 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 = 0
li = -1
while 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 = i
return 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 如果您有任何疑问或需要解释的地方。我很乐意提供帮助。代码提交结果：
实践后的思考
对于这个问题最初的想法就来自于在AI助手有了突破之后，尝试能否通过自然语言编程来代替程序语言编程。
自然语言编程指的是使用我们日常语言来表达计算机程序的概念和算法，而非传统的程序语言如C++和Python等。
自然语言具有良好的表达形式，更易于理解和表述，更加亲和易懂，人们可以用最自然的语言来表达自己的思想和创意，而无需陷入复杂的程序语言语法。
自然语言编程可以让人们更为容易得表达自己的需求，并快速实现理想中的功能。
然而，自然语言编程也存在明显劣势。
首先，自然语言表达是模糊的和不精确的。我们所讲的语言中，存在很多概念和意思是相对的和依赖语境的，这些难以在计算机程序中得到明确和一致的表达，这都给程序的理解使用和调试带来了很大困难。
其次，自然语言难以表达计算机程序需要的精确和严谨的概念，它自身的严谨性不够。
程序语言提供了形式化的语法和丰富的数据类型来定义程序逻辑，给出程序的统一性标准，有着共同的语言约定和对应规则，这都是自然语言很难达到的。
最后，要实现人与机器之间完全自然的语言交互和理解，这需要机器具备广泛而深入的知识水平和推理能力，而人工智能能否准确理解这些，需要标准来进行评估。目前的自然语言处理技术能否完全理解人类语言的深层次含义,实现人与机器完全自然的语言交互仍然需要商榷。
通过使用Claude打leetcode周赛，对于如何使用自然语言描述程序多了一点自己的认识。
自然语言可以表达所有的程序语言，具有更宽泛的表达能力。事实上，在学习和解释任何一门程序语言时，所依赖的都是自然语言。
程序语言本质上只是人与机器间的一种中间沟通工具，而其实这些年它的发展也在不断地从机器可解析的形式向更加贴近人类理解的自然语言靠拢，更偏人类正常沟通的方向靠近。
所以，程序语言并不比自然语言本身拥有更强的表达能力。相反，自然语言可以承载更丰富、更广泛的概念，实现更加抽象和深层次的思维传达。
程序语言之所以存在，其目的就在于让机器可以理解人类用自然语言表达的思想和逻辑。因此，程序语言并不是一个更优于自然语言的表现形式。
实践发现，在书写自然语言编程描述时，需要着重考虑到以下几个参考点：
语言表述：用尽可能精准自然的语言来进行沟通回复，避免重复性词语，尽可能不使用可能/或许这种不确定性的描述。
语义理解：过于复杂或者专业的表达会增加理解难度，需要补充更为清晰易懂的技术背景，会得到更好的输出。
交互模式：用更为直接明了的命令形式进行表达，虽然不及聊天形式自然，但更为清晰简明。
规范结构：需要在表达方式和交互规则上增加一定框架，对输入输出都会有更为直观的展示。
以上这些只是一些想法，自然语言编程背后涉及的知识和技术远不止此。
能超过50%的周赛参与者
用AI编写程序，为什么不选择热度最高的ChatGPT，或其他生成代码专用AI？就这个问题背后的原因，量子位询问了萧雅本人。
她表示，没有选择生成代码专用AI是因为想用最根本的模型进行解答，再考虑到所有输入是中文+代码，有10万token的Claude对中文的理解和处理优于ChatGPT等产品。
实际体验后她得出结论，通过与AI的交互来完成编程这种方法在某些步骤和环节比手写代码节省时间，尤其是改bug和学习新语言的时间。
“比如说本身对c++非常熟悉，而可能这个代码需要python书写才能更匹配，哪怕对语言不是很了解，但是整体的思路和想法有很大共通的。”她补充解释道，“这个语言做的好的地方，相对的那个语言应该也会有对应的库，但是可以在不那么精通另一个语言的情况下依然很好的书写代码。”
虽然能加快变成速度，但新方法还是没有办法超过90%-100%的作答者，不过至少能超过50%的周赛参与者。
理由是这种自然语言编程的方法和近些年的编程语言发展模式很接近，让语言设计都更偏向于人类，而远离计算机硬件。
此外，这个方法和人的学习过程是一致的，人在学习编程语言的时候都是用自然语言进行解释的，这是最好的描述工具。
她举例说，团队合作书写代码的时候，所有代码的描述也是通过自然语言说清楚再进行思维碰撞，这种方法可以很大程度提高工作效率。
最终目标肯定是直接给出题目就可以让AI进行解答，现在是做不到这点的，这种方法只是AI书写代码的其中一步。
