还在自己吭哧吭哧打算法平台 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+2)+?+(m+k?1)=((2m+k?1)?k)/2'''请用python3书写,并以下面这行作为开头。classSolution:defmaximizeSum(self,nums:List(int),k:int)-int:
Claude 回复内容如下:
这里是python代码实现pythonclassSolution:defmaximizeSum,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/23.直接返回计算结果。时间复杂度O(n)。需要遍历数组一次得到最大值。空间复杂度O(1)。这个解法直接利用了最大值与k的关系来得到最终结果没有实际操作数组。所以时间和空间复杂度都比较低。请letmeknow如果您有任何疑问或需要解释的地方。我很乐意提供帮助。
代码提交结果:
周赛题目 2 如下,找到两个数组的前缀公共数组:
发给 Claude 指令如下:
问题描述如下:'''给你两个下标从0开始长度为n的整数排列A和B。A和B的前缀公共数组定义为数组C,其中C是数组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书写,并以下面这行作为开头。classSolution:deffindThePrefixCommonArray(self,A:List(int),B:List(int))-List(int):
Claude 回复内容如下:
=1lt;A(i)q|=1lt;B(i)res.end(bin(pamp;q).count('1'))returnres解答思路1.p和q初始化为0用来记录A和B数组中出现过的数字。2.同时遍历A和B数组的元素。3.通过p|=1lt;lt;A(i)将A(i)位置1。4.通过q|=1lt;B(i)将B(i)位置1。5.pamp;q得到两个数组公共元素,然后bin(pamp;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简洁高效。请letmeknow如果您有任何疑问或需要解释的地方。我很乐意提供帮助。
代码提交结果:
周赛题目 3 如下,网格中鱼的最大数目:
发给 Claude 指令如下:
问题描述如下:'''给你一个下标从0开始大小为mxn的二维整数组grid,其中下标在处的整数表示:如果grid(r)(c)=0,那么它是一块陆地。如果grid(r)(c)0,那么它是一块水域,且包含grid(r)(c)条鱼。一位渔夫可以从任意水域格子出发,然后执行以下操作任意次:捕捞格子处所有的鱼,或者移动到相邻的水域格子。请你返回渔夫最优策略下,最多可以捕捞多少条鱼。如果没有水域格子,请你返回0。格子相邻的格子为(r,c+1),(r,c-1),(r+1,c)和(r-1,c),前提是相邻格子在网格图内。'''解答思路如下:'''1.获取网格的行数和列数2.定义深度优先搜索函数3.如果下标越界或网格中没有鱼,则返回04.统计当前点的价值为s5.将当前点标记成访问过,不需要重置其值6.四个方向进行深度优先搜索7.将搜索到的鱼的价值累加到s中8.返回能够获得的最大价值s9.遍历所有的格子,计算其能够获得的最大价值并返回'''请用python3书写,并以下面这行作为开头,按照思路不要添加任何额外细节。classSolution:deffindMaxFish(self,grid:List(List(int)))-gt;int:
Claude 回复内容如下:
这里是精简的python代码实现:pythonclassSolution:deffindMaxFish))-gt;int:m,n=len(grid),len(grid(0))defdfs(i,j):ifnot(0lt;=ilt;mand0lt;=jlt;nandgrid(i)(j)gt;0):return0s=grid(i)(j)grid(i)(j)=0s+=dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1)returnsres=0foriinrange(m):forjinrange(n):res=max(res,dfs(i,j))returnres解答思路: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)的值,避免了状态重置,简化了代码逻辑。请letmeknow如果您有任何疑问或需要解释的地方。我很乐意提供帮助。
代码提交结果:
周赛题目 4 如下,将数组清空:
发给 Claude 指令如下:
问题描述如下:'''给你一个包含若干互不相同整数的数组nums,你需要执行以下操作直到数组为空:如果数组中第一个元素是当前数组中的最小值,则删除它。否则,将第一个元素移动到数组的末尾。请你返回需要多少个操作使nums为空。'''解答思路如下:'''数组nums的长度为n创建一个空的堆列表heap对nums进行i,nums这个格式的遍历,再将当前元素值和对应索引组成后面格式的元组加入到堆列表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书写,并以下面这行作为开头。classSolution:defcountOperationsToEmptyArray(self,nums:List(int))-int:
Claude 回复内容如下:
这里是python代码实现:pythonfromsortedcontainersimportSortedListclassSolution:defcountOperationsToEmptyArray)-gt;int:n=len(nums)heap=()fori,numinenumerate(nums):heush(heap,(num,i))pos=SortedList()res=0li=-1whileheap:num,i=heop(heap)ifigt;li:d=pos.bisect_left(i)-pos.bisect_right(li)res+=i-li-delse:d=pos.bisect_right(n)-pos.bisect_right(li)+pos.bisect_left(i)res+=n-li+i-dpos.add(i)li=ireturnres解答思路: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)。需要堆和集合。这是一道运用堆与有序集合的题目。通过维护哨兵位置和已删除元素,得到最优解。请letmeknow如果您有任何疑问或需要解释的地方。我很乐意提供帮助。
代码提交结果:
实践后的思考
对于这个问题最初的想法就来自于在 AI 助手有了突破之后,尝试能否通过自然语言编程来代替程序语言编程。
自然语言编程指的是使用我们日常语言来表达计算机程序的概念和算法,而非传统的程序语言如 C++ 和 Python 等。
自然语言具有良好的表达形式,更易于理解和表述,更加亲和易懂,人们可以用最自然的语言来表达自己的思想和创意,而无需陷入复杂的程序语言语法。
自然语言编程可以让人们更为容易得表达自己的需求,并快速实现理想中的功能。
然而,自然语言编程也存在明显劣势。
首先,自然语言表达是模糊的和不精确的。我们所讲的语言中,存在很多概念和意思是相对的和依赖语境的,这些难以在计算机程序中得到明确和一致的表达,这都给程序的理解使用和调试带来了很大困难。
其次,自然语言难以表达计算机程序需要的精确和严谨的概念,它自身的严谨性不够。
程序语言提供了形式化的语法和丰富的数据类型来定义程序逻辑,给出程序的统一性标准,有着共同的语言约定和对应规则,这都是自然语言很难达到的。
最后,要实现人与机器之间完全自然的语言交互和理解,这需要机器具备广泛而深入的知识水平和推理能力,而人工智能能否准确理解这些,需要标准来进行评估。目前的自然语言处理技术能否完全理解人类语言的深层次含义,实现人与机器完全自然的语言交互仍然需要商榷。
通过使用 Claude 打 leetcode 周赛,对于如何使用自然语言描述程序多了一点自己的认识。
自然语言可以表达所有的程序语言,具有更宽泛的表达能力。事实上,在学习和解释任何一门程序语言时,所依赖的都是自然语言。
程序语言本质上只是人与机器间的一种中间沟通工具,而其实这些年它的发展也在不断地从机器可解析的形式向更加贴近人类理解的自然语言靠拢,更偏人类正常沟通的方向靠近。
所以,程序语言并不比自然语言本身拥有更强的表达能力。相反,自然语言可以承载更丰富、更广泛的概念,实现更加抽象和深层次的思维传达。
程序语言之所以存在,其目的就在于让机器可以理解人类用自然语言表达的思想和逻辑。因此,程序语言并不是一个更优于自然语言的表现形式。
实践发现,在书写自然语言编程描述时,需要着重考虑到以下几个参考点:
-
语言表述:用尽可能精准自然的语言来进行沟通回复,避免重复性词语,尽可能不使用可能 / 或许这种不确定性的描述。
-
语义理解:过于复杂或者专业的表达会增加理解难度,需要补充更为清晰易懂的技术背景,会得到更好的输出。
-
交互模式:用更为直接明了的命令形式进行表达,虽然不及聊天形式自然,但更为清晰简明。
-
规范结构:需要在表达方式和交互规则上增加一定框架,对输入输出都会有更为直观的展示。
以上这些只是一些想法,自然语言编程背后涉及的知识和技术远不止此。
能超过 50% 的周赛参与者
用 AI 编写程序,为什么不选择热度最高的 ChatGPT,或其他生成代码专用 AI?就这个问题背后的原因,量子位询问了萧雅本人。
她表示,没有选择生成代码专用 AI 是因为想用最根本的模型进行解答,再考虑到所有输入是中文 + 代码,有 10 万 token 的 Claude 对中文的理解和处理优于 ChatGPT 等产品。
实际体验后她得出结论,通过与 AI 的交互来完成编程这种方法在某些步骤和环节比手写代码节省时间,尤其是改 bug 和学习新语言的时间。
“比如说本身对 c++ 非常熟悉,而可能这个代码需要 python 书写才能更匹配,哪怕对语言不是很了解,但是整体的思路和想法有很大共通的。”她补充解释道,“这个语言做的好的地方,相对的那个语言应该也会有对应的库,但是可以在不那么精通另一个语言的情况下依然很好的书写代码。”
虽然能加快变成速度,但新方法还是没有办法超过 90%-100% 的作答者,不过至少能超过 50% 的周赛参与者。
理由是这种自然语言编程的方法和近些年的编程语言发展模式很接近,让语言设计都更偏向于人类,而远离计算机硬件。
此外,这个方法和人的学习过程是一致的,人在学习编程语言的时候都是用自然语言进行解释的,这是最好的描述工具。
她举例说,团队合作书写代码的时候,所有代码的描述也是通过自然语言说清楚再进行思维碰撞,这种方法可以很大程度提高工作效率。
最终目标肯定是直接给出题目就可以让 AI 进行解答,现在是做不到这点的,这种方法只是 AI 书写代码的其中一步。