当前位置: 首页 > news >正文

【算法训练营Day10】栈与队列part2

文章目录

  • 逆波兰表达式求值
  • 滑动窗口最大值
  • 前 K 个高频元素

逆波兰表达式求值

题目链接:150. 逆波兰表达式求值

解题逻辑:

  • 遍历字符串数组
  • 遇到数字就压栈
  • 遇到符号就把栈顶的两个元素弹出来进行运算,算完之后再把结果压栈
  • 如此循环往复直到遍历完整个字符串数组

代码如下:

class Solution {public int evalRPN(String[] tokens) {Deque<String> box = new ArrayDeque<>();for(String s : tokens) {if(s.equals("+")) box.push(Integer.toString(Integer.parseInt(box.pop()) + Integer.parseInt(box.pop()))); else if (s.equals("-")) box.push(Integer.toString( - (Integer.parseInt(box.pop()) - Integer.parseInt(box.pop())))); else if (s.equals("*")) box.push(Integer.toString(Integer.parseInt(box.pop()) * Integer.parseInt(box.pop()))); else if (s.equals("/")) {int a = Integer.parseInt(box.pop());int b = Integer.parseInt(box.pop());box.push(Integer.toString( b / a )); }else box.push(s);}return Integer.parseInt(box.pop());}
}

滑动窗口最大值

题目链接:239. 滑动窗口最大值

解题思路:

这道题我最先开始想的是使用优先级队列,但是优先级队列无法维护动态窗口的增添元素(因为优先级队列的底层是堆,添加进去就已经排好序了)。为了解决本题,我们应该使用另一种数据结构 – 单调队列。

这两种队列的概念如下:

单调队列

  • 单调队列是一种特殊的队列,队列中的元素保持单调递增或递减。它的特点是:
  • 元素有序:队列中的元素始终保持单调性。
  • 高效操作:插入和删除操作都能保持队列的单调性,时间复杂度为 O (1)。
  • 滑动窗口问题:常用于解决滑动窗口的最大值或最小值问题。

优先级队列

  • 优先级队列是一种抽象数据类型,元素按照优先级排序,优先级高的元素先出队。它的特点是:
  • 元素无序:元素按照优先级排序,但不保证完全有序。
  • 高效操作:插入和删除操作的时间复杂度为 O (log n)。
  • 贪心算法:常用于解决最优化问题,如 Dijkstra 算法。

那么我们如何保持单调队列的单调呢?

其核心就在于两个操作,例如现在我们需要维护一个单调递减的队列:

  • add操作:我们只需要在push一个新元素进去的时候比较队尾的元素是否比队尾新进的元素要小(或等于),如果小(或等于)的话就入队,如果大的话就剔除队尾元素,直到队尾元素比新进元素要小
  • remove操作:如果要删除的元素是最大元素(也就是队头元素),那么就执行remove操作,否则不进行操作

解题逻辑如下:

  • 初始化两个指针代表窗口的两侧
  • 初始化一个单调队列
  • 将k个元素加入到队列中
  • 随着窗口移动,根据指针进行元素的添加与剔除(如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作),并且将每次队头元素存储到数组中
  • 返回数组

代码如下:

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] result = new int[nums.length - k + 1];int left = 0;int right = k - 1;MonotonousQueue queue = new MonotonousQueue();for(int i = 0;i < k;i++) queue.add(nums[i]);int pointer = 0; while(right < nums.length) {result[pointer++] = queue.element();if(nums[left] == queue.element()) queue.remove();left++;right++;if(right < nums.length) queue.add(nums[right]);}return result;}class MonotonousQueue {Deque<Integer> myQueue = new ArrayDeque<>();public void add(Integer item){while(!myQueue.isEmpty() && myQueue.peekLast() < item) myQueue.pollLast(); myQueue.add(item);}public Integer remove(){return myQueue.remove();}public Integer element(){return myQueue.element();}}
}

前 K 个高频元素

题目链接:347. 前 K 个高频元素

解题思路:

  • 使用hashmap进行计数
  • 定义一个对象,用于存储元素以及次数
  • 遍历hashmap创建对象放入到优先级队列中
  • 从优先级队列中弹出k个元素形成数组所谓结果

代码如下:

class Solution {public int[] topKFrequent(int[] nums, int k) {PriorityQueue<CountHelper> pq = new PriorityQueue<>(Comparator.comparingInt(CountHelper::getCount).reversed());Map<Integer,Integer> countMap =  new HashMap<>();for(int i = 0;i < nums.length;i++) countMap.put(nums[i],countMap.getOrDefault(nums[i],0) + 1);for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {Integer key = entry.getKey();Integer value = entry.getValue();pq.add(new CountHelper(key,value));}int[] result = new int[k];int pointer = 0;while(pointer < k) result[pointer++] = pq.remove().getNum();return result;}class CountHelper {private int num;private int count;public CountHelper(int n, int c){num = n;count = c;}public int getNum(){return num;}public int getCount(){return count;}public void setNum(int n){num = n;}public void setCount(int c){count = c;}}
}
http://www.lryc.cn/news/583488.html

相关文章:

  • 微算法科技从量子比特到多级系统,Qudits技术革新引领量子计算新时代
  • 三码合一:OneCode注解驱动的新时代编码范式
  • C++学习笔记三
  • 类模板的语法
  • Python标准库:时间与随机数全解析
  • 【面试精讲】I2C 子系统核心结构与常见问题深度解析
  • MySQL 09 普通索引和唯一索引
  • 汽车功能安全-软件单元验证 (Software Unit Verification)【用例导出方法、输出物】8
  • 装配式建筑4.0:当房子像汽车一样被“智造”
  • 解锁DevOps潜力:如何选择合适的CI/CD工作流工具
  • 北京-4年功能测试2年空窗-报培训班学测开-第四十六天
  • Spring AI Alibaba Graph使用案例多节点并行执行
  • Webpack、Vite配置技巧与CI/CD流程搭建全解析
  • CentOS7系统部署Node.js LTS V18.16.0
  • 【自动驾驶】经典LSS算法解析——深度估计
  • 佰力博科技与您浅谈低温介电材料特性及应用分析
  • 科技对生态保育的影响?
  • Oracle存储过程导出数据到Excel:全面实现方案详解
  • 专题一_双指针_三数之和
  • 【基础算法】贪心 (四) :区间问题
  • WIFI协议全解析04:从芯片角度看WiFi协议:ESP32/8266 支持了哪些?
  • SQL 视图与事务知识点详解及练习题
  • ARM汇编编程(AArch64架构)课程 - 第7章:SIMD与浮点运算
  • STIDGCN(时空交互动态图卷积网络)的原理,包括其核心模块的设计思路和工作机制 交通预测是智能交通系统中的一个重要任务
  • python+vue的企业产品订单管理系统
  • Redis:分组与设备在 Redis 中缓存存储设计
  • Redis-哨兵机制doctor环境搭建
  • CSS基础选择器、文本属性、引入方式及Chorme调试工具
  • Linux 测开:日志分析 + 定位 Bug
  • 【图像处理基石】如何检测到画面中的ppt并对其进行增强?