你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
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之间。
题目数组中共出现4类元素：数字、“c”、“d”、“+”；
数字不用解释了，就是具体分数，可以是任意数值，正负都可，
“c”是前一有效数据无效化，可以理解为将前一数据删除，
“d”是前一有效数据的2倍，
“+”是前两个有效数据的和。
我首先想到的是：使用indexof方法，找到对应“c”、“d”、“+”操作的位置，
然后进行相应操作：
这个“c”最早在考虑的时候想复杂了：如果“c”前面有“d”或者“+”怎么办？
其实无论“c”前面是什么，都是无效的，
比如["1","2","3","+","c"]、["1","2","3","d","c"]，甚至是["1","2","3","c","c"]，都可以将“c”以及其前面的元素删除掉
找到“c”的位置后，使用数组的splice方法，将其与前面一个元素一起删除掉，
代码片段如下：
我要评论let invalid=arr.indexof("c");
if(invalid!==-1) {
arr.splice(invalid-1,2);
}else{
break;
}
我优先找了“d”，
因为“d”相对比较直接，只需判断其前面一个数据是不是非数字，
如果“d”前面还是“d”，则传入该元素前一索引位置，继续调用该函数，
如果“d”前面是“+”，则传入该元素前一索引位置，调用处理“+”对应的函数。
代码片段如下：
function multfun(index){
while(index){
if(arr[index-1]==="+"){
addfun(index-1);
}else if(arr[index-1]==="d"){
multfun(index-1);
}else{
arr[index]=2*arr[index-1];
}
break;
}
while(!index){
let mult=arr.indexof("d");
if(mult!==-1) {
if(arr[mult-1]==="+"){
addfun(mult-1);
}else if(arr[mult-1]==="d"){
multfun(mult-1);
}else{
arr[mult]=2*arr[mult-1];
}
}else{
break;
}
}
}
如果“+”前面是“d”，则传入该元素前一索引位置，继续调用该函数（这种情况不大可能出现，因为按现在的顺序，在此之前“d”已经全部被转化过了，不过万一先找“+”，后找“d”，这段代码就有用了），
如果“d”前面是“+”，则传入该元素前一索引位置，调用“+”对应的函数继续。
代码片段如下：
function addfun(index) {
while(index){
if(arr[index-1]==="+"){
addfun(index-1);
}else if(arr[index-2]==="+"){
addfun(index-2);
}else if(arr[index-1]==="d"){
multfun(arr[index-1]);
}else if(arr[index-2]==="d"){
multfun(arr[index-2]);
}else{
arr[index]=number(arr[index-1])+number(arr[index-2]);
}
break;
}
while(!index){
let add=arr.indexof("+");
if(add!==-1) {
if(arr[add-1]==="+"){
addfun(add-1);
}else if(arr[add-2]==="+"){
addfun(add-2);
}else if(arr[add-1]==="d"){
multfun(arr[add-1]);
}else if(arr[add-2]==="d"){
multfun(arr[add-2]);
}else{
arr[add]=number(arr[add-1])+number(arr[add-2]);
}
}else{
break;
}
}
}
依次调用处理“c”的函数：invalidfun();
处理“d”的函数：multfun();
处理“+”的函数：addfun();
之后求和：reduce();
此处碰到了坑：之前在addfun()的时候也遇到过，
数组元素相加时，若存在字符串："1"+2,1+"2",''1"+"2",结果都是"12",而不是想要得到的3；
所以在“加”运算的时候，都先number()强制转换一下，即可得到正常结果。
代码片段如下：
let arr=ops;
invalidfun();
multfun();
addfun();
return arr.reduce(function (prev, cur) {
return number(prev) + number(cur);
},0);
完整代码如下：（leetcode提交通过，执行用时：92ms）
var calpoints = function(ops) {
function invalidfun() {
while(1){
let invalid=arr.indexof("c");
if(invalid!==-1) {
arr.splice(invalid-1,2);
}else{
break;
}
}
}
function multfun(index){
while(index){
if(arr[index-1]==="+"){
addfun(index-1);
}else if(arr[index-1]==="d"){
multfun(index-1);
}else{
arr[index]=2*arr[index-1];
}
break;
}
while(!index){
let mult=arr.indexof("d");
if(mult!==-1) {
if(arr[mult-1]==="+"){
addfun(mult-1);
}else if(arr[mult-1]==="d"){
multfun(mult-1);
}else{
arr[mult]=2*arr[mult-1];
}
}else{
break;
}
}
}
function addfun(index) {
while(index){
if(arr[index-1]==="+"){
addfun(index-1);
}else if(arr[index-2]==="+"){
addfun(index-2);
}else if(arr[index-1]==="d"){
multfun(arr[index-1]);
}else if(arr[index-2]==="d"){
multfun(arr[index-2]);
}else{
arr[index]=number(arr[index-1])+number(arr[index-2]);
}
break;
}
while(!index){
let add=arr.indexof("+");
if(add!==-1) {
if(arr[add-1]==="+"){
addfun(add-1);
}else if(arr[add-2]==="+"){
addfun(add-2);
}else if(arr[add-1]==="d"){
multfun(arr[add-1]);
}else if(arr[add-2]==="d"){
multfun(arr[add-2]);
}else{
arr[add]=number(arr[add-1])+number(arr[add-2]);
}
}else{
break;
}
}
}
let arr=ops;
invalidfun();
multfun();
addfun();
return arr.reduce(function (prev, cur) {
return number(prev) + number(cur);
},0);
};
之后又参考官方题解：
方法：栈
思路与算法
让我们在处理数据时保持栈上每个有效回合的值。栈是理想的，因为我们只处理涉及最后或倒数第二轮的操作。
复杂度分析
复杂度分析：o(n)o(n)，其中 nn 是
ops的长度。我们解析给定数组中的每个元素，然后每个元素执行 o(1)o(1) 的工作。空间复杂度：o(n)o(n)，用于存储
stack的空间。
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;
}
}
class solution(object):
def calpoints(self, ops):
stack = []
for op in ops:
if op == '+':
stack.append(stack[-1] + stack[-2])
elif op == 'c':
stack.pop()
elif op == 'd':
stack.append(2 * stack[-1])
else:
stack.append(int(op))
return sum(stack)
发现这样写代码，精简多了，手动捂脸，
如对本文有疑问， 点击进行留言回复！！
offset、client、scroll (width,height、left,top、X,Y)
网友评论