算法:什么是棒球游戏问题?

250 阅读2分钟

在这里插入图片描述

最近,社区准备举行棒球比赛,小多米积极报名参加了志愿者,帮助比赛记录分数。这是小多米第一次报名参加社区活动,第二天一大早,她就去接受记录分数的培训了。

下午,小多米回到家,没有了出门时的兴高采烈,脸上多了些愁容。问了才知道,原来记分规则她听明白了,但是总分怎么算还不知道。

棒球比赛记分规则如下: 给定一个字符串数组,每一个字符串可以是以下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

上面就是算法中“棒球游戏”问题。聪明的你,知道怎么帮助小多米解决这个问题吗?