面试经典150题 -- 栈(总结)
总的链接
面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
关于栈 -- stack 的学习链接
c++的STL中的栈 -- stack-CSDN博客
20 . 有效的括号
这题直接用栈模拟就好了;
这里用一种取巧的方法 , 当遇见左括号，加入右括号，遇到右括号，直接判断栈顶元素是不是与当前元素相等(这样可以避免再开一个哈希表来存相应括号之间的映射关系),相等的话，pop栈顶，否则，直接return false;
class Solution {
public:
bool isValid(string s) {
stack<char> st ;
for(char c : s){
if(c=='(') st.push(')');
else if(c=='[') st.push(']');
else if(c=='{') st.push('}');
else if(st.empty() || st.top()!=c) return false;
else st.pop();
}
return st.empty() ;
}
};71 . 简化路径
先求出夹在两个/之间的目录名，根据题意，对于空或" . "都不用管，然后用栈模拟，如果不是"..",那么直接入栈，是".."的话，弹出栈顶的字符串;
class Solution {
public:
vector<string> get(string p,char ch){
vector<string> ans ;
string cur ;
for(char c : p){
if(c == ch){
ans.push_back(cur);
cur.clear();
}else{
cur += c ;
}
}
ans.push_back(cur);
return ans ;
}
string simplifyPath(string path) {
vector<string> p = get(path,'/');
vector<string> stk ;
for(string s : p){
if(s==".."){
if(!stk.empty())
stk.pop_back();
}else if(!s.empty() && s!="."){
stk.push_back(s);
}
}
string ans ;
if(stk.empty()){
ans = "/";
}else{
for(string s : stk){
ans += "/" + s ;
}
}
return ans ;
}
};155 . 最小栈
用一个栈来模拟正常的操作，用一个递减的栈来维护栈顶为当前序列的最小元素;
详情请看代码 :
class MinStack {
public:
stack<int> mi,st;
MinStack() {
mi.push(INT_MAX) ;
}
void push(int val) {
st.push(val) ;
mi.push(min(val,mi.top()));
}
void pop() {
st.pop();
mi.pop();
}
int top() {
return st.top() ;
}
int getMin() {
return mi.top() ;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/150 . 逆波兰表达式求值
栈的典型例题，如果是运算符，就取出栈顶两位元素进行运算，然后将结果压入栈中，如果是数字，直接压入栈中，最后返回栈顶元素即为运算结果 ;
typedef long long LL ;
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<LL> st ;
for(string s : tokens){
if(s=="+" ||s=="-" ||s=="*" ||s=="/"){
LL x = st.top();
st.pop() ;
LL y = st.top();
st.pop();
if(s=="+") st.push(x+y);
else if(s=="-") st.push(y-x);
else if(s=="*") st.push(1LL * y * x);
else st.push(y / x);
}else{
st.push(stoll(s));
}
}
return st.top() ;
}
};224 . 基本计算器
直接用栈模拟 ;
class Solution {
public:
void replace(string& s){
int pos = s.find(" ");
while (pos != -1) {
s.replace(pos, 1, "");
pos = s.find(" ");
}
}
int calculate(string s) {
// 存放所有的数字
stack<int> nums;
// 为了防止第一个数为负数，先往 nums 加个 0
nums.push(0);
// 将所有的空格去掉
replace(s);
// 存放所有的操作，包括 +/-
stack<char> ops;
int n = s.size();
for(int i = 0; i < n; i++) {
char c = s[i];
if(c == '(')
ops.push(c);
else if(c == ')') {
// 计算到最近一个左括号为止
while(!ops.empty()) {
char op = ops.top();
if(op != '(')
calc(nums, ops);
else {
ops.pop();
break;
}
}
}
else {
if(isdigit(c)) {
int cur_num = 0;
int j = i;
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while(j <n && isdigit(s[j]))
cur_num = cur_num*10 + (s[j++] - '0');
// 注意上面的计算一定要有括号，否则有可能会溢出
nums.push(cur_num);
i = j-1;
}
else {
if (i > 0 && (s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-')) {
nums.push(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
while(!ops.empty() && ops.top() != '(')
calc(nums, ops);
ops.push(c);
}
}
}
while(!ops.empty())
calc(nums, ops);
return nums.top();
}
void calc(stack<int> &nums, stack<char> &ops) {
if(nums.size() < 2 || ops.empty())
return;
int b = nums.top(); nums.pop();
int a = nums.top(); nums.pop();
char op = ops.top(); ops.pop();
nums.push(op == '+' ? a+b : a-b);
}
};