BaseballGame [source code]
public class BaseballGame {
static
/******************************************************************************/
class Solution {
public int calPoints(String[] ops) {
int sum = 0;
Stack<Integer> stack = new Stack<>();
for (String op : ops) {
if (op.equals ("+")) {
assert stack.size () >= 2;
int score2 = stack.pop (), score1 = stack.pop (), new_score = score1 + score2;
stack.push (score1);
stack.push (score2);
stack.push (new_score);
sum += new_score;
} else if (op.equals ("D")) {
int score = stack.pop ();
int new_score = score * 2;
stack.push (score);
stack.push (new_score);
sum += new_score;
} else if (op.equals ("C")) {
sum -= stack.pop ();
} else {
Integer score = null;
try {
score = Integer.parseInt (op);
} catch (Exception e) {
e.printStackTrace ();
}
stack.push (score);
sum += score;
}
}
return sum;
}
}
/******************************************************************************/
public static void main(String[] args) {
BaseballGame.Solution tester = new BaseballGame.Solution();
String[][] inputs = {
{"5","2","C","D","+"}, {"30"},
{"5","-2","4","C","D","9","+","+"}, {"27"},
};
for (int i = 0; i < inputs.length / 2; i++) {
String[] ops = inputs[2 * i];
int ans = Integer.parseInt (inputs[2 * i + 1][0]);
int output = tester.calPoints (ops);
System.out.println (Printer.separator ());
System.out.println (Printer.array (ops) + " -> " + Printer.wrapColor (output, output == ans ? "green" : "red") + ", expected: " + ans);
}
}
}
题目比较长, 看了好几分钟才看懂; 看懂了还是大概理解到底是什么意思了;
题目看完了之后写代码实际上没有花多少时间, 大概实际上算上debug是肯定不到15分钟的; 最后的速度是11ms (26%), 所以感觉还有上升的余地;
editorial的第一个解法:
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;
}
}
这个解法基本跟我的解法是类似的, 不过一点小细节, 比如他处理+的时候, 只pop一个, 另外一个peek, 这个其实我是想到了, 懒得这样做; 比如他parse int的时候, 没有处理exception, 这个我觉得没有什么好学的; 我这里处理这个exception, 其实是为了避免人家的input故意给你一个比如不正常的op这种; 当然, 他也没有维护sum, 而是最后单独走一遍, 这个其实是值得我学习到的;
不过回头想想, 好像我assertion加的不够多, 比如C的我就没有加, 不过知道就是最好的;
editorial好像就没有给出其他的解法了;
discussion里面也有人讨论invalid sequence的问题, 比如尤其是你开头就是一个C, 怎么办, C的是什么, 等等. 有一个人给出一个很聪明的方案:
@tndstone said in Straightforward Python:
Simply add two 0 at the left of the input list would solve this problem.
这个确实是不错的;
这个是一个对应的Python版本:
class Solution(object):
def calPoints(self, ops):
# Time: O(n)
# Space: O(n)
history = []
for op in ops:
if op == 'C':
history.pop()
elif op == 'D':
history.append(history[-1] * 2)
elif op == '+':
history.append(history[-1] + history[-2])
else:
history.append(int(op))
return sum(history)
可以看到Python这个语言有些时候真的是非常方便, 尤其这里, 是可以从end开始access的能力; 直接就可以当Stack用;
LinkedList版本:
class Solution {
public int calPoints(String[] ops) {
int sum = 0;
LinkedList<Integer> list = new LinkedList<>();
for (String op : ops) {
if (op.equals("C")) {
sum -= list.removeLast();
}
else if (op.equals("D")) {
list.add(list.peekLast() * 2);
sum += list.peekLast();
}
else if (op.equals("+")) {
list.add(list.peekLast() + list.get(list.size() - 2));
sum += list.peekLast();
}
else {
list.add(Integer.parseInt(op));
sum += list.peekLast();
}
}
return sum;
}
}
没有什么特别的, 就是熟悉一下LinkedList的API而已, LinkedList本身的interface确实是非常丰富的; 这题主要其实并不是非常依赖Stack Property, 所以用一个list是完全可以的;
一个简练的Stack版本:
public int calPoints(String[] ops) {
int ans = 0;
Stack<Integer> stk = new Stack<>();
for (String op : ops) {
if (op.equals("C")) { ans -= stk.pop (); continue; }
else if (op.equals ("D")) stk.push (stk.peek () * 2);
else if (op.equals ("+")) stk.push (stk.get(stk.size () - 1) + stk.get(stk.size () - 2));
else stk.push (Integer.valueOf (op));
ans += stk.peek();
}
return ans;
}
所以Stack其实也是可以get的;
submission最优解6(99):
class Solution {
public int calPoints(String[] ops) {
String temp_str;
int pos = 0;
int[] temp_array = new int [2 * ops.length];
int sum = 0;
int temp;
for (int i = 0; i < ops.length; i++)
{
temp_str = ops[i];
if (temp_str.charAt(0) == 'C')
{
pos--;
sum -= temp_array[pos];
}
else if (temp_str.charAt(0) == '+')
{
temp_array[pos] = temp_array[pos - 1] + temp_array[pos - 2];
pos++;
sum += temp_array[pos-1];
}
else if (temp_str.charAt(0) == 'D')
{
temp_array[pos] = temp_array[pos - 1] + temp_array[pos - 1];
pos++;
sum += temp_array[pos-1];
}
else if (temp_str.charAt(0) == '-')
{
temp = 0;
for (int j = 1; j < temp_str.length(); j++)
{
temp *= 10;
temp += temp_str.charAt(j) - 48;
}
temp_array[pos] = (-temp);
pos++;
sum += (-temp);
}
else
{
temp = 0;
for (int j = 0; j < temp_str.length(); j++)
{
temp *= 10;
temp += temp_str.charAt(j) - 48;
}
temp_array[pos] = temp;
pos++;
sum += temp;
}
}
return sum;
}
}
比较无聊, 就是强行用array造轮子而已; 想写也行, 对于实际的工作和interview反正都没有什么帮助就是了;
Problem Description
You're now a baseball game point recorder.
Given a list of strings, each string can be one of the 4 following types:
- Integer (one round's score): Directly represents the number of points you get in this round.
- "+" (one round's score): Represents that the points you get in this round are the sum of the last two valid round's points.
- "D" (one round's score): Represents that the points you get in this round are the doubled data of the last valid round's points.
- "C" (an operation, which isn't a round's score): Represents the last valid round's points you get were invalid and should be removed.
Each round's operation is permanent and could have an impact on the round before and the round after.
You need to return the sum of the points you could get in all the rounds.
Example 1:
Input: ["5","2","C","D","+"]
Output: 30
Explanation:
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get 2 points. The sum is: 7.
Operation 1: The round 2's data was invalid. The sum is: 5.
Round 3: You could get 10 points (the round 2's data has been removed). The sum is: 15.
Round 4: You could get 5 + 10 = 15 points. The sum is: 30.
Example 2:
Input: ["5","-2","4","C","D","9","+","+"]
Output: 27
Explanation:
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get -2 points. The sum is: 3.
Round 3: You could get 4 points. The sum is: 7.
Operation 1: The round 3's data is invalid. The sum is: 3.
Round 4: You could get -4 points (the round 3's data has been removed). The sum is: -1.
Round 5: You could get 9 points. The sum is: 8.
Round 6: You could get -4 + 9 = 5 points. The sum is 13.
Round 7: You could get 9 + 5 = 14 points. The sum is 27.
Note:
- The size of the input list will be between 1 and 1000.
- Every integer represented in the list will be between -30000 and 30000.
Difficulty:Easy
Total Accepted:14.6K
Total Submissions:25K
Contributor:今が最高
Companies
amazon
Related Topics
stack