LeetCode算法题-Baseball Game（Java实现）

这是悦乐书的第288次更新，第305篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第156题（顺位题号是682）。你现在是棒球比赛点记录器。给定一个字符串列表，每个字符串可以是以下4种类型之一：

整数（一轮的得分）：直接表示你在这轮中获得的积分数。
“+”（一轮的得分）：表示你在这一轮得到的分数是最后两个有效回合分数的总和。
“D”（一轮得分）：表示你在这一轮得到的分数是最后一轮有效回合分数的加倍数据。
“C”（一项操作，不是一轮的得分）：代表你得到的最后一个有效回合点是无效的，应该删除。

每一轮的操作都是永久性的，可能会影响之前和之后的一轮。返回所有轮次中可获得的积分总和。例如：

输入：[“5”，“2”，“C”，“D”，“+”]

输出：30

说明：

第1轮：你可以获得5分。总和是：5。

第2轮：你可以获得2分。总和是：7。

操作1：第2轮的数据无效。总和是：5。

第3轮：你可以获得10分（第2轮的数据已被删除）。总和是：15。

第4轮：你可以获得5 + 10 = 15分。总和是：30。

输入：[“5”，“ - 2”，“4”，“C”，“D”，“9”，“+”，“+”]

输出：27

说明：

第1轮：你可以获得5分。总和是：5。

第2轮：你可以获得-2分。总和是：3。

第3轮：你可以获得4分。总和是：7。

操作1：第3轮的数据无效。总和是：3。

第4轮：你可以得到-4分（第3轮的数据已被删除）。总和是：-1。

第5轮：你可以获得9分。总和是：8。

第6轮：你可以获得-4 + 9 = 5分。总和是13。

第7轮：你可以获得9 + 5 = 14分。总和是27。

注意：

输入列表的大小将介于1和1000之间。
列表中表示的每个整数都介于-30000和30000之间。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

在遇到C的时候，我们将数组中的部分元素进行替换，将当前元素替换为null，并且将其前一个有效元素也替换为null，对其前一个有效元素进行替换时，sum要先减去该值。在遇到D的时候，找到当前元素前一个有效元素（不等于null），计算其元素值的2倍，累加到sum上去，然后对当前元素重新赋值。在遇到加号的时候，找到当前元素的前两个有效元素，算出和，累加到sum上去，并且对当前元素重新赋值。

public int calPoints(String[] ops) {
    int sum = 0;
    for (int i=0; i<ops.length; i++) {
        if ("C".equals(ops[i])) {
            ops[i] = "null";
            int h = i-1;
            while (h>0 && ops[h] == "null") {
                h--;
            }
            sum -= Integer.parseInt(ops[h]);
            ops[h] = "null";
        } else if("D".equals(ops[i])){
            int index = i-1;
            while (index>0 && ops[index] == "null") {
                index--;
            }
            int temp = Integer.parseInt(ops[index])*2;
            sum += temp;
            ops[i] = temp+"";
        } else if("+".equals(ops[i])){
            int j = i-1;
            while (j>0 && ops[j] == "null") {
                j--;
            }
            int last = Integer.parseInt(ops[j]);
            int k = j-1;
            while (k>0 && ops[k] == "null") {
                k--;
            }
            int second = Integer.parseInt(ops[k]);
            sum += last+second;
            ops[i] = (last+second)+"";
        } else {
            sum += Integer.parseInt(ops[i]);
        }
    }
    return sum;
}

03 第二种解法

使用一个新的数组，长度与ops的长度一致，存放新的元素值。在外部定义一个变量i，作为新数组的递增索引，如果遇到了C，就将索引回退一位；如果遇到D，就获取新数组前一位元素再乘以2，作为当前索引所在位置的新元素值；如果遇到加号，就取新数组当前索引所在位置的前两位元素，计算和，再将和赋值给当前索引所在位置的元素，取前两位元素时，需要判断下标是否大于0。最后计算新数组中0到i位的元素之和。

public int calPoints(String[] ops) {
    int sum = 0;
    int[] res = new int[ops.length];
    int i=0;
    for (String str : ops) {
        if ("C".equals(str)) {
            i--;
        } else if ("D".equals(str)) {
            res[i] = res[i-1>0 ? i-1 : 0]*2;
            i++;
        } else if ("+".equals(str)) {
            res[i] = res[i-1>0 ? i-1 : 0]+res[i-2>0 ? i-2 : 0];
            i++;
        } else {
            res[i] = Integer.parseInt(str);
            i++;
        }
    }
    for (int j=0; j<i; j++) {
        sum += res[j];
    }
    return sum;
}

04 第三种解法

使用栈，借助其先进后出的特性，栈顶元素始终是最后一个元素。对数组的元素进行遍历，如果遇到C了，就将栈顶的元素的出栈；如果遇到D了，就获取栈顶的值（不出栈）乘以2，作为新的栈顶入栈；如果遇到加号，就先将当前的栈顶出栈，然后再获取新的栈顶（不出栈），计算两者的和，然后将原栈顶再入栈，再将和作为新栈顶入栈。最后，遍历栈内所有的元素，计算和。

public int calPoints(String[] ops) {
    Stack<Integer> stack = new Stack<Integer>();
    for (String str : ops) {
        if ("C".equals(str)) {
            stack.pop();
        } else if ("D".equals(str)) {
            stack.push(stack.peek()*2);
        } else if ("+".equals(str)) {
            int last = stack.pop();
            int newtop = last + stack.peek();
            stack.push(last);
            stack.push(newtop);
        } else {
            stack.push(Integer.parseInt(str));
        }
    }
    int sum = 0;
    for (int n : stack) {
        sum += n;
    }
    return sum;
}

05 小结

算法专题目前已日更超过四个月，算法题文章156+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！