代码随想录算法训练营Day-11 | 150. 逆波兰表达式求值、239. 滑动窗口最大值、 347.前 K 个高频元素-北京尧图网络

150. 逆波兰表达式求值文章链接完成情况看完逆波兰表达式原理自己想出了思路15minAC思路遍历字符串遇到加减乘除就从栈里弹出两个值进行计算再进入栈是数字就继续入栈最后弹出栈顶就是最后计算结果注意事项stoi()-转换为int、stol()-转换为long、stoll()-转换为long long、stoul()-转换为unsigned long、stoull()-转换为unsigned long longint evalRPN(vectorstring tokens) { stacklong long st; for(auto i:tokens){ if(i||i-||i*||i/){ int b st.top(); st.pop(); int a st.top(); st.pop(); if(i) st.push(ab); else if(i-) st.push(a-b); else if(i*) st.push(a*b); else if(i/) st.push(a/b); }else{ st.push(stoll(i)); } } return st.top(); }239. 滑动窗口最大值文章链接完成情况看文章视频花费约1hAC本题学习了使用双向队列构造新功能列其常用函数为push_front(); pop_front(); push_back(); pop_back(); front(); back()思路本题构造了新功能列列包含pop、push和front函数其中push规则为如果push值大于队尾元素删除队尾直到push值前面没有比它大的值该操作可以实现队列元素始终降序排放pop函数规则为判断队头是否是要删除的值判断好之后再删因为push操作会提前删掉本来就应该删的元素front函数无处理就是弹出队头但由于队列元素降序排放所以队头就是最大值题目函数中执行先push前k个元素返回队头得到第一个结果放入result数组-从k开始遍历数组每次执行pop窗口左边元素push窗口右边元素返回front。class MyQueue{ public: dequeint qe; void pop(int v){ if(!qe.empty() vqe.front()) qe.pop_front(); //因为队列降序排列所以比队头小的元素已经提前删掉所以在删除元素时要判断是不是真的要pop队头若要删除的元素队头则确实应该删掉再删如果不等于队头则说明已经删过了则无需处理 } void push(int v){ while(!qe.empty() vqe.back()) qe.pop_back();//保证新进元素前面没有比自己大的元素也就是队列元素降序排列 qe.push_back(v);//判断完前面没有比自己大的元素之后在加入此元素 } int front(){ return qe.front();//由于队列降序排列则直接返回队头即可 } }; public: vectorint maxSlidingWindow(vectorint nums, int k) { MyQueue qe; vectorint result; for(int i0;ik;i){ qe.push(nums[i]); } result.push_back(qe.front()); for(int i k;inums.size();i){ qe.pop(nums[i-k]);//每次滑动时删除窗口最左边值 qe.push(nums[i]);//加上窗口新值 result.push_back(qe.front()); } return result; }347.前 K 个高频元素文章链接完成情况看视频文章花费约45min本题使用了哈希表map用来存放数字以及出现频率然后使用小顶堆进行前k个高频元素存放思路遍历数组mp[数字]达到记录数字及其出现频率的作用然后遍历mp元素依次进入堆(优先级队列)中当堆元素超过k时就弹出一次(需要弹出最小值所以用小顶堆)最后将堆元素倒序放入数组result中注意事项-堆定义class mycomparison{ public: bool operator()(const pairint,int l,const pairint,int r){ return l.secondr.second;//如果左大于右返回true 该方式实现的是小顶堆 } } priority_queuepairint,int,vectorpairint,int,mycomparison pri_que; //中第一个数元素类型第二个是以什么容器存放元素一般默认就是vector固定写法最后是比较方法实现大顶堆还是小顶堆依据pair的第一还是第二部分排序class Solution { public: class mycomparison{ public: bool operator()(const pairint,int l,const pairint,int r){ return l.secondr.second; } }; vectorint topKFrequent(vectorint nums, int k) { unordered_mapint,int myMap; for(int i:nums) myMap[i]; priority_queuepairint,int,vectorpairint,int,mycomparison pri_que; for(auto pr:myMap){ pri_que.push(pr); if(pri_que.size()k) pri_que.pop(); } vectorint result(k); for(int i k-1;i0;i--){ result[i] pri_que.top().first; pri_que.pop(); } return result; } };总结栈和队可以互相实现栈很适合解决匹配问题比如左右运算符、相邻元素相同删除、逆波兰运算问题双向队列的前后获取、push和弹出很适合解决滑动窗口维护最大值的问题堆(优先级队列)适合解决对无序数据取k个最值的问题。

代码随想录算法训练营Day-11 | 150. 逆波兰表达式求值、239. 滑动窗口最大值、 347.前 K 个高频元素

相关推荐

推荐系统特征工程管线的自动化：从手写 SQL 到 Feature Store 的工程演进与一致性保障

Redis的string类及基础指令

广告 CTR 预估模型的 GPU 推理优化：大规模稀疏特征 Embedding 的显存管理与混合精度计算

更多资讯

温州电工证报考时间怎么安排？郑州报考避坑指南帮你理清流程

技工学校电工证考证不知道去哪报名怕被中介坑的良心建议

高压电工证含金量高怎么考？考前押题帮你搞定

廊坊大城电工证怎么考？全国通用的证书怎么用？

电工证台州复审延期怎么办理

南昌去哪里考电工证好怎么报名电工证实操考试心里没底怕挂科怎么办

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？