成都网站开发定制/新闻网最新消息

前言

 这几个题目都是栈和队列的高频面试题目，主要是考察思路和coding能力，在前面几道题目的基础上进行延伸的。同时还有优先级队列和双端队列的用法

题目链接

150. 逆波兰表达式求值 - 力扣（LeetCode） 

239. 滑动窗口最大值 - 力扣（LeetCode） 

一、逆波兰表达式求值

 说点白话：我们好奇计算器是怎么处理运算的不？我们会在编译原理这门课程中学到，逆波兰表达式，俗称后缀表达式，具体来说就是，计算机并不知道计算逻辑的优先级（括号的优先级），但是他能找到一个括号最先匹配的，这样我们就会花了很大的时间去遍历查询括号，还有运算符的优先级问题，我们都需要考虑，有什么方法可以跳过这些呢？就是后缀表达式，我们让符号去匹配他的计算数值，同时利用栈来对符号的优先级进行排序，这样两个问题都能得到解决，足以可见逆波兰表达式（后缀表达式的腻害之处）。

tips:注意除法运算和减法的顺序第一次写错了，哈哈哈 

    int evalRPN(vector<string>& tokens) {stack<long long> st;for(int i=0;i<tokens.size();i++){if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){long long nums1=st.top();st.pop();long long nums2=st.top();st.pop();if(tokens[i]=="+")st.push(nums1+nums2);if(tokens[i]=="-")st.push(nums2-nums1);if(tokens[i]=="*")st.push(nums1*nums2);if(tokens[i]=="/")st.push(nums2/nums1);}else{st.push(stoll(tokens[i]));}}return st.top();}
};

二、滑动窗口求最大值

 思路：借助deque双端队列去实现这个题目比较简单一点，同时保持队列是递减的就行。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {if(nums.size() == 0 || k == 0) return {};deque<int> deque;vector<int> res(nums.size() - k + 1);for(int j = 0, i = 1 - k; j < nums.size(); i++, j++) {// 删除 deque 中对应的 nums[i-1]if(i > 0 && deque.front() == nums[i - 1])deque.pop_front();// 保持 deque 递减while(!deque.empty() && deque.back() < nums[j])deque.pop_back();deque.push_back(nums[j]);if(i >= 0)res[i] = deque.front();}return res;}

三、前K个高频元素的值

 使用优先级队列，哈希表统计数据，压入数据，然后遍历出数据。

 

unordered_map<int, int> hmap;priority_queue<pair<int,int>> pq;vector<int> res;for (int i : nums)hmap[i]++;   //使用哈希表统计个数for (auto iter : hmap)pq.emplace(iter.second,iter.first);   //压入优先级队列for (int i = 0; i < k; i++)   //遍历k次找到前k个最大次数对应的值{ res.push_back(pq.top().second);pq.pop();}return res;