【Leetcode】【简单】【682棒球比赛】【JavaScript】
题目
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;
}
}
}
再之后可以找“+”的位置
如果“+”前面是“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;
}
}
}
最后可以将全部转化后的数组求和
依次调用处理“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);
};
解答二、数组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
发现这样写代码，精简多了，手动捂脸，
最新文章
- android 通讯录实现
- tesseract-ocr
- WinForm使用皮肤图文步骤
- Flash+XML前后按钮超酷焦点图,层叠翻转图形
- HDU 4005 The war Tarjan+dp
- iOS使用Core Graphics和UIBezierPath绘画
- 怎样在python中获取时间？
- [Java] Serializable(序列化)的理解
- SQL Server日期函数总结
- [UWP]实用的Shape指南
- 【wannacry病毒之暗网】-如何访问"暗网"（慎入）
- ubuntu实时显示网速cpu占用和内存占用率
- Ajax 的用法
- Flink入门使用
- Sql Server2014数据库清理日志
- 【测试工程师面试】在BOSS直聘上和面试官的一问一答
- python3使用selenium + Chrome基础操作代码
- PHP导出MySQL数据字典 Summer-Mysql-Dic
- 饮冰三年-人工智能-linux-06 系统启动流程及安全
- PHP 网页数据api采集