数据结构-栈与队列笔记
普通的双端队列
用栈实现队列
232. 用栈实现队列 - 力扣(LeetCode)
import java.util.ArrayDeque;
import java.util.Deque;class MyQueue {// 使用双端队列(Deque)来实现一个队列Deque<Integer> input; // 用于存放新加入的元素Deque<Integer> output; // 用于存放准备出队的元素public MyQueue() {input = new ArrayDeque<>(); // 初始化input队列output = new ArrayDeque<>(); // 初始化output队列}public void push(int x) {// 将元素x添加到input队列的前端input.addFirst(x);}public int pop() {// 首先调用exchange方法,确保output队列中有元素exchange();// 从output队列的前端移除并返回元素return output.removeFirst();}public int peek() {// 首先调用exchange方法,确保output队列中有元素exchange();// 返回output队列前端的元素,但不移除它return output.getFirst();}public boolean empty() {// 如果input和output队列都为空,则返回true,表示队列为空return input.isEmpty() && output.isEmpty();}public void exchange() {// 如果output队列不为空,则不需要交换,直接返回if (!output.isEmpty()) {return;}// 当output队列为空时,将input队列中的所有元素转移到output队列while (!input.isEmpty()) {int temp = input.removeFirst(); // 从input队列前端移除元素output.addFirst(temp); // 将移除的元素添加到output队列的前端}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue(); // 创建MyQueue对象* obj.push(x); // 将元素x添加到队列* int param_2 = obj.pop(); // 移除并返回队列前端的元素* int param_3 = obj.peek(); // 返回队列前端的元素,但不移除* boolean param_4 = obj.empty(); // 检查队列是否为空*/
有效的括号(难)
20. 有效的括号 - 力扣(LeetCode)
import java.util.ArrayDeque;
import java.util.Deque;class Solution {public boolean isValid(String s) {// 使用双端队列(Deque)来存储尚未匹配的右括号Deque<Character> deque = new ArrayDeque<>();// 遍历字符串s中的每个字符for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i); // 获取当前遍历到的字符// 如果当前字符是左括号,将其对应的右括号添加到队列的前端if (ch == '(') {deque.addFirst(')');} else if (ch == '{') {deque.addFirst('}');} else if (ch == '[') {deque.addFirst(']');} else {// 如果当前字符是右括号// 检查栈是否为空或者栈顶元素是否与当前右括号匹配if (deque.isEmpty() || ch != deque.getFirst()) {// 如果栈为空或者栈顶元素不匹配,说明括号序列无效,返回falsereturn false;} else {// 如果栈顶元素与当前右括号匹配,从队列中移除栈顶元素deque.removeFirst();}}}// 最后检查栈是否为空,如果为空,说明所有括号都正确匹配,返回true;否则返回falsereturn deque.isEmpty();}
}
删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 - 力扣(LeetCode)
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringBuilder;class Solution {public String removeDuplicates(String s) {// 使用双端队列(Deque)来存储不重复的字符Deque<Character> deque = new ArrayDeque<>();// 遍历字符串s中的每个字符for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i); // 获取当前遍历到的字符// 如果队列不为空且队列的第一个字符与当前字符相同if (!deque.isEmpty() && deque.getFirst() == ch) {// 移除队列中的第一个字符deque.removeFirst();} else {// 否则,将当前字符添加到队列的前端deque.addFirst(ch);}}// 使用StringBuilder来构建最终的字符串StringBuilder sb = new StringBuilder();// 遍历队列,将队列中的字符添加到StringBuilder中while (!deque.isEmpty()) {sb.append(deque.removeLast()); // 从队列的后端移除字符并添加到StringBuilder}// 将StringBuilder转换为字符串并返回return sb.toString();}
}
逆波兰表达式求值
150. 逆波兰表达式求值 - 力扣(LeetCode)
import java.util.ArrayDeque;
import java.util.Deque;class Solution {public int evalRPN(String[] tokens) {// 使用双端队列(Deque)来存储操作数Deque<Integer> deque = new ArrayDeque<>();// 遍历tokens数组中的每个元素for (int i = 0; i < tokens.length; i++) {String ch = tokens[i]; // 获取当前遍历到的元素// 如果当前元素是运算符if (ch.equals("+")) {// 从队列中弹出前两个操作数int first = deque.removeFirst();int second = deque.removeFirst();// 计算它们的和,并将其压入队列前端int sum = first + second;deque.addFirst(sum);} else if (ch.equals("-")) {// 从队列中弹出前两个操作数int first = deque.removeFirst();int second = deque.removeFirst();// 计算它们的差,并将其压入队列前端int sum = second - first;deque.addFirst(sum);} else if (ch.equals("*")) {// 从队列中弹出前两个操作数int first = deque.removeFirst();int second = deque.removeFirst();// 计算它们的乘积,并将其压入队列前端int sum = first * second;deque.addFirst(sum);} else if (ch.equals("/")) {// 从队列中弹出前两个操作数int first = deque.removeFirst();int second = deque.removeFirst();// 计算它们的商,并将其压入队列前端// 注意:这里假设不会出现除以零的情况int sum = second / first;deque.addFirst(sum);} else {// 如果当前元素不是运算符,将其转换为整数并压入队列前端deque.addFirst(Integer.parseInt(ch));}}// 返回队列中的第一个元素,即表达式的结果return deque.getFirst();}
}
单调队列
滑动窗口最大值(难)
239. 滑动窗口最大值 - 力扣(LeetCode)
import java.util.ArrayDeque;
import java.util.Deque;class MyDeque {Deque<Integer> deque; // 双端队列,用于存储元素MyDeque() {deque = new ArrayDeque<>(); // 初始化双端队列}// 尝试移除队列头部的元素,如果头部元素等于valboolean remove(int val) {if (!deque.isEmpty() && deque.getFirst() == val) {deque.removeFirst(); // 移除队列头部元素}return true; // 无论是否移除,都返回true}// 将val添加到队列中,移除所有比val小的尾部元素boolean add(int val) {while (!deque.isEmpty() && deque.getLast() < val) {deque.removeLast(); // 移除队列尾部元素}deque.addLast(val); // 添加val到队列尾部return true; // 返回true表示添加成功}// 返回队列头部的元素,即当前窗口中的最大值int maxValue() {return deque.getFirst(); // 返回队列头部元素}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length; // 输入数组的长度int[] ret = new int[n - k + 1]; // 存储每个窗口的最大值MyDeque deque = new MyDeque(); // 创建MyDeque对象// 将数组的前k个元素添加到队列中for (int i = 0; i < k; i++) {deque.add(nums[i]);}// 将第一个窗口的最大值添加到结果数组中int index = 0;ret[index++] = deque.maxValue();// 遍历数组,从索引k到n-1for (int i = k; i < n; i++) {// 移除窗口外的元素deque.remove(nums[i - k]);// 将当前元素添加到队列中deque.add(nums[i]);// 将当前窗口的最大值添加到结果数组中ret[index++] = deque.maxValue();}return ret; // 返回结果数组}
}
优先队列
前 K 个高频元素(难)
. - 力扣(LeetCode)
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;class Solution {public int[] topKFrequent(int[] nums, int k) {// 创建一个HashMap来存储数组中每个数字的出现次数HashMap<Integer, Integer> hashmap = new HashMap<>();for (int num : nums) {// 对于数组中的每个数字,如果它已经在HashMap中,则增加其计数,否则添加到HashMap中并设置计数为1hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);}// 创建一个小顶堆(PriorityQueue),用于存储二元组(数字,出现次数)// 比较器使用Lambda表达式,根据二元组的第二个元素(出现次数)来比较PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);for (Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {// 遍历HashMap中的每个条目if (pq.size() < k) {// 如果堆的大小小于k,则直接添加当前条目pq.add(new int[]{entry.getKey(), entry.getValue()});} else {// 如果堆的大小已经达到k,并且堆顶元素的出现次数小于当前条目的出现次数if (pq.peek()[1] < entry.getValue()) {// 移除堆顶元素(出现次数最小的元素)pq.poll();// 添加当前条目pq.add(new int[]{entry.getKey(), entry.getValue()});}}}// 创建一个数组来存储最终的k个最频繁出现的数字int[] ret = new int[k];for (int i = 0; i < k; i++) {// 依次从堆中取出元素,填充到数组中ret[i] = pq.poll()[0];}// 返回结果数组return ret; }
}
相关文章:
数据结构-栈与队列笔记
普通的双端队列 用栈实现队列 232. 用栈实现队列 - 力扣(LeetCode) import java.util.ArrayDeque; import java.util.Deque;class MyQueue {// 使用双端队列(Deque)来实现一个队列Deque<Integer> input; // 用于存放新加…...
DevExpress WPF中文教程:如何解决数据更新的常见问题?
DevExpress WPF拥有120个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpress WPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。 无论是Office办公软件…...

SpringBoot基础(四):bean的多种加载方式
SpringBoot基础系列文章 SpringBoot基础(一):快速入门 SpringBoot基础(二):配置文件详解 SpringBoot基础(三):Logback日志 SpringBoot基础(四):bean的多种加载方式 目录 一、xml配置文件二、注解定义bean1、使用AnnotationCon…...
JavaScript网页设计案例:构建动态交互的在线图书管理系统
JavaScript网页设计案例:构建动态交互的在线图书管理系统 在当今的数字化时代,网页设计不仅仅是关于美观和布局,更重要的是用户体验和互动性。JavaScript,作为一种强大的编程语言,在网页开发中扮演着至关重要的角色&a…...

嵌入式数据结构中线性表的具体实现
大家好,今天主要给大家分享一下,如何使用数据结构中的线性表以及具体的实现。 第一:线性表的定义和表示方法 线性表的定义 – 线性表就是零个或多个相同数据元素的有限序列。 • 线性表的表示方法 – 线性表记为: L=(a0,∙∙∙∙∙∙∙∙ai-1aiai+1 ∙∙∙∙∙∙an-1) •…...

Redis高级篇 —— 分布式缓存
Redis高级篇 —— 分布式缓存 文章目录 Redis高级篇 —— 分布式缓存1 Redis持久化1.1 RDB1.2 RDB的fork原理1.3 RDB总结1.4 AOF持久化1.5 RDB和AOF的对比 2 Redis主从2.1 搭建主从架构2.2 数据同步原理2.2.1 全量同步2.2.2 增量同步 3 Redis哨兵3.1 哨兵的作用和原理3.1.1 哨兵…...

彩族相机内存卡恢复多种攻略:告别数据丢失
在数字时代,相机内存卡作为我们存储珍贵照片和视频的重要媒介,其数据安全性显得尤为重要。然而,意外删除、错误格式化、存储卡损坏等情况时有发生,导致数据丢失,给用户带来不小的困扰。本文将详细介绍彩族相机内存卡数…...
【C语言】计算需要的缓冲区大小
使用 snprintf 函数计算缓冲区大小的方法其实是一个常见的技巧,因为 snprintf 会返回所需的缓冲区大小,而不需要实际写入任何数据。当传入 NULL 指针时,`snprintf` 并不会尝试写入数据,而是仅仅返回格式化后的字符串长度。如果再加上终止符(即 \0),我们就可以知道实际需…...

Renesas R7FA8D1BH (Cortex®-M85) 上超声波测距模块(HC-SR04)驱动开发
目录 概述 1 软硬件 1.1 软硬件环境信息 1.2 开发板信息 1.3 调试器信息 2 硬件架构 2.1 硬件框架结构 2.2 测距模块(HC-SR04)介绍 2.2.1 HC-SR04特性 2.2.2 HC-SR04操作时序 2.2.3 计算距离 3 软件实现 3.1 FSP配置项目 3.1.1 配置IO口的外…...

短视频矩阵系统独立源码/源头开发
短视频矩阵系统独立源码/源头开发 #抖音矩阵系统源码开发 #短视频矩阵系统源码开发 #短视频seo源码开发 一、 抖音短视频seo矩阵系统源码开发,需要掌握以下技术: 网络编程:能够使用Python、Java或其他编程语言进行网络编程,比如…...

k8s部署jenkins集群,配置集群kubernetes plugin的pod模板
一、配置集群 填写k8s地址:https://kubernetes.default.svc.cluster.local 命名空间:kubernetes-plugin Jenkins地址:http://jenkins:18080 Jenkins通道:jenkins:50000 jenkins是容器别名 设置jenkinsslave的标签属性 二、…...

微软确认Word离奇Bug 命名不当会导致文件被删
微软近日确认Word应用中存在一个Bug,该漏洞可能导致用户在特定情况下错误地删除文件。该问题主要出现在文件命名过程中,如果用户在保存Word文件时采用特定的命名方式,文件可能会被移动到回收站。 根据微软支持中心的消息,如果用户…...

Vue包的安装使用
文章目录 vue介绍一、灵活易用1.渐进式框架2.简洁的语法 二、高效的响应式系统1.数据驱动2.响应式原理 三、强大的组件化开发1.组件化思想2.组件通信 四、丰富的生态系统1.插件和库2.社区支持 安装依赖删除新增文件夹components设置(1)home.vue(2)data.vue(3)zero.vue router配…...

大模型1-本地部署实现交互问答
任务 在本地部署大模型,调用大模型进行对话。 添加库: 1、Transformer Transformers 是由 Hugging Face 开发的一个开源库,广泛应用于自然语言处理(NLP)任务。其主要功能是简化了对大型预训练语言模型的加载和使用…...

鸿蒙架构-系统架构师(七十八)
1信息加密是保证系统机密性的常用手段。使用哈希校验是保证数据完整性的常用方法。可用性保证合法用户对资源的正常访问,不会被不正当的拒绝。()就是破坏系统的可用性。 A 跨站脚本攻击XSS B 拒绝服务攻击DoS C 跨站请求伪造攻击CSRF D 缓…...

大数据存储计算平台EasyMR:多集群统一管理助力企业高效运维
随着全球企业进入数字化转型的快车道,数据已成为企业运营、决策和增长的核心驱动力。为了处理海量数据,同时应对数据处理的复杂性和确保系统的高可用性,企业往往选择部署多个Hadoop集群,这样的策略可以将生产环境、测试环境和灾备…...
代理IP的类型及其在爬虫中的应用
1 动态住宅代理 这些IP地址来自真实的住宅用户,因此具有很高的匿名性和隐私性,不易被别为代理IP。而增加了爬虫任务的安全性。这类代理有以下特点: 高安全性:使用这类代理可发起真实有效的请求,提高爬虫效率的同时&am…...
鸿蒙Swiper动态加载翻页数据(等同于安卓动态加载viewPager)
我这里是加载一个实体类列表 类似 List 的数据,那么首先写一个dataSource: export class MyDataSource implements IDataSource {private list: MyBean[] []constructor(list: MyBean[]) {this.list list}totalCount(): number {return this.list.len…...

嵌入式面试——FreeRTOS篇(八) Tickless低功耗
本篇为:FreeRTOS Tickless 低功耗模式篇 一、低功耗模式简介 1、低功耗介绍 答: 很多应用场合对于功耗的要求很严格,比如可穿戴低功耗产品、物联网低功耗产品等;一般MCU都有相应的低功耗模式,裸机开发时可以使用MCU的…...

基于facefusion的换脸
FaceFusion是一个引人注目的开源项目,它专注于利用深度学习技术实现视频或图片中的面部替换。作为下一代换脸器和增强器,FaceFusion在人脸识别和合成技术方面取得了革命性的突破,为用户提供了前所未有的视觉体验。 安装 安装基础软件 安装…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...

3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...