解題說明
Baseball Game
題目描述:你正在記錄一場棒球比賽的分數。給定一個字串陣列 operations,每個元素代表一個操作:整數表示新的分數,+ 表示前兩次分數之和,D 表示前一次分數的兩倍,C 表示取消前一次的分數。回傳所有記錄分數的總和。
解題思路:使用堆疊(stack)來模擬整個過程:
- 遇到整數:將其轉為數字並推入堆疊。
- 遇到
+:取堆疊頂端兩個元素相加,將結果推入堆疊(不移除原有元素)。 - 遇到
D:取堆疊頂端元素乘以 2,將結果推入堆疊。 - 遇到
C:彈出堆疊頂端元素(取消上一次記錄)。
最後將堆疊中所有元素相加即為答案。
C++ 解法
複雜度分析
時間複雜度:O(n) — 遍歷所有操作一次,每個操作都是 O(1)。
空間複雜度:O(n) — 堆疊在最壞情況下存放 n 個分數。
虛擬碼
1. Initialize empty stack 2. For each operation op: a. If op is "+": push stack[-1] + stack[-2] b. If op is "D": push 2 * stack[-1] c. If op is "C": pop stack d. Else: push integer(op) 3. Return sum of all elements in stack
其他解法
使用 std::stack:用標準的 std::stack 代替 vector,但需要在最後累加時逐個彈出。語義上更明確,但存取前兩個元素時不如 vector 方便(需要先 pop 再 push 回去)。
直接模擬不用堆疊:用陣列和索引手動管理,本質相同,只是用不同的資料結構。
延伸思考
- 如果新增一個操作符
M表示取所有當前記錄的平均值,該如何修改? - 如果
+操作改為前三次分數之和,需要做什麼邊界處理? - 能否用遞迴的方式解決此問題?有何優劣?