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

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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

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

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