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

本文主要是介绍day12--150. 逆波兰表达式求值+239. 滑动窗口最大值+ 347. 前 K 个高频元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、150. 逆波兰表达式求值

题目链接:https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
文章讲解:https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
视频讲解:https://www.bilibili.com/video/BV1kd4y1o7on

1.1 初见思路

  1. 就是用栈,碰到符号,就弹出最上面的2个元素,计算完后吧结果再push进栈

1.2 具体实现

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> deque = new LinkedList();for (int i = 0; i < tokens.length; i++) {String token = tokens[i];if(token.equals("+")){int num2 = deque.pop();int num1 = deque.pop();deque.push(num1+num2);}else if(token.equals("-")){int num2 = deque.pop();int num1 = deque.pop();deque.push(num1-num2);}else if(token.equals("*")){int num2 = deque.pop();int num1 = deque.pop();deque.push(num1*num2);}else if(token.equals("/")){int num2 = deque.pop();int num1 = deque.pop();deque.push((num1/num2));}else{deque.push(Integer.parseInt(token));}}return deque.pop();}
}

1.3 重难点

二、 239. 滑动窗口最大值

题目链接:https://leetcode.cn/problems/sliding-window-maximum/
文章讲解:https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
视频讲解:https://www.bilibili.com/video/BV1XS4y1p7qj

2.1 初见思路

  1. 使用双端队列,得知道移动时,应该去除哪个值,增加哪个值
  2. 记录当前窗口内最大值,若移除了最大值,则重新比一遍窗口内的最大值
  3. 若未移除最大值,比较新增值和最大值,更新最大值

2.2 具体实现

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length-k+1];int maxNum=Integer.MIN_VALUE;LinkedList<Integer> linkedList = new LinkedList<>();for(int i=0;i<k;i++){linkedList.addLast(nums[i]);maxNum=Math.max(nums[i],maxNum);}res[0]=maxNum;for(int i=k;i<nums.length;i++){int outNum = linkedList.peekFirst();//若未移除最大值,比较新增值和最大值if(outNum!=maxNum){maxNum=maxNum<nums[i]?nums[i]:maxNum;linkedList.pollFirst();linkedList.addLast(nums[i]);}else{linkedList.pollFirst();linkedList.addLast(nums[i]);//重新比一遍窗口内的最大值maxNum = getMax(linkedList);}res[i-k+1]=maxNum;}return res;}public int getMax(LinkedList<Integer> list){int max=Integer.MIN_VALUE;for (Integer integer : list) {max=Math.max(max,integer);}return max;}
}
上面的实现方式会在k很大的时候超时,因为getMax()方法会遍历,所以会超时;
得使用双端队列构建出有序队列
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {ArrayDeque<Integer> deque = new ArrayDeque<>();int n = nums.length;int[] res = new int[n - k + 1];int idx = 0;for(int i = 0; i < n; i++) {// 根据题意,i为nums下标,是要在[i - k + 1, i] 中选到最大值,只需要保证两点// 1.队列头结点需要在[i - k + 1, i]范围内,不符合则要弹出while(!deque.isEmpty() && deque.peek() < i - k + 1){deque.poll();}// 2.既然是单调,就要保证每次放进去的数字要比末尾的都大,否则也弹出while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();}deque.offer(i);// 因为单调,当i增长到符合第一个k范围的时候,每滑动一步都将队列头节点放入结果就行了if(i >= k - 1){res[idx++] = nums[deque.peek()];}}return res;}
}

2.3 重难点

  • 要会使用双端队列构建出有序队列

三、 347. 前 K 个高频元素

题目链接:https://leetcode.cn/problems/top-k-frequent-elements/description/
文章讲解:https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解:https://www.bilibili.com/video/BV1Xg41167Lz

3.1 初见思路

3.2 具体实现

class Solution {public int[] topKFrequent(int[] nums, int k) {HashMap<Integer,Integer> map = new HashMap<>();for(int num:nums){map.put(num,map.getOrDefault(num,0)+1);}PriorityQueue<Integer> queue = new PriorityQueue<>((p1,p2)->{return map.get(p1)-map.get(p2);});for(Map.Entry<Integer,Integer> entry:map.entrySet()){//queue不满的时候直接插入if(queue.size()<k){queue.add(entry.getKey());}//queue满了就需要移除后再插入else if(entry.getValue()>map.get(queue.peek())){queue.remove();queue.add(entry.getKey());}}int[] res = new int[queue.size()];int index=0;for(int i=k-1;i>=0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多res[i] = queue.poll();}return res;}
}

在这里插入图片描述

这篇关于day12--150. 逆波兰表达式求值+239. 滑动窗口最大值+ 347. 前 K 个高频元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1070489

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

SpringBoot @Scheduled Cron表达式使用方式

《SpringBoot@ScheduledCron表达式使用方式》:本文主要介绍SpringBoot@ScheduledCron表达式使用方式,具有很好的参考价值,希望对大家有所帮助,如有... 目录Cron 表达式详解1. 表达式格式‌2. 特殊字符解析3. 常用示例‌4. 重点规则5. 动态与复杂场景‌

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Spring Boot 集成 Quartz 使用Cron 表达式实现定时任务

《SpringBoot集成Quartz使用Cron表达式实现定时任务》本文介绍了如何在SpringBoot项目中集成Quartz并使用Cron表达式进行任务调度,通过添加Quartz依赖、创... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

Python使用Pandas对比两列数据取最大值的五种方法

《Python使用Pandas对比两列数据取最大值的五种方法》本文主要介绍使用Pandas对比两列数据取最大值的五种方法,包括使用max方法、apply方法结合lambda函数、函数、clip方法、w... 目录引言一、使用max方法二、使用apply方法结合lambda函数三、使用np.maximum函数

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W