題目 682. 棒球比賽 你現在是棒球比賽記錄員。給定一個字元串列表，每個字元串可以是以下四種類型之一：1.整數（一輪的得分）：直接表示您在本輪中獲得的積分數。2. "+"（一輪的得分）：表示本輪獲得的得分是前兩輪有效 回合得分的總和。3. "D"（一輪的得分）：表示本輪獲得的得分是前一輪有效 回合 ...
題目
682. 棒球比賽
你現在是棒球比賽記錄員。
給定一個字元串列表，每個字元串可以是以下四種類型之一：
1.整數（一輪的得分）：直接表示您在本輪中獲得的積分數。
2."+"（一輪的得分）：表示本輪獲得的得分是前兩輪有效回合得分的總和。
3."D"（一輪的得分）：表示本輪獲得的得分是前一輪有效回合得分的兩倍。
4."C"（一個操作，這不是一個回合的分數）：表示您獲得的最後一個有效回合的分數是無效的，應該被移除。
每一輪的操作都是永久性的，可能會對前一輪和後一輪產生影響。
你需要返回你在所有回合中得分的總和。示例 1:
輸入: ["5","2","C","D","+"] 輸出: 30 解釋: 第1輪：你可以得到5分。總和是：5。 第2輪：你可以得到2分。總和是：7。 操作1：第2輪的數據無效。總和是：5。 第3輪：你可以得到10分（第2輪的數據已被刪除）。總數是：15。 第4輪：你可以得到5 + 10 = 15分。總數是：30。示例 2:
輸入: ["5","-2","4","C","D","9","+","+"] 輸出: 27 解釋: 第1輪：你可以得到5分。總和是：5。 第2輪：你可以得到-2分。總數是：3。 第3輪：你可以得到4分。總和是：7。 操作1：第3輪的數據無效。總數是：3。 第4輪：你可以得到-4分（第三輪的數據已被刪除）。總和是：-1。 第5輪：你可以得到9分。總數是：8。 第6輪：你可以得到-4 + 9 = 5分。總數是13。 第7輪：你可以得到9 + 5 = 14分。總數是27。註意：
輸入列表的大小將介於1和1000之間。
列表中的每個整數都將介於-30000和30000之間。
解答
題目數組中共出現4類元素：數字、“C”、“D”、“+”；
數字不用解釋了，就是具體分數，可以是任意數值，正負都可，
“C”是前一有效數據無效化，可以理解為將前一數據刪除，
“D”是前一有效數據的2倍，
“+”是前兩個有效數據的和。
解答一、indexOf找到操作符位置，然後對應操作
我首先想到的是：使用indexOf方法，找到對應“C”、“D”、“+”操作的位置，
然後進行相應操作：
首先肯定先判斷“C”，
這個“C”最早在考慮的時候想複雜了：如果“C”前面有“D”或者“+”怎麼辦？
其實無論“C”前面是什麼，都是無效的，
比如["1","2","3","+","C"]、["1","2","3","D","C"]，甚至是["1","2","3","C","C"]，都可以將“C”以及其前面的元素刪除掉
找到“C”的位置後，使用數組的splice方法，將其與前面一個元素一起刪除掉，
代碼片段如下：
let invalid=arr.indexOf("C");
if(invalid!==-1) {
arr.splice(invalid-1,2);
}else{
break;
}
然後找“D”或“+”的位置
我優先找了“D”，
因為“D”相對比較直接，只需判斷其前面一個數據是不是非數字，
如果“D”前面還是“D”，則傳入該元素前一索引位置，繼續調用該函數，
如果“D”前面是“+”，則傳入該元素前一索引位置，調用處理“+”對應的函數。
代碼片段如下：
function multFun(index){ while(index){ if(arr[index-1]==="+"){ addFun(index-1); }else if(arr[index-1]==="D"){ multFun(index-1); }else{ arr[index]=2*arr[index-1]; } break; } while(!index){ let mult=arr.indexOf("D"); if(mult!==-1) { if(arr[mult-1]==="+"){ addFun(mult-1); }else if(arr[mult-1]==="D"){ multFun(mult-1); }else{ arr[mult]=2*arr[mult-1]; } }else{ break; } } }View Code
再之後可以找“+”的位置
如果“+”前面是“D”，則傳入該元素前一索引位置，繼續調用該函數（這種情況不大可能出現，因為按現在的順序，在此之前“D”已經全部被轉化過了，不過萬一先找“+”，後找“D”，這段代碼就有用了），
如果“D”前面是“+”，則傳入該元素前一索引位置，調用“+”對應的函數繼續。
代碼片段如下：
function addFun(index) { while(index){ if(arr[index-1]==="+"){ addFun(index-1); }else if(arr[index-2]==="+"){ addFun(index-2); }else if(arr[index-1]==="D"){ multFun(arr[index-1]); }else if(arr[index-2]==="D"){ multFun(arr[index-2]); }else{ arr[index]=Number(arr[index-1])+Number(arr[index-2]); } break; } while(!index){ let add=arr.indexOf("+"); if(add!==-1) { if(arr[add-1]==="+"){ addFun(add-1); }else if(arr[add-2]==="+"){ addFun(add-2); }else if(arr[add-1]==="D"){ multFun(arr[add-1]); }else if(arr[add-2]==="D"){ multFun(arr[add-2]); }else{ arr[add]=Number(arr[add-1])+Number(arr[add-2]); } }else{ break; } } }View Code
最後可以將全部轉化後的數組求和
依次調用處理“C”的函數：invalidFun();
處理“D”的函數：multFun();
處理“+”的函數：addFun();
之後求和：reduce();
此處碰到了坑：之前在addFun()的時候也遇到過，
數組元素相加時，若存在字元串："1"+2,1+"2",''1"+"2",結果都是"12",而不是想要得到的3；
所以在“加”運算的時候，都先Number()強制轉換一下，即可得到正常結果。
代碼片段如下：
let arr=ops; invalidFun(); multFun(); addFun(); return arr.reduce(function (prev, cur) { return Number(prev) + Number(cur); },0);
完整代碼如下：（leetcode提交通過，執行用時：92ms）
var calPoints = function(ops) { function invalidFun() { while(1){ let invalid=arr.indexOf("C"); if(invalid!==-1) { arr.splice(invalid-1,2); }else{ break; } } } function multFun(index){ while(index){ if(arr[index-1]==="+"){ addFun(index-1); }else if(arr[index-1]==="D"){ multFun(index-1); }else{ arr[index]=2*arr[index-1]; } break; } while(!index){ let mult=arr.indexOf("D"); if(mult!==-1) { if(arr[mult-1]==="+"){ addFun(mult-1); }else if(arr[mult-1]==="D"){ multFun(mult-1); }else{ arr[mult]=2*arr[mult-1]; } }else{ break; } } } function addFun(index) { while(index){ if(arr[index-1]==="+"){ addFun(index-1); }else if(arr[index-2]==="+"){ addFun(index-2); }else if(arr[index-1]==="D"){ multFun(arr[index-1]); }else if(arr[index-2]==="D"){ multFun(arr[index-2]); }else{ arr[index]=Number(arr[index-1])+Number(arr[index-2]); } break; } while(!index){ let add=arr.indexOf("+"); if(add!==-1) { if(arr[add-1]==="+"){ addFun(add-1); }else if(arr[add-2]==="+"){ addFun(add-2); }else if(arr[add-1]==="D"){ multFun(arr[add-1]); }else if(arr[add-2]==="D"){ multFun(arr[add-2]); }else{ arr[add]=Number(arr[add-1])+Number(arr[add-2]); } }else{ break; } } } let arr=ops; invalidFun(); multFun(); addFun(); return arr.reduce(function (prev, cur) { return Number(prev) + Number(cur); },0); };View Code
解答二、數組push()、pop()方法
之後又參考官方題解：
方法：棧
思路與演算法
讓我們在處理數據時保持棧上每個有效回合的值。棧是理想的，因為我們只處理涉及最後或倒數第二輪的操作。
複雜度分析
複雜度分析：O(N)O(N)，其中 NN 是
ops的長度。我們解析給定數組中的每個元素，然後每個元素執行 O(1)O(1) 的工作。空間複雜度：O(N)O(N)，用於存儲
stack的空間。
class Solution { public int calPoints(String[] ops) { Stack<Integer> stack = new Stack(); for(String op : ops) { if (op.equals("+")) { int top = stack.pop(); int newtop = top + stack.peek(); stack.push(top); stack.push(newtop); } else if (op.equals("C")) { stack.pop(); } else if (op.equals("D")) { stack.push(2 * stack.peek()); } else { stack.push(Integer.valueOf(op)); } } int ans = 0; for(int score : stack) ans += score; return ans; } }Java
class Solution(object): def calPoints(self, ops): stack = [] for op in ops: if op == '+': stack.append(stack[-1] + stack[-2]) elif op == 'C': stack.pop() elif op == 'D': stack.append(2 * stack[-1]) else: stack.append(int(op)) return sum(stack)Python
發現這樣寫代碼，精簡多了，手動捂臉，
