数据结构刷题——栈(下)_std i hurt o love的博客-爱代码爱编程
一、逆波兰表达式求值
解法:栈
逆波兰表达式求值的过程总是先列出运算符前面两个数字,然后将这两个数字进行相应运算,得到一个新的数字,这个数又与后面的数进行相应运算,直到结束。
所以,可以先新建一个栈,当遇到数字时,直接压入栈中,遇到运算符时,先取出栈顶的两个数字,进行相应运算,再压回栈中。最后栈中剩下的那个元素即是表达式的值。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param tokens string字符串vector
* @return int整型
*/
int evalRPN(vector<string>& tokens) {
// write code here
stack<int> s;
int num,num1,num2,tmp;
for(auto i:tokens){
if(i=="+"|| i=="-"|| i=="*"|| i=="/")
{
num1=s.top();
s.pop();
num2=s.top();
s.pop();
if(i=="+")
tmp=num2+num1;
else if(i=="-")
tmp=num2-num1;
else if(i=="*")
tmp=num2*num1;
else if(i=="/")
tmp=num2/num1;
s.push(tmp);
}
else
{
num = atoi(i.c_str());
s.push(num);
}
}
return s.top();
}
};
时间复杂度:需要遍历整个字符串数组,所以时间复杂度是O(n)。
空间复杂度:最坏情况下,总共有(n+1)/2个数压入栈中,所以至多需要额外大小为(n+1)/2的栈,所以空间复杂度为O(n)。
二、点击消除
解法:栈
- 创建一个空栈;输入元素;
- 遍历s,如果栈内元素为0,则直接添加;否则,如果栈内最后一个元素与i相等,则弹出该元素;否则直接添加;
- 如果栈长度为0,打印0;否则,逐个打印
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int main()
{
string str;
cin>>str;
stack<char>s;
for(auto i:str)
{
if(s.empty())
s.push(i);
else
{
if(i==s.top())
s.pop();
else
s.push(i);
}
}
if(s.empty())
cout<<0<<endl;
else
{
str.clear();
while(!s.empty())
{
str+=s.top();
s.pop();
}
reverse(str.begin(),str.end());
cout<<str<<endl;
}
return 0;
}
时间复杂度:O(n),遍历字符串
空间复杂度:O(n),栈最大为n
三、最长的括号子串
解法:
因为括号需要一一匹配,而且先来的左括号,只能匹配后面的右括号,因此可以考虑使用栈的先进后出功能,使括号匹配。
- 可以使用栈来记录左括号下标。
- 遍历字符串,左括号入栈,每次遇到右括号则弹出左括号的下标。
- 然后长度则更新为当前下标与栈顶下标的距离。
- 遇到不符合的括号,可能会使栈为空,因此需要使用start记录上一次结束的位置,这样用当前下标减去start即可获取长度,即得到子串。
- 循环中最后维护子串长度最大值。
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0;
//记录上一次连续括号结束的位置
int start = -1;
stack<int> st;
for(int i = 0; i < s.length(); i++){
//左括号入栈
if(s[i] == '(')
st.push(i);
//右括号
else{
//如果右括号时栈为空,不合法,设置为结束位置
if(st.empty())
start = i;
else{
//弹出左括号
st.pop();
//栈中还有左括号,说明右括号不够,减去栈顶位置就是长度
if(!st.empty())
res = max(res, i - st.top());
//栈中没有括号,说明左右括号行号,减去上一次结束的位置就是长度
else
res = max(res, i - start);
}
}
}
return res;
}
};