1.栈OJ(C++)
1.1 最小栈
不是原生地去实现一个栈,而是自己去封装实现。但是它有额外的要求,提供一个getMin的函数,且这个getMin要求在常数时间完成。
很多同学的想法是设计一个最小值来记录最小值。这个想法其实是不合理的。
入栈的时候记录最小值,最小值出栈再遍历找最小。大家想想,如果这样设计的问题在哪?最大的问题在于我要是pop一下呢?最小值pop后再遍历找最小。问题是栈不支持遍历,有同学又说那我用一个vector存储数据,但是这样时间复杂度就变成O(n)了呀。
这里真正的实现方案是这样:不要用min来存储最小值,而是用两个栈。一个是正常存储数据的栈,一个是存最小值的栈。
st正常push数据,对于minst如果最小值更新,就push更新后的最小值,如果没有更新则push之前的最小值。删除就依次删除,就达到了O(1)的要求,以空间换时间。
大家想想当前设计的方案还有没有什么缺陷?或者说有没有优化的空间?
大家有没有发现这样重复存了好多5。那我们这里优化一下,不重复进,不用更新最小值我们都不进。那我们这里就不是你删除一个我删除一个了,st删除最小值时minst才删。但是这种写法要注意连续重复的最小值。所以对于minst,<=栈顶值的时候进数据。
代码实现:
class MinStack {
public:
//自定义类型不需要我们写构造函数
MinStack() {
}
void push(int val) {
_st.push(val);
// 最小栈进数据
if(_minst.empty() || val <= _minst.top())
{
_minst.push(val);
}
}
void pop() {
if(_st.top() == _minst.top())
_minst.pop();
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack<int> _st;
stack<int> _minst;
};
1.2栈的压入、弹出序列
这道题题意还是很简单的,它说给你一个入栈序列和一个出栈序列,看对不对得上。
我们知道出栈的顺序是有很多种的,所以这道题还是有点麻烦。
这道题其实没有什么好的解法,我们用一个栈来模拟:我这个入栈序列是不是能模拟出出栈顺序,能就符合true,模拟不出来就符合false。
模拟出栈顺序:
1、入栈序列先入栈。每次入栈后,栈顶和出栈序列比较。
a、如果能匹配,出栈序列往后出栈。
b、不能匹配:(1)说明这个数据可能还没入栈,继续入栈。
(2)入栈序列已经走到尾了,说明数据一定在栈中,只是顺序不对,出栈序列非法。
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> st;
size_t popi = 0;
for(auto e : pushV)
{
st.push(e);
while(!st.empty() && st.top() == popV[pop1])
{
++popi;
st.pop();
}
}
//return popi == popV.size();
return st.empty();
}
};
1.3 逆波兰表达式求值
逆波兰表达式又叫后缀表达式,与之对应的还有中缀表达式,没有前缀表达式。
中缀就是运算符在两个数字或者表达式中间,但是中缀计算机没法计算,因为计算机是一个一个读取表达式的数据,要涉及优先级。
所以这个时候就会先转换为后缀表达式再进行计算,操作数的顺序还是不变,运算符要按照优先级排序。
但是这道题的难度没那么大,因为它直接就是给的后缀表达式,直接就可以进行运算。
后缀表达式运算很简单:
1.遇到操作数就入栈
2.遇到操作符,就取连续两个栈顶数据运算,运算结果继续入栈。
记住,先取出来的是右操作数,后取出来的是左操作数。因为左边先入栈右边后入栈,后进先出。这个地方区分左右是因为*和+不区分左右,/和-要区分左右。所以左右操作数的顺序不能乱。
我们拓展来讲一讲如何中缀转后缀:
1.遇到操作数,输出或者存储起来
2.遇到操作符先入栈,之后入栈就和栈顶操作符比较:
a、栈为空或者比栈顶优先级高入栈,之后继续重复1步骤。
b、比栈顶操作符优先级低/一样,出栈顶操作符。之后继续重复2步骤。
3.将栈中操作符全部出栈
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
//&减少拷贝
for(const auto& str : tokens)
{
if(str == "+" || str == "-"
|| str == "*" || str == "/")
{
int right = st.top();
st.pop();
int left = st.pop();
st.pop();
switch(str[0])
{
case '+':
st.push(left+right);
break;
case '-':
st.push(left-right);
break;
case '/':
st.push(left/right);
break;
default:
break;
}
}
else
{
//字符串转整型为了符合switch语句
st.push(stoi(str));
}
}
return st.pop();
}
};
}
else
{
//字符串转整型为了符合switch语句
st.push(stoi(str));
}
}
return st.pop();
}
};