代码随想录打卡第十二天补

2024-06-17 21:04

本文主要是介绍代码随想录打卡第十二天补,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录打卡第十二天补

第五章 栈和队列 part2

150. 逆波兰表达式求值

本题不难,但第一次做的话,会很难想到,所以先看视频,了解思路再去做题

题目链接/文章讲解/视频讲解: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

这个题目的话,首先想到的就是使用栈的解法,需要一遇到运算符进行取出顶上两个元素的操作,然后再将运算结果放入栈中。思路比较简单

问题:

数据结构栈的使用:Deque还是什么

怎么判断是数字还是运算符

看了代码随想录的之后,发现可以直接进行比较运算符,使用equals,然后使用if else结构就可以直接的获取非运算符的数字了,其次主义题目中其实说明了除法中 的取整

然后在写的时候发现,取出来的是数字,只要存进去的时候转换为数字,取出来肯定是数字,然后就是,字符相等的比较的时候,单双引号的问题,单引号是字符,双引号是字符串。但是为什么在取出来的时候不用字符那,因为是字符串数组,不是字符数组

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<>();for (String eachstr : tokens){if(eachstr.equals("+")){stack.push(stack.pop() + stack.pop());} else if(eachstr.equals("-")) {int s1 = stack.pop();int s2 = stack.pop();stack.push( s2 - s1);} else if (eachstr.equals("*")) {stack.push( stack.pop() * stack.pop());} else if (eachstr.equals("/")) {int s1 = stack.pop();int s2 = stack.pop();stack.push( s2 / s1);} else {stack.push(Integer.valueOf(eachstr));}}return stack.pop();}
}

239. 滑动窗口最大值 (有点难度,可能代码写不出来,但一刷至少需要理解思路

之前讲的都是栈的应用,这次该是队列的应用了。

本题算比较有难度的,需要自己去构造单调队列,建议先看视频来理解。

题目链接/文章讲解/视频讲解: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

思路:读完题目,觉得,我每次智能看到窗口里面的数字,然后我只需要每次移动之后,找到窗口的最大值并存入一个数组就可以。然后窗口的数据结构的实现用什么那,然后这道题目的难点应该在于每次如何找到窗口的最大值。如果吗每次都需要遍历就很复杂。

看完代码随想录:单调队列,首先理解单调队列的思想,就是维护一个队首为最大值的队列,注意仅仅针对这道题目来说,然后就是,队列里面需要存储的是这个窗口的数据,每次在添加元素的时候,需要判断这个元素是否比队列末尾的元素大,打的话就替换掉,同时也要注意队首的元素是否存在于这个窗口中,也就是需要判断窗口移动的时候是否移出去的数据是队头元素。

回顾一下双端队列的new方法和添加删除元素的方法:

今日收获:在写代码模拟过程的时候,其实放在最普通最中间的情况去看待问题,从大方向去把握代码的各部分内容,再从细节把握每部分的具体操作

先写一个队列存储的下标的版本

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {ArrayDeque<Integer> deque = new ArrayDeque<>();int[] res = new int[nums.length - k + 1];int idx=0;for (int i = 0; i < nums.length; i++){//先看队头元素是否需要移除,i指代需要加入队列的元素的下标,注意这里需要使用whilewhile(!deque.isEmpty() && deque.peekFirst() <= i-k){//注意这里需要指明是队头deque.pollFirst();}//加入队尾元素while(!deque.isEmpty() && nums[deque.peekLast()] <nums[i] ){deque.removeLast();}//添加元素的话需要在循环外面deque.addLast(i);if (i+1 >= k){res[idx] = nums[deque.peekFirst()];idx++;}}return res;}
}

347.前 K 个高频元素 (有点难度,可能代码写不出来,一刷至少需要理解思路)

大/小顶堆的应用, 在C++中就是优先级队列

本题是 大数据中取前k值 的经典思路,了解想法之后,不算难。

题目链接/文章讲解/视频讲解:https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

这里我们就先理解下思路,直接看代码随想录的

/*Comparator接口说明:* 返回负数,形参中第一个参数排在前面;返回正数,形参中第二个参数排在前面* 对于队列:排在前面意味着往队头靠* 对于堆(使用PriorityQueue实现):从队头到队尾按从小到大排就是最小堆(小顶堆),*                                从队头到队尾按从大到小排就是最大堆(大顶堆)--->队头元素相当于堆的根节点* */
class Solution {//解法1:基于大顶堆实现public int[] topKFrequent1(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数for (int num : nums) {map.put(num, map.getOrDefault(num,0) + 1);}//在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);for (Map.Entry<Integer, Integer> entry : map.entrySet()) {//大顶堆需要对所有元素进行排序pq.add(new int[]{entry.getKey(), entry.getValue()});}int[] ans = new int[k];for (int i = 0; i < k; i++) { //依次从队头弹出k个,就是出现频率前k高的元素ans[i] = pq.poll()[0];}return ans;}//解法2:基于小顶堆实现public int[] topKFrequent2(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}//在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序if (pq.size() < k) { //小顶堆元素个数小于k个时直接加pq.add(new int[]{entry.getKey(), entry.getValue()});} else {if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了pq.add(new int[]{entry.getKey(), entry.getValue()});}}}int[] ans = new int[k];for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多ans[i] = pq.poll()[0];}return ans;}
}

总结

栈与队列做一个总结吧,加油

https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html

这篇关于代码随想录打卡第十二天补的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时