:-: 11.1 棒球比赛 * * * * * **题干：** 你现在是棒球比赛记录员。给定一个字符串列表，每个字符串可以是以下四种类型之一： 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。 ~~~ **题目分析：** 由题目可得，只要是能转换为整数的字符串都直接相加，然后我们把每轮的分数都保存起来，留作后用，然后我们遇到“+”字符串，就直接取我们保留的每轮分数中的后两个分数相加，然后把相加后的分数保存下来，接着如果遇到“D”字符串，就直接取我们保留的每轮分数中的最后的分数乘以2，然后把此分数保存下来，最后如果我们遇到“C”字符串，就用当前总分数，减去我们保留的每轮分数中的最后的分数，然后将这个保留的每轮分数中的最后的分数删除或者下次覆盖。 **新手有可能遇到的解题思路陷阱：** 遇到“C”字符串，用当前总分数，减去我们保留的每轮分数中的最后的分数之后，并没有然后将这个保留的每轮分数中的最后的分数删除或者下次覆盖。这样就会造成下次遇到“+”、 “D”难以处理的情况。 **解题思路分析以及代码实现：** 第一种思路：数组法。 为什么使用Integer.parseInt()？原因可以看看这两个博客，也可以另外搜索。 [Java中valueOf与parseInt方法比较](https://blog.csdn.net/polar_geass/article/details/78977492) [Integer.parseInt(s)与Integer.valueOf(s)的区别详解](https://blog.csdn.net/u010502101/article/details/79162587) 第一种思路代码： ~~~ public int calPoints(String[] ops) { int sum = 0, number = 0, i = -1; int[] num = new int[ops.length]; for (String str : ops) { switch (str) { case "C": sum -= num[i]; i--; break; case "D": number = num[i] * 2; sum += number; num[++i] = number; break; case "+": int one = num[i]; int two = num[i - 1]; sum += one + two; num[++i] = one + two; break; default: i++; number = Integer.parseInt(str); num[i] = number; sum += number; break; } } return sum; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：常用集合法。 我们是采用ArrayList、还是LinkList呢？ [LinkedList、ArrayList详解（译文）](https://github.com/giantray/stackoverflow-java-top-qa/blob/master/contents/when-to-use-linkedlist-over-arraylist.md) [Java基础 ArrayList与LinkedList区别](https://www.jianshu.com/p/30a8195f0b81) [Java中arraylist和linkedlist的区别](https://www.imooc.com/article/5425) [arrayList、linkList众解](https://www.nowcoder.com/questionTerminal/75e2c8ab79a045b5842947656859e9e3) 第二种思路代码： ~~~ public int calPoints(String[] ops) { int sum = 0, number = 0; List<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < ops.length; i++) { switch (ops[i]) { case "C": sum -= list.get(list.size() - 1); list.remove(list.size() - 1); break; case "D": number = list.get(list.size() - 1) * 2; sum += number; list.add(number); break; case "+": int one = list.get(list.size() - 1); int two = list.get(list.size() - 2); sum += one + two; list.add(one + two); break; default: number = Integer.parseInt(ops[i]); list.add(number); sum += number; break; } } return sum; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(n)。 第三种思路：栈。 第三种思路代码： ~~~ public int calPoints(String[] ops) { Stack<Integer> stack = new Stack<Integer>(); int sum = 0; for (String op : ops) { char ch = op.charAt(0); //判断是否为数字或负数 if (Character.isDigit(ch) || ch == '-') { stack.push(Integer.parseInt(op)); res += stack.peek(); } if (ch == 'C') res -= stack.pop(); if (ch == 'D') { stack.push(stack.peek() * 2); res += stack.peek(); } if (ch == '+') { int one = stack.pop(); int two = stack.peek() + one; stack.push(one); stack.push(two); res +=two; } } return res; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(n)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**