還在自己吭哧吭哧打算法平臺(tái) Leetcode 的周賽？為什么不試試神奇的 ChatGPT 類 AI 呢！
用 AI 助手 Claude 參加第 103 場(chǎng)周賽，共四道題，均完成了 AC，能達(dá)到參與者前 10% 的成績(jī)。
事情的起因是知乎上一位叫蕭雅的用戶嘗試使用 AI 進(jìn)行編程，但在測(cè)試過程中，她發(fā)現(xiàn)直接給出題目讓 AI 進(jìn)行編程并輸出結(jié)果的方法，效果并不理想。
于是一種大膽的想法誕生了：使用自然語(yǔ)言配合逐步的思路描述，通過與 AI 的交互來完成編程。
具體操作中，她選擇了 Anthropic 公司出品的 ChatGPT 最強(qiáng)競(jìng)品 ——Claude 這個(gè) AI 助手，并選取了 Leetcode 第 103 場(chǎng)雙周賽來完成實(shí)驗(yàn)。
整體的解答過程遵循以下幾點(diǎn)要求：
全程使用自然語(yǔ)言進(jìn)行描述，通過一次溝通完成輸出，因此下文所有發(fā)給 Claude 的指令均可以復(fù)現(xiàn)。
采用問題描述、解答思路、以及開頭書寫要求作為提問固定格式。
編程采用 python 代碼輸出。
最終測(cè)試結(jié)果是，可以認(rèn)為通過自然語(yǔ)言 + 解答思路發(fā)送給 AI 進(jìn)行編程是可行的。
以下是測(cè)試全過程：
用自然語(yǔ)言讓 AI 打 leetcode 周賽
Leetcode 第 103 場(chǎng)周賽題目 1 如下，k 個(gè)元素的最大和：
發(fā)給 Claude 指令如下：
問題描述如下： ''' 給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 。你需要執(zhí)行以下操作 恰好 k 次，最大化你的得分： 1.從 nums 中選擇一個(gè)元素 m 。 2.將選中的元素 m 從數(shù)組中刪除。 3.將新元素 m + 1 添加到數(shù)組中。 4.你的得分增加 m 。 請(qǐng)你返回執(zhí)行以上操作恰好 k 的最大得分。 ''' 解答思路如下： ''' 由于最大值加一后還是最大值，那么反復(fù)利用最大值即可。 設(shè)數(shù)組的最大值為m，答案就是m+(m+1)+(m+2)+?+(m+k?1)= [(2m+k?1)?k]/2 ''' 請(qǐng)用python3書寫，并以下面這行作為開頭。 class Solution: def maximizeSum(self, nums: List[int], k: int) - int:
Claude 回復(fù)內(nèi)容如下：
這里是python代碼實(shí)現(xiàn) python class Solution: def maximizeSum(self, nums: List[int], k: int) - int: m = max(nums) return (2*m + k - 1) * k // 2 解答思路 1. 首先找到數(shù)組中的最大值m。 2. 然后最大的得分公式為m + (m+1) + (m+2) + + (m+k-1) = (m + (m+k-1)) * k / 2 = (2*m + k - 1) * k / 2 3. 直接返回計(jì)算結(jié)果。 時(shí)間復(fù)雜度O(n)。需要遍歷數(shù)組一次得到最大值。 空間復(fù)雜度O(1)。 這個(gè)解法直接利用了最大值與k的關(guān)系來得到最終結(jié)果沒有實(shí)際操作數(shù)組。所以時(shí)間和空間復(fù)雜度都比較低。 請(qǐng) let me know 如果您有任何疑問或需要解釋的地方。我很樂意提供幫助。
代碼提交結(jié)果：
周賽題目 2 如下，找到兩個(gè)數(shù)組的前綴公共數(shù)組：
發(fā)給 Claude 指令如下：
問題描述如下： ''' 給你兩個(gè)下標(biāo)從 0 開始長(zhǎng)度為 n 的整數(shù)排列 A 和 B 。 A 和 B 的 前綴公共數(shù)組 定義為數(shù)組 C ，其中 C[i] 是數(shù)組 A 和 B 到下標(biāo)為 i 之前公共元素的數(shù)目。 請(qǐng)你返回 A 和 B 的 前綴公共數(shù)組 。 如果一個(gè)長(zhǎng)度為 n 的數(shù)組包含 1 到 n 的元素恰好一次，我們稱這個(gè)數(shù)組是一個(gè)長(zhǎng)度為 n 的 排列 。 ''' 解答思路如下： ''' 1.存儲(chǔ)公共前綴的大小 2.存儲(chǔ) a 和 b 中已經(jīng)匹配過的元素 3.同時(shí)遍歷 a 和 b 中的元素 4.將 a 中的當(dāng)前元素 x 對(duì)應(yīng)的二進(jìn)制位置為 1，標(biāo)記為已匹配 5.將 b 中的當(dāng)前元素 y 對(duì)應(yīng)的二進(jìn)制位置為 1，標(biāo)記為已匹配 6.計(jì)算當(dāng)前公共前綴的大小，即 p 和 q 的二進(jìn)制數(shù)中 1 的個(gè)數(shù) 7.返回公共前綴大小的列表 ''' 請(qǐng)用python3書寫，并以下面這行作為開頭。 class Solution: def findThePrefixCommonArray(self, A: List[int], B: List[int]) - List[int]:
Claude 回復(fù)內(nèi)容如下：
這里是優(yōu)化后的python代碼實(shí)現(xiàn)
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.end(bin(p&q).count('1')
return res
解答思路
1. p和q初始化為0用來記錄A和B數(shù)組中出現(xiàn)過的數(shù)字。
2. 同時(shí)遍歷A和B數(shù)組的元素。
3. 通過p |= 1 < A[i]將A[i]位置1。
4. 通過q |= 1 B[i]將B[i]位置1。
5. p & q得到兩個(gè)數(shù)組公共元素然后bin(p & q).count('1'計(jì)算1的個(gè)數(shù)得到公共元素個(gè)數(shù)c。
6. 添加c到res。
7. 重復(fù)3-6直到A或B數(shù)組遍歷結(jié)束。
8. 返回res。
時(shí)間復(fù)雜度O(m + n)。需要遍歷兩個(gè)數(shù)組。
空間復(fù)雜度O(m + n)。需要使用res存儲(chǔ)結(jié)果。
這種方法無需提前記錄每個(gè)數(shù)字在A和B數(shù)組中出現(xiàn)的次數(shù)而是在遍歷的同時(shí)更新p和q簡(jiǎn)潔高效。
請(qǐng) let me know 如果您有任何疑問或需要解釋的地方。我很樂意提供幫助。代碼提交結(jié)果：
周賽題目 3 如下，網(wǎng)格中魚的最大數(shù)目：
發(fā)給 Claude 指令如下：
問題描述如下： ''' 給你一個(gè)下標(biāo)從 0 開始大小為 m x n 的二維整數(shù)組 grid ，其中下標(biāo)在 (r, c) 處的整數(shù)表示： 如果 grid[r][c] = 0 ，那么它是一塊 陸地 。 如果 grid[r][c] 0 ，那么它是一塊 水域 ，且包含 grid[r][c] 條魚。 一位漁夫可以從任意 水域 格子 (r, c) 出發(fā)，然后執(zhí)行以下操作任意次： 捕撈格子 (r, c) 處所有的魚，或者 移動(dòng)到相鄰的 水域 格子。 請(qǐng)你返回漁夫最優(yōu)策略下， 最多 可以捕撈多少條魚。如果沒有水域格子，請(qǐng)你返回 0 。 格子 (r, c) 相鄰 的格子為 (r, c + 1) ，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，前提是相鄰格子在網(wǎng)格圖內(nèi)。 ''' 解答思路如下： ''' 1.獲取網(wǎng)格的行數(shù)和列數(shù) 2.定義深度優(yōu)先搜索函數(shù) 3. 如果下標(biāo)越界或網(wǎng)格中沒有魚，則返回 0 4.統(tǒng)計(jì)當(dāng)前點(diǎn)的價(jià)值為s 5.將當(dāng)前點(diǎn)標(biāo)記成訪問過，不需要重置其值 6. 四個(gè)方向進(jìn)行深度優(yōu)先搜索 7.將搜索到的魚的價(jià)值累加到 s 中 8.返回能夠獲得的最大價(jià)值s 9.遍歷所有的格子，計(jì)算其能夠獲得的最大價(jià)值并返回 ''' 請(qǐng)用python3書寫，并以下面這行作為開頭，按照思路不要添加任何額外細(xì)節(jié)。 class Solution: def findMaxFish(self, grid: List[List[int]]) - int:
Claude 回復(fù)內(nèi)容如下：
這里是精簡(jiǎn)的python代碼實(shí)現(xiàn): 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. 獲取網(wǎng)格的行數(shù)m和列數(shù)n。 2. 定義dfs函數(shù)進(jìn)行深度優(yōu)先搜索。 3. 如果下標(biāo)越界或網(wǎng)格中沒有魚則返回 0。 4. 統(tǒng)計(jì)當(dāng)前點(diǎn)grid[i][j]的魚的數(shù)量s。 5. 將grid[i][j]標(biāo)記為已訪問不需要重置其值 。 6. dfs搜索四個(gè)方向并將搜索到的魚的數(shù)量累加到s。 7. 返回s。 8. 遍歷所有的格子通過dfs計(jì)算其能夠獲得的最大價(jià)值并更新res。 9. 返回res。 時(shí)間復(fù)雜度O(m*n)。需要遍歷整個(gè)網(wǎng)格。 空間復(fù)雜度O(m*n)。遞歸深度可能達(dá)到m*n。 這是一道典型的深度優(yōu)先搜索問題需要注意狀態(tài)重置。 通過不重置grid[i][j]的值避免了狀態(tài)重置簡(jiǎn)化了代碼邏輯。 請(qǐng) let me know 如果您有任何疑問或需要解釋的地方。我很樂意提供幫助。
代碼提交結(jié)果：
周賽題目 4 如下，將數(shù)組清空：
發(fā)給 Claude 指令如下：
問題描述如下： ''' 給你一個(gè)包含若干 互不相同 整數(shù)的數(shù)組 nums ，你需要執(zhí)行以下操作 直到數(shù)組為空 ： 如果數(shù)組中第一個(gè)元素是當(dāng)前數(shù)組中的 最小值 ，則刪除它。 否則，將第一個(gè)元素移動(dòng)到數(shù)組的 末尾 。 請(qǐng)你返回需要多少個(gè)操作使 nums 為空。 ''' 解答思路如下： ''' 數(shù)組 nums 的長(zhǎng)度為n 創(chuàng)建一個(gè)空的堆列表heap 對(duì)nums進(jìn)行i,nums這個(gè)格式的遍歷，再將當(dāng)前元素值和對(duì)應(yīng)索引組成后面格式的元組 (num, i) 加入到堆列表 heap 中，不要對(duì)這兩個(gè)格式順序做修改。 將 nums 中的所有元素及其下標(biāo)加入最小堆 heap 中 用sortedcontainers里面的SortedList創(chuàng)建空的有序集合pos，用于存儲(chǔ)已經(jīng)刪除的元素的下標(biāo) res用于存儲(chǔ)清空數(shù)組所需的最少操作數(shù)，初始化為 0 哨兵li，上一個(gè)彈出的數(shù)的位置，初始化為-1 獲取堆中的最小值，并計(jì)算清除該元素所需的步數(shù)，重復(fù)直到堆為空 如果 i 在上一個(gè)彈出元素li的后面，對(duì)于每個(gè)被彈出的元素，計(jì)算從i到li在pos中的有效元素?cái)?shù)量d，即計(jì)算值在 li的右邊且值小于 i 的元素?cái)?shù)量。再將從當(dāng)前位置到i之間的長(zhǎng)度減去d，加入總步數(shù) res 中 如果當(dāng)前元素的位置在上一個(gè)被彈出元素 li 的前面，則計(jì)算從 li 到數(shù)組結(jié)尾的有效元素?cái)?shù)量d，即集合中小于等于i的元素?cái)?shù)量與集合中小于n的元素?cái)?shù)量相加，再減去集合中小于li的元素?cái)?shù)量為有效元素?cái)?shù)量d。再將從當(dāng)前位置 li 到數(shù)組末尾的元素?cái)?shù)量加上i，再減去d，加入總步數(shù)res中 將元素 i 的下標(biāo)加入已刪除元素的有序集合pos中 更新上一個(gè)彈出的置 返回清空數(shù)組所需的最少操作數(shù)res ''' 請(qǐng)用python3書寫，并以下面這行作為開頭。 class Solution: def countOperationsToEmptyArray(self, nums: List[int]) - int:
Claude 回復(fù)內(nèi)容如下：
這里是python代碼實(shí)現(xiàn): python from sortedcontainers import SortedList class Solution: def countOperationsToEmptyArray(self, nums: List[int]) -> int: n = len(nums) heap = [] for i, num in enumerate(nums): heush(heap, (num, i)) pos = SortedList() res = 0 li = -1 while heap: num, i = heop(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. 數(shù)組 nums 的長(zhǎng)度為n。 2. 創(chuàng)建一個(gè)空的堆列表heap。 3. 對(duì)nums進(jìn)行i,nums這個(gè)格式的遍歷,再將當(dāng)前元素值和對(duì)應(yīng)索引組成后面格式的元組 (num, i) 加入到堆列表 heap 中,不要對(duì)這兩個(gè)格式順序做修改。 4. 用sortedcontainers里面的SortedList創(chuàng)建空的有序集合pos,用于存儲(chǔ)已經(jīng)刪除的元素的下標(biāo)。 5. res用于存儲(chǔ)清空數(shù)組所需的最少操作數(shù),初始化為0。 6. 哨兵li,上一個(gè)彈出的數(shù)的位置,初始化為-1。 7. 獲取堆中的最小值,并計(jì)算清除該元素所需的步數(shù),重復(fù)直到堆為空。 8. 如果i在上一個(gè)彈出元素li的后面,對(duì)于每個(gè)被彈出的元素,計(jì)算從i到li在pos中的有效元素?cái)?shù)量d,即計(jì)算值在 li的右邊且值小于 i 的元素?cái)?shù)量。再將從當(dāng)前位置到i之間的長(zhǎng)度減去d,加入總步數(shù)res中。 9. 如果當(dāng)前元素的位置在上一個(gè)被彈出元素li的前面,則計(jì)算從li到數(shù)組結(jié)尾的有效元素?cái)?shù)量d,即集合中小于等于i的元素?cái)?shù)量與集合中小于n的元素?cái)?shù)量相加,再減去集合中小于li的元素?cái)?shù)量為有效元素?cái)?shù)量d。再將從當(dāng)前位置li到數(shù)組末尾的元素?cái)?shù)量加上i,再減去d,加入總步數(shù)res中。 10. 將元素i的下標(biāo)加入已刪除元素的有序集合pos中。 11. 更新上一個(gè)彈出的置li = i。 12. 返回清空數(shù)組所需的最少操作數(shù)res。 時(shí)間復(fù)雜度:O(nlogn)。需要排序。 空間復(fù)雜度:O(n)。需要堆和集合。 這是一道運(yùn)用堆與有序集合的題目。通過維護(hù)哨兵位置和已刪除元素,得到最優(yōu)解。 請(qǐng) let me know 如果您有任何疑問或需要解釋的地方。我很樂意提供幫助。
代碼提交結(jié)果：
實(shí)踐后的思考
對(duì)于這個(gè)問題最初的想法就來自于在 AI 助手有了突破之后，嘗試能否通過自然語(yǔ)言編程來代替程序語(yǔ)言編程。
自然語(yǔ)言編程指的是使用我們?nèi)粘ＵZ(yǔ)言來表達(dá)計(jì)算機(jī)程序的概念和算法，而非傳統(tǒng)的程序語(yǔ)言如 C++ 和 Python 等。
自然語(yǔ)言具有良好的表達(dá)形式，更易于理解和表述，更加親和易懂，人們可以用最自然的語(yǔ)言來表達(dá)自己的思想和創(chuàng)意，而無需陷入復(fù)雜的程序語(yǔ)言語(yǔ)法。
自然語(yǔ)言編程可以讓人們更為容易得表達(dá)自己的需求，并快速實(shí)現(xiàn)理想中的功能。
然而，自然語(yǔ)言編程也存在明顯劣勢(shì)。
首先，自然語(yǔ)言表達(dá)是模糊的和不精確的。我們所講的語(yǔ)言中，存在很多概念和意思是相對(duì)的和依賴語(yǔ)境的，這些難以在計(jì)算機(jī)程序中得到明確和一致的表達(dá)，這都給程序的理解使用和調(diào)試帶來了很大困難。
其次，自然語(yǔ)言難以表達(dá)計(jì)算機(jī)程序需要的精確和嚴(yán)謹(jǐn)?shù)母拍?，它自身的?yán)謹(jǐn)性不夠。
程序語(yǔ)言提供了形式化的語(yǔ)法和豐富的數(shù)據(jù)類型來定義程序邏輯，給出程序的統(tǒng)一性標(biāo)準(zhǔn)，有著共同的語(yǔ)言約定和對(duì)應(yīng)規(guī)則，這都是自然語(yǔ)言很難達(dá)到的。
最后，要實(shí)現(xiàn)人與機(jī)器之間完全自然的語(yǔ)言交互和理解，這需要機(jī)器具備廣泛而深入的知識(shí)水平和推理能力，而人工智能能否準(zhǔn)確理解這些，需要標(biāo)準(zhǔn)來進(jìn)行評(píng)估。目前的自然語(yǔ)言處理技術(shù)能否完全理解人類語(yǔ)言的深層次含義，實(shí)現(xiàn)人與機(jī)器完全自然的語(yǔ)言交互仍然需要商榷。
通過使用 Claude 打 leetcode 周賽，對(duì)于如何使用自然語(yǔ)言描述程序多了一點(diǎn)自己的認(rèn)識(shí)。
自然語(yǔ)言可以表達(dá)所有的程序語(yǔ)言，具有更寬泛的表達(dá)能力。事實(shí)上，在學(xué)習(xí)和解釋任何一門程序語(yǔ)言時(shí)，所依賴的都是自然語(yǔ)言。
程序語(yǔ)言本質(zhì)上只是人與機(jī)器間的一種中間溝通工具，而其實(shí)這些年它的發(fā)展也在不斷地從機(jī)器可解析的形式向更加貼近人類理解的自然語(yǔ)言靠攏，更偏人類正常溝通的方向靠近。
所以，程序語(yǔ)言并不比自然語(yǔ)言本身?yè)碛懈鼜?qiáng)的表達(dá)能力。相反，自然語(yǔ)言可以承載更豐富、更廣泛的概念，實(shí)現(xiàn)更加抽象和深層次的思維傳達(dá)。
程序語(yǔ)言之所以存在，其目的就在于讓機(jī)器可以理解人類用自然語(yǔ)言表達(dá)的思想和邏輯。因此，程序語(yǔ)言并不是一個(gè)更優(yōu)于自然語(yǔ)言的表現(xiàn)形式。
實(shí)踐發(fā)現(xiàn)，在書寫自然語(yǔ)言編程描述時(shí)，需要著重考慮到以下幾個(gè)參考點(diǎn)：
語(yǔ)言表述：用盡可能精準(zhǔn)自然的語(yǔ)言來進(jìn)行溝通回復(fù)，避免重復(fù)性詞語(yǔ)，盡可能不使用可能 / 或許這種不確定性的描述。
語(yǔ)義理解：過于復(fù)雜或者專業(yè)的表達(dá)會(huì)增加理解難度，需要補(bǔ)充更為清晰易懂的技術(shù)背景，會(huì)得到更好的輸出。
交互模式：用更為直接明了的命令形式進(jìn)行表達(dá)，雖然不及聊天形式自然，但更為清晰簡(jiǎn)明。
規(guī)范結(jié)構(gòu)：需要在表達(dá)方式和交互規(guī)則上增加一定框架，對(duì)輸入輸出都會(huì)有更為直觀的展示。
以上這些只是一些想法，自然語(yǔ)言編程背后涉及的知識(shí)和技術(shù)遠(yuǎn)不止此。
能超過 50% 的周賽參與者
用 AI 編寫程序，為什么不選擇熱度最高的 ChatGPT，或其他生成代碼專用 AI？就這個(gè)問題背后的原因，量子位詢問了蕭雅本人。
她表示，沒有選擇生成代碼專用 AI 是因?yàn)橄胗米罡镜哪Ｐ瓦M(jìn)行解答，再考慮到所有輸入是中文 + 代碼，有 10 萬(wàn) token 的 Claude 對(duì)中文的理解和處理優(yōu)于 ChatGPT 等產(chǎn)品。
實(shí)際體驗(yàn)后她得出結(jié)論，通過與 AI 的交互來完成編程這種方法在某些步驟和環(huán)節(jié)比手寫代碼節(jié)省時(shí)間，尤其是改 bug 和學(xué)習(xí)新語(yǔ)言的時(shí)間。
“比如說本身對(duì) c++ 非常熟悉，而可能這個(gè)代碼需要 python 書寫才能更匹配，哪怕對(duì)語(yǔ)言不是很了解，但是整體的思路和想法有很大共通的?！彼a(bǔ)充解釋道，“這個(gè)語(yǔ)言做的好的地方，相對(duì)的那個(gè)語(yǔ)言應(yīng)該也會(huì)有對(duì)應(yīng)的庫(kù)，但是可以在不那么精通另一個(gè)語(yǔ)言的情況下依然很好的書寫代碼?！?/p>
雖然能加快變成速度，但新方法還是沒有辦法超過 90%-100% 的作答者，不過至少能超過 50% 的周賽參與者。
理由是這種自然語(yǔ)言編程的方法和近些年的編程語(yǔ)言發(fā)展模式很接近，讓語(yǔ)言設(shè)計(jì)都更偏向于人類，而遠(yuǎn)離計(jì)算機(jī)硬件。
此外，這個(gè)方法和人的學(xué)習(xí)過程是一致的，人在學(xué)習(xí)編程語(yǔ)言的時(shí)候都是用自然語(yǔ)言進(jìn)行解釋的，這是最好的描述工具。
她舉例說，團(tuán)隊(duì)合作書寫代碼的時(shí)候，所有代碼的描述也是通過自然語(yǔ)言說清楚再進(jìn)行思維碰撞，這種方法可以很大程度提高工作效率。
最終目標(biāo)肯定是直接給出題目就可以讓 AI 進(jìn)行解答，現(xiàn)在是做不到這點(diǎn)的，這種方法只是 AI 書寫代碼的其中一步。
本文來自微信公眾號(hào)：量子位 （ID：QbitAI），作者：關(guān)注前沿科技
廣告聲明：文內(nèi)含有的對(duì)外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。