您现在的位置是:首页 >技术交流 >【代码随想录】刷题Day11网站首页技术交流
【代码随想录】刷题Day11
简介【代码随想录】刷题Day11
1.栈解决括号判断问题
1.由于最先的左类括号是最后被判断的,所以我们使用的是栈来判断
2.如果碰到左类括号,那就直接入栈
3.如果碰到右类括号,如果栈中是空的,那么说明没有括号和它对应,直接返回false
4.如果碰到右类括号和stack的栈顶对应,说明栈顶可以出栈
5.如果不对应,也是无效的括号,返回false
6.最后循环走完的说明是成功的,返回true
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(auto e:s)
{
if(e=='('||e=='['||e=='{')
st.push(e);
else
{
if(st.empty()==1)
return false;
if(e==')'&&st.top()=='('||e==']'&&st.top()=='['||e=='}'&&st.top()=='{')
st.pop();
else
return false;
}
}
return st.empty();
}
};
2.栈删除相同临近的字符
1.由于我们要删除临近的字符,使用栈很合适,只要检查栈顶和要插入的是否一样。
2.进入循环将s中的值插入栈中:如果栈为空,或者栈顶元素和要插入元素不相同,说明此时元素可以被插入;此外的都是需要把栈顶元素删除
3.循环结束,需要把栈的元素全部交给字符串,但是元素出栈得到结果是倒着的,所以我们还要将得到的字符串reverse一下
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(auto e:s)
{
if(st.empty()||e!=st.top())
st.push(e);
else
st.pop();
}
string ret;
while(!st.empty())
{
ret += st.top();
st.pop();
}
reverse(ret.begin(),ret.end());
return ret;
}
};
3.逆波兰表达法求值
1.遇到数就入栈
2.遇到符号就出栈两个值,进行运算,注意前后,先出栈的是右边的数。运算得到的结果要返回栈中,以便进入下一轮计算
3.最后留在栈中的唯一一个数,就是我们要返回的结果
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for(int i=0;i<tokens.size();i++)
{
if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
{
int second = s.top();
s.pop();
int first = s.top();
s.pop();
if(tokens[i]=="+"){s.push(first+second);}
if(tokens[i]=="-"){s.push(first-second);}
if(tokens[i]=="*"){s.push(first*second);}
if(tokens[i]=="/"){s.push(first/second);}
}
else
s.push(stoi(tokens[i]));
}
return s.top();
}
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。