算法训练营Day11

20. 有效的括号

题目链接：https://leetcode.cn/problems/valid-parentheses/
文章讲解：https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html

考察点：栈和队列

可以不用stack, string本身就可以模拟栈。unordered_map也可以去掉，push字符串的时候做个简单的判断即可。

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false;
        unordered_map<char, char> pair;
        stack<char> st;
        pair = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        for (auto c: s) {
            if (pair.find(c) == pair.end()) {
                st.push(c);
            } else {
                if (st.empty() || st.top() != pair[c]) {
                    return false;
                } else {
                    st.pop();
                }
            }
        }
        return st.empty();
    }
};

1047. 删除字符串中的所有相邻重复项

题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
文章讲解：https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html

考察点：栈和队列

注意判断栈非空。

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        for (char c: s) {
            if (st.empty() || st.top() != c) {
                st.push(c);
            } else {
                st.pop();
            }
        }
        string res;
        res.resize(st.size());
        for (int i = (int)st.size() - 1; i >= 0; i--) {
            res[i] = st.top();
            st.pop();
        }
        return res;
    }
};

150. 逆波兰表达式求值

题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/
文章讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html

考察点：栈和队列

理解题意之后很简单。

class Solution {
public:
     void get_ab(stack<long long> &st, long long &a, long long &b) {
        b = st.top();
        st.pop();
        a = st.top();
        st.pop();
    }
    int evalRPN(vector<string>& tokens) {
        stack<long long> st; 
        for(auto s:tokens){
            long long a, b;
            if(s=="+"){
                this->get_ab(st, a, b);
                st.push(a + b);
            }else if(s=="-"){
                this->get_ab(st, a, b);
                st.push(a-b);
            }else if(s=="*"){
                this->get_ab(st, a, b);
                st.push(a*b);
            }else if(s=="/"){
                this->get_ab(st, a, b);
                st.push(a/b);
            }else{
                st.push(stoll(s));
            }
        }
        return st.top();
    }
};