LeetCode每日一题题解:682. 棒球比赛-题解-python && C++源代码

简介: LeetCode每日一题题解:682. 棒球比赛-题解-python && C++源代码

682. 棒球比赛


难度简单208收藏分享切换为英文接收动态反馈


你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成,过去几回合的得分可能会影响以后几回合的得分。


比赛开始时,记录是空白的。你会得到一个记录操作的字符串列表 ops,其中 ops[i] 是你需要记录的第 i 项操作,ops 遵循下述规则:


整数 x - 表示本回合新获得分数 x

"+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。

"D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。

"C" - 表示前一次得分无效,将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。

请你返回记录中所有得分的总和。


示例 1:


输入:ops = ["5","2","C","D","+"]

输出:30

解释:

"5" - 记录加 5 ,记录现在是 [5]

"2" - 记录加 2 ,记录现在是 [5, 2]

"C" - 使前一次得分的记录无效并将其移除,记录现在是 [5].

"D" - 记录加 2 * 5 = 10 ,记录现在是 [5, 10].

"+" - 记录加 5 + 10 = 15 ,记录现在是 [5, 10, 15].

所有得分的总和 5 + 10 + 15 = 30

示例 2:


输入:ops = ["5","-2","4","C","D","9","+","+"]

输出:27

解释:

"5" - 记录加 5 ,记录现在是 [5]

"-2" - 记录加 -2 ,记录现在是 [5, -2]

"4" - 记录加 4 ,记录现在是 [5, -2, 4]

"C" - 使前一次得分的记录无效并将其移除,记录现在是 [5, -2]

"D" - 记录加 2 * -2 = -4 ,记录现在是 [5, -2, -4]

"9" - 记录加 9 ,记录现在是 [5, -2, -4, 9]

"+" - 记录加 -4 + 9 = 5 ,记录现在是 [5, -2, -4, 9, 5]

"+" - 记录加 9 + 5 = 14 ,记录现在是 [5, -2, -4, 9, 5, 14]

所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27

示例 3:


输入:ops = ["1"]

输出:1

提示:


1 <= ops.length <= 1000

ops[i] 为 "C"、"D"、"+",或者一个表示整数的字符串。整数范围是 [-3 * 104, 3 * 104]

对于 "+" 操作,题目数据保证记录此操作时前面总是存在两个有效的分数

对于 "C" 和 "D" 操作,题目数据保证记录此操作时前面总是存在一个有效的分数

题解:


构建单调栈,然后遍历字符数组,遇到数字,则压入堆栈,遇到“C”则,弹出栈顶的值,遇到“D”则将栈顶的值*2然后压入单调栈

遇见“+”则将栈顶的值和栈顶前一个值相加压入堆栈、


Python代码:

class Solution:
    def calPoints(self, ops: List[str]) -> int:
        ats , i = [] , 0     #构建单调栈
        while i<len(ops):
            if ops[i] == 'C':  #当访问的值为“C”的时候,因为需要删除之前的值,所以弹出栈顶的值即可
                ats.pop()              
            elif ops[i] == 'D':     #如果是"D"则需要将之前的数字字符,变成整数*2
                ats.append(ats[-1]*2)
            elif ops[i] == "+":     #若为“+”,则将前两个数 即栈顶和栈顶之前的数 变成整数再相加
                ats.append(ats[-1] + ats[-2])
            else:         #如为数字,则直接变成整数压入单调栈
                ats.append(int(ops[i]))
            i += 1
        return sum(ats)     #输出相加后的结果

C++代码:

class Solution {
public:
    int calPoints(vector<string>& ops) {
        stack<int> ats;
        int i = 0 , a = 0;
        while(i<ops.size()){
             if (ops[i] == "C"){
                 a -= ats.top();
                 ats.pop();
             }
             else if (ops[i] == "D"){
                 ats.push(2*ats.top());
                 a += ats.top();
             }
             else if (ops[i] == "+"){
                 int d = ats.top();
                 ats.pop();
                 int b = ats.top();
                 ats.push(d);
                 ats.push(d+b);
                 a += ats.top();
             }
             else{
                 ats.push(stoi(ops[i]));
                 a += ats.top();
             }
             i++;
        }
        return a;
    }
};
相关文章
|
2月前
|
移动开发 Python Windows
python编程获取网页标题title的几种方法及效果对比(源代码)
python编程获取网页标题title的几种方法及效果对比(源代码)
|
3月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
169 0
|
13天前
|
安全 Linux 数据安全/隐私保护
python知识点100篇系列(15)-加密python源代码为pyd文件
【10月更文挑战第5天】为了保护Python源码不被查看,可将其编译成二进制文件(Windows下为.pyd,Linux下为.so)。以Python3.8为例,通过Cython工具,先写好Python代码并加入`# cython: language_level=3`指令,安装easycython库后,使用`easycython *.py`命令编译源文件,最终生成.pyd文件供直接导入使用。
python知识点100篇系列(15)-加密python源代码为pyd文件
|
19天前
|
C++ Python
探索Python与C/C++混合编程的艺术
探索Python与C/C++混合编程的艺术
26 1
|
2月前
|
人工智能 算法 图形学
总有一个是你想要的分享40个Python游戏源代码
这是一系列基于Python开发的游戏项目集合,包括中国象棋、麻将、足球、坦克大战、扑克等多种类型游戏,运用了Pygame等库实现图形界面与AI算法。此外还包含迷宫、数独、推箱子等益智游戏及经典游戏如《仙剑奇侠传二战棋版》和《星露谷物语》的Python版本,适合编程学习与娱乐。
82 11
WK
|
2月前
|
机器学习/深度学习 Java 程序员
为什么Python比C++慢很多?
Python相较于C++较慢主要体现在:动态类型系统导致运行时需解析类型,增加开销;作为解释型语言,逐行转换字节码的过程延长了执行时间;自动内存管理和垃圾回收机制虽简化操作但也带来了额外负担;全局解释器锁(GIL)限制了多线程性能;尽管Python库方便灵活,但在性能上往往不及C++底层库。然而,Python在某些领域如数据分析、机器学习中,凭借其高级别抽象和简洁语法仍表现出色。选语言需依据具体应用场景和需求综合考量。
WK
59 1
|
2月前
|
关系型数据库 MySQL API
Python管理系统源代码
本文介绍了多种基于Python和相关技术的管理系统源代码,包括学生信息管理、图书管理、ERP、异常管理、考试系统等。提供了64个源代码供下载,适用于不同场景和个人项目需求。下载链接:https://pan.baidu.com/s/1hXPLbKHMpBDhlFVv1kdMxA?pwd=8888,提取码:8888。欢迎使用和支持。
37 3
|
3月前
|
PHP C++ Python
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
47 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2