代码随想录day11 150. 逆波兰表达式求值 、 239. 滑动窗口最大值 、 347.前 K 个高频元素
代码随想录day11 150. 逆波兰表达式求值 、 239. 滑动窗口最大值 、 347.前 K 个高频元素
150. 逆波兰表达式求值
栈的应用 学数据结构时候写过,注意要使用long long
class Solution {
public:
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 right = st.top();
st.pop();
long long left = st.top();
st.pop();
if (tokens[i] == "+") st.push(left + right);
if (tokens[i] == "-") st.push(left - right);
if (tokens[i] == "*") st.push(left * right);
if (tokens[i] == "/") st.push(left / right);
} else {
st.push(stoll(tokens[i]));
}
}
return st.top();
}
};
239. 滑动窗口最大值
这题是看卡哥视频的,但我不是很习惯pop的写法,因为我觉得pop就是单纯的弹出元素,而这里实际涉及了外界的下标,因为左下标-1元素值等于首元素,所以才觉得要弹出元素,属于和外界逻辑相关,而不是和队列本意相关,所以我就放到了函数体内,然后单调队列,其实就是对deque的入队作了限制,入队元素如果大于尾元素,则要不断弹出
class Solution {
public:
void push(deque<int> &que, int val) {
while (!que.empty() && val > que.back()) {
que.pop_back();
}
que.push_back(val);
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> que;
vector<int> res;
for (int i = 0; i < k; i++) {
push(que, nums[i]);
}
res.push_back(que.front());
for (int i = k; i < nums.size(); i++) {
if (!que.empty() && que.front() == nums[i - k]) {
que.pop_front();
}
push(que, nums[i]);
res.push_back(que.front());
}
return res;
}
};
347. 前 K 个高频元素
想法和卡哥差不多都是用map统计然后放入优先队列进行排序,但我本来想的是用大顶堆,最后弹出两个频率最大的元素,但后来发现这复杂度是O(nlogn),所以不符合要求
几个注意的点是priority_que的模板参数 第一个是元素类型,第二个是容器类型,第三个类(重写了仿函数,或者如果元素是自定义类可以重写operator大小比较),第三个参数得是类,我写lamda直接报错了
一个小诀窍就是vector可以正序或者倒叙写入就可以把实现想要的顺序
class Solution {
public:
struct cmp {
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) {
unordered_map<int,int> countMap;
for (auto &ele : nums) {
countMap[ele]++;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> priQue;
for (auto &ele : countMap) {
priQue.push(ele);
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;
}
};
原文地址:https://blog.csdn.net/weixin_45461296/article/details/140405475
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!