代码随想录 | 刷题-栈与队列2

发表于 分类于

150. 逆波兰表达式求值

细节很重要，注意数字可能有多位，有负数；数学表达式操作前后数字顺序影响结果 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(string ss: tokens){
            char ssEnd = ss[ss.size()-1];
            if(ssEnd <= '9' && ssEnd >= '0'){
                int val = 0;
                int times = 1;
                while(!ss.empty()){
                    if(ss[ss.size()-1] == '-'){
                        val = 0 - val;
                    }else{
                        int n = (ss[ss.size()-1] - '0');
                        val += n * times;
                        times = times * 10;
                    }
                    ss.pop_back();
                }
                st.push(val);
            }else{
                int n1 = st.top();
                st.pop();
                int n2 = st.top();
                st.pop();
                int opVal = 0;
                if(ssEnd == '+'){
                    opVal = n2 + n1;
                }else if(ssEnd == '-'){
                    opVal = n2 - n1;
                }else if(ssEnd == '*'){
                    opVal = n2 * n1;
                }else{
                    opVal = n2 / n1;
                }
                st.push(opVal);
            }
        }
        return st.top();
    }
};

239. 滑动窗口最大值

注意单调栈判断条件；top查询应在代码逻辑最后 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MyQueue{
private:
    deque<int> dq;
public:
    MyQueue(){}
    void push(int val){
        while(!dq.empty() && val > dq.back()){
            dq.pop_back();
        }
        dq.push_back(val);
    }
    void pop(int val){
        if(!dq.empty() && dq.front() == val){
            dq.pop_front();
        }
    }
    int top(){
        return dq.front();
    }
};
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue mq;
        vector<int> maxWin;
        for(int i = 0; i<nums.size();i++){
            mq.push(nums[i]);
            if(i>(k-1)){
                mq.pop(nums[i-k]);
            }
            if(i>=(k-1)){
                maxWin.push_back(mq.top());
            }
        }
        return maxWin;
    }
};

347.前 K 个高频元素

注意operator()一定要是public的，因为小顶堆每次弹出堆顶最小元素所以最后要逆序填入vector
为什么priority_queue第三个参数要传入一个类？priority_queue 只需要知道这个类的类型（模板参数），它会自己构造一个比较器对象myComp comp 来比较元素 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    class myComp{
        public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>&rhs){
            return lhs.second > rhs.second;// 插入元素判断为true时走入叶子节点，所以是小顶堆
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for(int n:nums){
            mp[n]++;
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>, myComp> priQue;
        for(unordered_map<int, int>::iterator p = mp.begin();p!=mp.end();p++){
            priQue.push(*p);
            if(priQue.size()>k)priQue.pop();
        }
        vector<int> res(k);
        for(int i = k-1;i>=0;i--){
            res[i] = priQue.top().first;
            priQue.pop();
        }
        return res;
    }
};