面试经典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);
    }
};