最後一塊石頭的重量
「最後一塊石頭重量」問題的詳細指南和 Python 實現。
1. 學習
「最後一塊石頭的重量」問題是堆/優先隊列部分的關鍵挑戰。
此實作著重於 Python 中的簡單層級邏輯。
在我們提供的解決方案中，我們優先考慮技術準確性和程式碼可讀性。
2. Real-World Applications
3. Visual Intuition
可視化「最後一塊石頭重量」的邏輯流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔細閱讀最後一塊石頭重量的問題陳述。
2. Formulate brute force
起草一個簡單的迭代解決方案。
3. Identify inefficiency
尋找冗餘計算。
4. Optimize search path
使用散列或排序來加速該過程。
5. Final Implementation
清理生產標準代碼。
問題陳述
給定一個整數石頭數組，其中stones[i] 是第 i 個石頭的重量。
我們正在玩石頭遊戲。在每一輪中，我們選擇最重的兩塊石頭並將它們粉碎在一起。假設最重的兩塊石頭的重量為 x 和 y，且 x <= y。這次粉碎的結果是：
- 如果 x == y，兩塊石頭都會被摧毀，
- 如果 x != y，則重量 x 的石頭被破壞，重量 y 的石頭具有新的重量 y - x。
遊戲結束時，最多剩下一顆棋子。
返回最後剩下的石頭的重量。如果沒有剩下石子，則傳回 0。
寫一個函數 lastStoneWeight(stones: List[int]) -> int。
- •1 <= len(stones) <= 30
- •1 <= stones[i] <= 1000
範例
stones = [2,7,4,1,8,1]
1
Smash 7 and 8 to get 1, array becomes [2,4,1,1,1]. Smash 2 and 4 to get 2, array becomes [2,1,1,1]. Smash 2 and 1 to get 1, array becomes [1,1,1]. Smash 1 and 1 to get 0, array becomes [1]. The last remaining stone is 1.
stones = [1]
1
Only one stone, so weight is 1.
Need a Hint?
Edge Cases to Watch
- 空輸入結構
- 單元素輸入
- 大數值範圍
準備好解決了嗎？
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
面試見解和變化
複雜度分析分解
為什麼時間: Directly evaluates all possibilities.
為什麼選擇太空: Uses standard local memory.
為什麼時間: Optimized paths reduce total operations.
為什麼選擇太空: May trade memory for speed.
最佳化解決方案Python程式碼
最佳化解決方案Python程式碼
import heapq
def last_stone_weight_opt(stones):
stones = [-s for s in stones]
heapq.heapify(stones)
while len(stones) > 1:
first = heapq.heappop(stones)
second = heapq.heappop(stones)
if second > first: heapq.heappush(stones, first - second)
stones.append(0)
return abs(stones[0])暴力破解代碼（劇透保護）
暴力破解代碼（劇透保護）
def last_stone_weight_brute(stones):
while len(stones) > 1:
stones.sort()
s1, s2 = stones.pop(), stones.pop()
if s1 != s2: stones.append(s1 - s2)
return stones[0] if stones else 0Algorithm Pattern Checklist
When dealing with Heap / Priority Queue data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推薦的 Python 資源
透過相關的互動式教學、備忘單和程式碼比較來擴展您的知識。
Python 迴圈：For 與 While 迴圈解釋
了解如何使用 Python 循環來迭代資料。透過互動式範例掌握 for 迴圈、while 迴圈、break、continue 和迴圈最佳實務。
如何在 Python 中對列表進行排序（升序和降序）
了解如何在 Python 中使用 sort() 方法和sorted() 函數對清單進行排序。發現自訂鍵排序和逆序範例。
Python 字串方法備忘單
Python 字串操作的完整參考指南。掌握格式化、搜尋、拆分、取代和檢查字串屬性。
Python 與 JavaScript：哪種程式語言最好？
Python 和 JavaScript 的全面比較。探索語法差異、效能、用例（後端與前端）和編碼範例。