栈与队列力扣经典例题20. 有效的括号1047. 删除字符串中的所有相邻重复项150. 逆波兰表达式求值

本文主要是介绍栈与队列力扣经典例题20. 有效的括号1047. 删除字符串中的所有相邻重复项150. 逆波兰表达式求值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对于栈与队列,我们首先要搞清楚,栈是先入后出,而队列是先入先出,利用这个特性,我们来判断题目用什么STL容器,便于我们去解决问题

20. 有效的括号

这道题,首先我们要知道哪些情况,是会使结果变为false的,第一种就是括号数是奇数,那肯定不能两两匹配,第二种就是括号数是偶数可以匹配,但是括号类型不对,就像case 3一样

class Solution {
public:bool isValid(string s) {stack<char>str;if(s.size()%2){return false;}for(int i=0;i<s.size();i++){if(s[i]=='(')str.push(')');else  if(s[i]=='[')str.push(']');else  if(s[i]=='{')str.push('}'); else if(str.empty()||str.top()!=s[i])return false;else str.pop();}return str.empty();}
};

 1047. 删除字符串中的所有相邻重复项

遇到这种题我们的思路就是,遍历数组,如果遍历到的数与栈顶元素相同,那么栈顶元素出栈,再遍历下一个,如果不同才可以入栈

class Solution {
public:string removeDuplicates(string s) {int n=s.size();stack<char>st;for(int i=0;i<n;i++){if(!st.empty()&&s[i]==st.top()){st.pop();continue;}st.push(s[i]);} string ss="";int t=size(st);for(int i=0;i<t;i++){ss+=st.top();st.pop();}reverse(ss.begin(),ss.end());//记得翻转字符串return ss;}
};

 

150. 逆波兰表达式求值

这道题的思路就是,当我们碰到的是一个数时,我们就让它入栈,如果碰到一个运算符号,我们就进行对应的运算,再将运算结果入栈

class Solution {
public:int evalRPN(vector<string>& tokens) {// 力扣修改了后台测试数据,需要用longlongstack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result = st.top();st.pop(); // 把栈里最后一个元素弹出(其实不弹出也没事)return result;}
};

 

这篇关于栈与队列力扣经典例题20. 有效的括号1047. 删除字符串中的所有相邻重复项150. 逆波兰表达式求值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/770297

相关文章

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s