代码随想录 第11天

150 逆波兰表达式求值

class Solution { public: int evalRPN(vector<string>& tokens) { int a; int b; int result; stack<int> s; for(int i = 0;i < tokens.size();i++){ if(tokens[i] == "+"){ b = s.top(); s.pop(); a = s.top(); s.pop(); result = a + b; s.push(result); }else if(tokens[i] == "-"){ b = s.top(); s.pop(); a = s.top(); s.pop(); result = a - b; s.push(result); }else if(tokens[i] == "*"){ b = s.top(); s.pop(); a = s.top(); s.pop(); result = a * b; s.push(result); }else if(tokens[i] == "/"){ b = s.top(); s.pop(); a = s.top(); s.pop(); result = a / b; s.push(result); }else{ int num = stoi(tokens[i]); s.push(num); } } result = s.top(); s.pop(); return result; } };

239 滑动窗口最大值

没看懂过程，再过一遍

class Solution { public: class Myqueue{ public: deque<int> que; void pop(int val){ if(!que.empty() && val == que.front()){ que.pop_front(); } } void push(int val){ while(!que.empty() && val > que.back()){ que.pop_back(); } que.push_back(val); } int getmax(){ return que.front(); } }; vector<int> maxSlidingWindow(vector<int>& nums, int k) { Myqueue que; vector<int> result; for(int i = 0;i < k;i++){ que.push(nums[i]); } result.push_back(que.getmax()); for(int i = k;i < nums.size();i++){ que.pop(nums[i - k]); que.push(nums[i]); result.push_back(que.getmax()); } return result; } };

347 前k个高频元素

需要复习，重点了解堆的性质和定义

class Solution { public: class mycomparison{ public: bool operator()(const pair<int,int>& lhs,const pair<int,int>& rhs){ return lhs.second > rhs.second; } }; vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> map; for(int i = 0;i < nums.size();i++){ map[nums[i]]++; } priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> pri_que; for(unordered_map<int,int>::iterator it = map.begin();it != map.end();it++){ pri_que.push(*it); if(pri_que.size() > k){ pri_que.pop(); } } vector<int> result(k); for(int i = 0;i < k;i++){ result[i] = pri_que.top().first; pri_que.pop(); } return result; } };