張曉雅 投稿自 凹非寺
量子位 | 公衆号 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 如果您有任何疑問或需要解釋的地方。我很樂意提供幫助。 代碼送出結果：
周賽題目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書寫代碼的其中一步。
— 完 —
量子位 QbitAI · 頭條号簽約
關注我們，第一時間獲知前沿科技動态