【Leetcode】【简单】【682棒球比赛】【JavaScri…

2019-03-10 11:51:20来源：博客园阅读 ()

题目

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()方法

之后又参考官方题解：

方法：栈

思路与算法

让我们在处理数据时保持栈上每个有效回合的值。栈是理想的，因为我们只处理涉及最后或倒数第二轮的操作。

复杂度分析

复杂度分析：

空间复杂度：

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

发现这样写代码，精简多了，手动捂脸，??‍♂?。

于是手动搞了另外一个版本，栈。

将数组遍历后，配合switch，和pop、push，即可完成：

首先遍历，数组的每一个元素，使用switch判断：

如果元素是“数字”，将该元素push进栈，

如果元素是“C”，则将栈顶的元素pop出来，

如果元素是“D”，则将栈顶元素乘2后，push进栈，

如果元素是“+”，则将栈顶两个元素相加后，push进栈。

代码如下：（leetcode提交通过，执行用时：100ms）

var calPoints = function(ops) {
    let arr=[];
    for(let op of ops){
        switch(op){
            case "C":arr.pop();break;
            case "D":{
                let last=arr[arr.length-1];
                arr.push(last*2);
                break;
            }
            case "+":{
                let last=arr[arr.length-1],
                    preLast=arr[arr.length-2];
                arr.push(Number(last) + Number(preLast));
                break;
            }
            default:arr.push(op);break;
        }
    }
    return arr.reduce(function (prev, cur) {
        return Number(prev) + Number(cur);
    },0);
}