Day9：逆波兰表达式求值150 滑动窗口最大值239 前 K 个高频元素347

2024/10/24 22:21:17 来源：https://blog.csdn.net/vpurple_/article/details/140149443 浏览: 次关键词：Day9：逆波兰表达式求值150 滑动窗口最大值239 前 K 个高频元素347

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

class Solution {
public:int evalRPN(vector<string>& tokens) {//使用栈来消除stack<string> st;for(int i=0;i<tokens.size();i++){if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){string op=tokens[i];int num1=atoi(st.top().c_str());st.pop();int num2=atoi(st.top().c_str());st.pop();int res=0;if(tokens[i]=="+"){res=num1+num2;}else if(tokens[i]=="-"){res=num2-num1;}else if(tokens[i]=="*"){res=num1*num2;}else{res=num2/num1;}string ress=to_string(res);st.push(ress);}else{st.push(tokens[i]);}}return atoi(st.top().c_str());}
};

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

class Solution {
public:class myqueue // 单调队列最前面的就是最大的数字{deque<int> que;public:void push(int val) // 有序单调序列，加入元素与最后一个最小的元素比较，要是比他小正常插入，如果比他大就pop出去{while (!que.empty() && val > que.back()) {que.pop_back();}que.push_back(val);}void pop(int val) { // 直到队列中的首部的元素等于要弹出的区间元素，才弹出if (!que.empty() && val == que.front()) {que.pop_front();}}int front() { return que.front(); }bool empty() { return que.empty(); }};vector<int> maxSlidingWindow(vector<int>& nums, int k) {// 单调队列myqueue que;vector<int> res;// 滑动窗口int left = 0;int right = left; // 左闭右闭while (right <= nums.size()) {while (right < k) {que.push(nums[right]);right++;}res.push_back(que.front());if (!que.empty()) {que.pop(nums[left]);}left++;if (right < nums.size()) {que.push(nums[right]);}right++;}return res;}
};

题目347. 前 K 个高频元素 - 力扣（LeetCode）

class Solution {
public:// 自定义比较class Compar {public:bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) {return p1.second > p2.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 先进行出现频次的记录到map中,然后用优先级队列进行符合条件的k个排序，要用小根堆进行排序unordered_map<int, int> map;for (auto e : nums) {map[e]++;}// 优先级队列// 优先级队列默认大根堆，每次pop出的都是当前优先级队列中最大的那个元素，如果要改成小根堆，自定义类型的排序需要传仿函数/*template <class T, //存储元素类型class Container = vector<T>,//优先队列底层使用的存储结构class Compare = less<typename Container::value_type>>//定义优先队列中元素的比较方式的类 class priority_queue; */priority_queue<pair<int, int>, vector<pair<int, int>>, Compar> pri_que;for (auto& e : map) {if (pri_que.size() > k) {pri_que.pop();}pri_que.push(e);}if (pri_que.size() > k) {pri_que.pop();}vector<int> vec(k, 0);for (int i = vec.size() - 1; i >= 0; i--) {vec[i] = pri_que.top().first;pri_que.pop();}return vec;}
};