每日编程中遇到任何疑问、意见、建议请公众号留言或直接撩Q474356284(备注每日编程)
你现在是棒球比赛记录员。
给定一个字符串列表,每个字符串可以是以下四种类型之一:
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。
注意:
输入列表的大小将介于1和1000之间。
列表中的每个整数都将介于-30000和30000之间。
解决方法:
(1)算法的基本思想:
注意点:
①atio可以将直接将字符串“-2”转成数字-2
②num = atoi(ops[i].substr(0).c_str());
substr()函数 原型为:basic string::substr(string,start,length),也可把string移到外面,为string &a,a.substr(start,length),其中a是待截取的字符串,start表示从截取开始的前一位,length表示截取长度,例如string &a="hello world",则a.substr(6,5)=world.
c_str()函数 原型为:const char *c_str(),如果要将string对象,转化为char*对象,c_str()提供了这样一种方法,它返回一个客户程序可读不可改的指向字符数组的指针。
atoi()函数 原型为:int atoi(char *str),用途是将字符串转换成一个整数值,str是待转化成整数值的字符串.成功责返回转化后的整数值,失败返回0
③对一个vector元素求和。
int sum=accumulate(n.begin(),n.end(),0);
如果元素为int机返回累计的和
如果元素为string,则将字符串连接起来
(2)代码实现:
算法一:
class Solution {
public:
int calPoints(vector<string>& ops) {
int num = 0;
int flag = 1;
vector<int> n;
for(int i = 0;i<ops.size();i++)
{
if(ops[i][0] == '-'){
flag = -1;
num = atoi(ops[i].substr(1).c_str()) * flag;
n.push_back(num);
}
else if(isdigit(ops[i][0])){
num = atoi(ops[i].substr(0).c_str());
n.push_back(num);
}
else if(ops[i][0] == 'D'){
n.push_back(n.back()*2);
}
else if(ops[i][0] == 'C')
{
n.pop_back();
}
else if(ops[i][0] == '+')
n.push_back(n[n.size()-1]+n[n.size()-2]);
}
int sum=accumulate(n.begin(),n.end(),0);
return sum;
}
};算法二(更优秀的逻辑):class Solution {
public:
int calPoints(vector<string>& ops) {
stack<int> st;
int n = ops.size();
for(int i=0; i<n; i++){
if(ops[i] == "+"){
int a = st.top();
st.pop();
int b = st.top();
st.push(a);
st.push(a+b);
}else if(ops[i] == "D"){
int a = st.top();
st.push(2*a);
}else if(ops[i] == "C"){
st.pop();
}else{
int a = atoi(ops[i].c_str());
st.push(a);
}
}
int sum = 0;
while(!st.empty()){
sum += st.top();
st.pop();
}
return sum;
}
};
使用栈实现队列的下列操作:
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 -- 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
}
/** Get the front element. */
int peek() {
}
/** Returns whether the queue is empty. */
bool empty() {
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/