张晓雅 投稿自 凹非寺
量子位 | 公众号 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, 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 如果您有任何疑问或需要解释的地方。我很乐意提供帮助。
代码提交结果：
