682. 棒球比赛
2023-02-18 16:34:56 时间
682. 棒球比赛
你现在是棒球比赛记录员。
给定一个字符串列表,每个字符串可以是以下四种类型之一:
1.整数(一轮的得分):直接表示您在本轮中获得的积分数。
2. "+"(一轮的得分):表示本轮获得的得分是前两轮有效 回合得分的总和。
3. "D"(一轮的得分):表示本轮获得的得分是前一轮有效 回合得分的两倍。
4. "C"(一个操作,这不是一个回合的分数):表示您获得的最后一个有效 回合的分数是无效的,应该被移除。
每一轮的操作都是永久性的,可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
代码:
#include<iostream>
#include<stack>
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
string init(){
string str;
cin>>str;
return str;
}
stack<int> st;
int main(){
string str= init();
char ch;
int num1,num2,sum=0;
int len=str.length();
for (int i = 0; i < len; i++)
{
ch=str[i];
switch (ch)
{
case 'C':
if(!st.empty()){
st.pop();
}
break;
case 'D':
if(!st.empty()){
st.push(st.top()*2);
}
break;
case '+':
if(st.size()>=2){
num1=st.top();
st.pop();
num2 =st.top();
st.pop();
st.push(num1);
st.push(num2);
st.push(num1+num2);
}
break;
default:
st.push(ch-'0');
break;
}
}
// cout<<st.size();
while(!st.empty()){
sum+=st.top();
// cout<<st.top()<<" ";
st.pop();
}
cout<<sum<<endl;
// 52CD+
}
方法:栈
思路与算法
让我们在处理数据时保持栈上每个有效回合的值。栈是理想的,因为我们只处理涉及最后或倒数第二轮的操作。
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;
}
}
复杂度分析
复杂度分析:O(N),其中 N 是 ops 的长度。我们解析给定数组中的每个元素,然后每个元素执行 O(1)的工作。
空间复杂度:O(N),用于存储 stack 的空间。
相关文章
- HTML5项目笔记10:使用HTML5 IndexDB设计离线数据库
- HTML5项目笔记9:HTML5 Canvas 的图表报表开发
- HTML5项目笔记8:使用HTML5 的跨域通信机制进行数据同步
- HTML5项目笔记7:使用HTML5 WebStorage API构建与.NET对应的会话机制
- HTML5项目笔记6:使用HTML5 FileSystem API设计离线文件存储
- HTML5项目笔记5:使用HTML5 WebDataBase设计离线数据库
- HTML5项目笔记4:使用Audio API设计绚丽的HTML5音乐播放器
- HTML5项目笔记2:离线系统表单设计
- HTML5项目笔记1:项目准备和工具使用
- Web前端设计模式--购物车拖拽的实现...
- LinQ构建分层架构
- Web前端设计模式--构建Ajax智能搜索...
- Web前端设计模式--制作漂亮的弹出层...
- Web 前端设计模式--Dom重构...
- Web前端设计模式--jQuery验证插件...
- PBN主区代表95%时间概率的范围,这个理解对么?
- 第九节 RNP APCH保护区的绘制
- 第八节 起始进近基线转弯保护区的绘制
- 第七节 VOR/DME进近程序保护区的绘制
- 第六节 FAF与GP不工作保护区的绘制