代码随想录—day11—栈与队列(part2)

题例:150. 逆波兰表达式求值 - 力扣LeetCode给你一个字符串数组tokens表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意有效的算符为、-、*和/。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是向零截断。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用32 位整数表示。示例 1输入tokens [2,1,,3,*]输出9解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9示例 2输入tokens [4,13,5,/,]输出6解释该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6示例 3输入tokens [10,6,9,3,,-11,*,/,*,17,,5,]输出22解释该算式转化为常见的中缀算术表达式为 ((10 * (6 / ((9 3) * -11))) 17) 5 ((10 * (6 / (12 * -11))) 17) 5 ((10 * (6 / -132)) 17) 5 ((10 * 0) 17) 5 (0 17) 5 17 5 22提示1 tokens.length 104tokens[i]是一个算符、-、*或/或是在范围[-200, 200]内的一个整数class Solution { public: int evalRPN(vectorstring tokens) { stackintst; for(string str:tokens){ if(str||str-||str*||str/){ int num1st.top(); st.pop(); int num2st.top(); st.pop(); if(str){st.push(num1num2);} if(str-){st.push(num2-num1);} if(str*){st.push(num1*num2);} if(str/){st.push(num2/num1);} }else{ st.push(stoll(str)); } } int resultst.top(); st.pop(); return result; } };感觉审题挺难的但实际上就只需要遍历tokens遍历到数字就把元素压入栈中遍历到运算符号就让原栈顶和新栈顶进行对应的运算再把两个元素弹出压入运算结果就可以了题例:239. 滑动窗口最大值 - 力扣LeetCode给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例 1输入nums [1,3,-1,-3,5,3,6,7], k 3输出[3,3,5,5,6,7]解释滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7示例 2输入nums [1], k 1输出[1]提示1 nums.length 105-104 nums[i] 1041 k nums.lengthclass Solution { private: class Myqueue{ public: dequeintque; void pop(int value){ if(!que.empty()que.front()value){ que.pop_front(); } } void push(int value){ while(!que.empty()valueque.back()){ que.pop_back(); } que.push_back(value); } int front(){ return que.front(); } }; public: vectorint maxSlidingWindow(vectorint nums, int k) { Myqueue que; vectorintresult; for(int i0;ik;i){ que.push(nums[i]); } result.push_back(que.front()); for(int ik;inums.size();i) { que.pop(nums[i-k]); que.push(nums[i]); result.push_back(que.front()); } return result; } };引入单调队列Myqueue保证其首部储存的一直为窗口中的最大元素pop掉已经离开窗口的最大元素题例347. 前 K 个高频元素 - 力扣LeetCode给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。示例 1输入nums [1,1,1,2,2,3], k 2输出[1,2]示例 2输入nums [1], k 1输出[1]示例 3输入nums [1,2,1,2,1,2,3,1,3,2], k 2输出[1,2]提示1 nums.length 105-104 nums[i] 104k的取值范围是[1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前k个高频元素的集合是唯一的进阶你所设计算法的时间复杂度必须优于O(n log n)其中n是数组大小。class Solution { public: // 小顶堆 class mycomparison { public: bool operator()(const pairint, int lhs, const pairint, int rhs) { return lhs.second rhs.second; } }; vectorint topKFrequent(vectorint nums, int k) { // 要统计元素出现频率 unordered_mapint, int map; // mapnums[i],对应出现的次数 for (int i 0; i nums.size(); i) { map[nums[i]]; } // 对频率排序 // 定义一个小顶堆大小为k priority_queuepairint, int, vectorpairint, int, mycomparison pri_que; // 用固定大小为k的小顶堆扫面所有频率的数值 for (unordered_mapint, int::iterator it map.begin(); it ! map.end(); it) { pri_que.push(*it); if (pri_que.size() k) { // 如果堆的大小大于了K则队列弹出保证堆的大小一直为k pri_que.pop(); } } // 找出前K个高频元素因为小顶堆先弹出的是最小的所以倒序来输出到数组 vectorint result(k); for (int i k - 1; i 0; i--) { result[i] pri_que.top().first; pri_que.pop(); } return result; } };这里还没学二叉树相关知识题就先欠着了......