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

代码随想录第七章 栈与队列

1、leecode232 用栈实现队列

使用栈模拟队列的行为,仅使用一个栈是不行的,所以需要两个栈,一个是输入栈,一个是输出栈。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;class MyQueue {private:stack<int> stack_in;stack<int> stack_out;public:void push(int value) {stack_in.push(value);}int pop() {if (stack_out.empty()) {while (!stack_in.empty()) {stack_out.push(stack_in.top());stack_in.pop();}}int result = stack_out.top();stack_out.pop();return result;}int top() {if (stack_out.empty()) {while (!stack_in.empty()) {stack_out.push(stack_in.top());stack_in.pop();}}int result = stack_out.top();return result;}bool empty() {return stack_in.empty() && stack_out.empty();}
};void main() {MyQueue queue;queue.push(1);queue.push(2);queue.push(3);cout << "the first value: " << queue.pop() << endl;cout << "the next value: " << queue.pop() << endl;cout << "the next value: " << queue.pop() << endl;cout << "hello world" << endl;
}

2、用队列实现栈。 leetcode225

队列的规则是先进先出,把一个队列中的数据导入另一个队列,数据的顺序并没有变。所以用栈实现队列和用队列实现栈的思路是不一样的,取决于这两个数据结构的性质。如果用两个对列实现栈,那么两个队列就没有输入队列和输出队列的关系,另一个队列完全是用来备份的。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;class MyStack {private:queue<int> queue_fir;queue<int> queue_sec;public:void push(int val) {queue_fir.push(val);}int pop() {int size = queue_fir.size();size--;while (size--) {queue_sec.push(queue_fir.front());queue_fir.pop();}int result = queue_fir.front();queue_fir.pop();queue_fir = queue_sec;while (!queue_sec.empty()) {queue_sec.pop();}return result;}int top() {return queue_fir.back();}bool empty() {return queue_fir.empty();}
};void main() {MyStack stack;stack.push(1);stack.push(2);stack.push(3);cout << stack.pop() << endl;cout << stack.pop() << endl;cout << stack.pop() << endl;cout << "hello world" << endl;
}

3、匹配括号 leetcode20

这里有三种不匹配的情况

(1)、第一种情况,字符串中左方向的括号多余了,所以不匹配。

第一种情况:已经遍历了字符串,但是栈不为空,说明有相应的左括号,但没有右括号,所以返回错误。

(2)、第二种情况,括号没有多余,但是括号的类型不匹配。

在遍历字符串的过程中,发现栈中没有要匹配的字符,返回错误。

(3)、第三种情况,字符串中右方向的括号多余了,所以不匹配。

在遍历字符串的过程中栈已经为空,没有匹配的字符了,说明右括号没有找到对应的左括号,返回错误。

那么什么时候说明左括号和右括号全部匹配了呢?如果遍历字符串之后,栈是空的,则说明全都匹配了。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;class Solution {private:stack<int> st;public:bool IsValid(string& s) {for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {st.push(')');}else if (s[i] == '{') {st.push('}');}else if (s[i] == '[') {st.push(']');}else if (st.empty() || st.top() != s[i]) {return false;}else {st.pop();}}return st.empty();}
};void main() {string s = "(){}[]{[]}";Solution slo;slo.IsValid(s);cout << "hello world" << endl;
}

4、滑动窗口最大值 leetcode239

一个大小为k的滑动窗口,从前向后在数组nums上移动,返回滑动窗口每移动一次时窗口中的最大值。

(1)、设计单调对列,设计的时候,pop和push操作保持如下规则:

pop():如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不进行任何操作。

push():如果push的元素value大于入口元素的数值,那么就将队列入口的元素弹出,直到push元素的数值小于或等于队列入口元素的数值。

基于以上规则,每次窗口移动的时候,只要调用que.front()就可以返回当前窗口的最大值。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
using namespace std;//单调队列,从大到小
class MyQueue {private:deque<int> que;//使用deque实现单调队列public://每次弹出元素时,比较当前要弹出元素的数值是否等于队列出口元素的数值,如果相等则弹出。//弹出元素之前,需要判断队列当前是否为空void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}//如果要push的数组大于入口元素的数值,那么就将队列入口元素弹出,知道push的数值小于或等于对列入口元素的数值。//这样就保持了队列中的数值是从大到小的单调递减了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {return que.front();}
};void main() {cout << "hello world" << endl;
}

这样就用deque实现了一个单调队列,接下来解决求滑动窗口最大值的问题就简单了。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
using namespace std;class Slotuion {private://单调队列,从大到小class MyQueue {private:deque<int> que;//使用deque实现单调队列public://每次弹出元素时,比较当前要弹出元素的数值是否等于队列出口元素的数值,如果相等则弹出。//弹出元素之前,需要判断队列当前是否为空void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}//如果要push的数组大于入口元素的数值,那么就将队列入口元素弹出,知道push的数值小于或等于对列入口元素的数值。//这样就保持了队列中的数值是从大到小的单调递减了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {return que.front();}};private:MyQueue que;public:vector<int> MaxSlidingWindow(vector<int> &input,int k) {vector<int> result;for (int i = 0; i < k; i++) {que.push(input[i]);}result.push_back(que.front());for (int i = k; i < input.size(); i++) {que.push(input[i]);que.pop(input[i - k]);result.push_back(que.front());}return result;}
};void main() {vector<int> input = { 2,4,-2,-4,3,1,5 };int k = 4;Slotuion slo;slo.MaxSlidingWindow(input, k);cout << "hello world" << endl;
}

相关文章:

代码随想录第七章 栈与队列

1、leecode232 用栈实现队列 使用栈模拟队列的行为&#xff0c;仅使用一个栈是不行的&#xff0c;所以需要两个栈&#xff0c;一个是输入栈&#xff0c;一个是输出栈。 #include<iostream> #include<vector> #include<string> #include<stack> #incl…...

SQL Server对象类型(5)——4.5. 同义词(Synonym)

4.5. 同义词(Synonym) 4.5.1. 同义词概念 与Oracle中相同,SQL Server中的同义词是虚的、被定义的模式对象,其本身并不存储任何数据。其用途之一就是为其他类型基础对象提供一个别名;用途之二就是为应用提供一个抽象层,以方便后期应用相关的基础对象的更改和维护。用户可…...

IP风险查询:抵御DDoS攻击和CC攻击的关键一步

随着互联网的普及&#xff0c;网络攻击变得越来越普遍和复杂&#xff0c;对企业和个人的网络安全构成了重大威胁。其中&#xff0c;DDoS&#xff08;分布式拒绝服务&#xff09;攻击和CC&#xff08;网络连接&#xff09;攻击是两种常见且具有破坏性的攻击类型&#xff0c;它们…...

Tune-A-Video论文阅读

论文链接&#xff1a;Tune-A-Video: One-Shot Tuning of Image Diffusion Models for Text-to-Video Generation 文章目录 摘要引言相关工作文生图扩散模型文本到视频生成模型文本驱动的视频编辑从单个视频生成 方法前提DDPMsLDMs 网络膨胀微调和推理模型微调基于DDIM inversio…...

Dataset和DataLoader用法

Dataset和DataLoader用法 在d2l中有简洁的加载固定数据的方式&#xff0c;如下 d2l.load_data_fashion_mnist() # 源码 Signature: d2l.load_data_fashion_mnist(batch_size, resizeNone) Source: def load_data_fashion_mnist(batch_size, resizeNone):"""…...

【跟小嘉学习区块链】二、Hyperledger Fabric 架构详解

系列文章目录 【跟小嘉学习区块链】一、区块链基础知识与关键技术解析 【跟小嘉学习区块链】一、区块链基础知识与关键技术解析 文章目录 系列文章目录[TOC](文章目录) 前言一、Hyperledger 社区1.1、Hyperledger(面向企业的分布式账本)1.2、Hyperledger社区组织结构 二、Hype…...

springboot下spring方式实现Websocket并设置session时间

概述 springboot实现websocket有4种方式 servlet&#xff0c;spring&#xff0c;netty&#xff0c;stomp 使用下来spring方式是最简单的. springboot版本&#xff1a;3.1.2 jdk&#xff1a;17 当前依赖版本 <dependency><groupId>org.springframework.boot<…...

LeetCode算法二叉树—相同的树

目录 100. 相同的树 - 力扣&#xff08;LeetCode&#xff09; 代码&#xff1a; 运行结果&#xff1a; 给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是…...

搭建Flink集群、集群HA高可用以及配置历史服务器

Flink集群搭建 Flink集群搭建集群规划下载并解压安装包修改集群配置分发安装目录启动集群访问Web UI Flink集群HA高可用概述集群规划配置flink配置master、workers配置ZK分发安装目录启动HA集群测试 Flink参数配置配置历史服务器概述配置启动、停止历史服务器提交一个Job任务查…...

vscode终端中打不开conda虚拟包管理

今天&#xff0c;想着将之前鸽的Unet网络模型给实现一下&#xff0c;结果发现&#xff0c;在vscode中运行python脚本&#xff0c;显示没有这包&#xff0c;没有那包。但是在其他的ipynb中是有的&#xff0c;感觉很奇怪。我检查了一下python版本&#xff0c;发现不是我深度学习的…...

【音视频】MP4封装格式

基本概念 使用MP4box.js查看MP4内部组成结构 整体结构 数据索引&#xff08;moov&#xff09;数据流包&#xff08;mdat&#xff09; 各个包的位置&#xff0c;大小&#xff0c;信息&#xff0c;时间戳&#xff0c;编码方式等全在数据索引 数据流包只有纯二进制码流数据 数据…...

环境-使用vagrant快速创建linux虚拟机

1.下载软件 虚拟机 Oracle VM VirtualBox 镜像 Vagrant by HashiCorp (vagrantup.com) 如果下载慢&#xff0c;可以复制下载链接&#xff0c;使用迅雷下载 2.安装 根据提示点击下一步即可&#xff0c;建议安装到空间较大的非系统盘。 打开 window cmd 窗口&#xff0c;…...

10.1网站编写(Tomcat和servlet基础)

一.Tomcat: 1.Tomcat是java写的,运行时需要依赖jre,所以要装jdk. 2.建议配置好环境变量. 3.默认端口号8080(业务端口)可能会被占用,建议改一下(本人改成了9999). 4.另一个默认端口是8005(管理端口). 二Servlet基础(编写一个hello world代码): 整体分为7个步骤,分别是创建…...

10CQRS

本系列包含以下文章&#xff1a; DDD入门DDD概念大白话战略设计代码工程结构请求处理流程聚合根与资源库实体与值对象应用服务与领域服务领域事件CQRS&#xff08;本文&#xff09; 案例项目介绍 # 既然DDD是“领域”驱动&#xff0c;那么我们便不能抛开业务而只讲技术&…...

DAZ To UMA⭐一.DAZ简单使用教程

文章目录 &#x1f7e5; DAZ快捷键&#x1f7e7; DAZ界面介绍 &#x1f7e5; DAZ快捷键 移动物体:ctrlalt鼠标左键 旋转物体:ctrlalt鼠标右键 导入模型:双击左侧模型UI &#x1f7e7; DAZ界面介绍 Files:显示全部文件 Products:显示全部产品 Figures:安装的全部人物 Wardrobe…...

面试题 —— Java集合篇(23题)

文章目录 1.Java中常见集合有哪些 &#xff1f;2. 说说你对Java集合是怎么理解的&#xff1f;3.请你说一下List&#xff0c;Set&#xff0c;Map三者的特点是 &#xff1f;4.在实际开发过程中如何更好的选择集合 &#xff1f;5. ArrayList和Vector区别 &#xff1f;6. ArrayList…...

SpringBoot2.7.14整合Swagger3.0的详细步骤及容易踩坑的地方

&#x1f9d1;‍&#x1f4bb;作者名称&#xff1a;DaenCode &#x1f3a4;作者简介&#xff1a;啥技术都喜欢捣鼓捣鼓&#xff0c;喜欢分享技术、经验、生活。 &#x1f60e;人生感悟&#xff1a;尝尽人生百味&#xff0c;方知世间冷暖。 &#x1f4d6;所属专栏&#xff1a;Sp…...

题解:ABC321D - Set Menu

题解&#xff1a;ABC321D - Set Menu 题目 链接&#xff1a;Atcoder。 链接&#xff1a;洛谷。 难度 算法难度&#xff1a;B。 思维难度&#xff1a;C。 调码难度&#xff1a;B。 综合评价&#xff1a;见洛谷链接。 算法 枚举二分查找。 思路 先对b升序排序&#x…...

什么是Progressive Web App(PWA)?它们有哪些特点?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 渐进式Web App简介⭐ PWAs的主要特点⭐ 总结⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入…...

MySQL的高级SQL语句

目录 一、高级SQL语句 1、select 查询表中一个或多个字段的数据 2、distinct 不显示重复的数据记录 3、where 有条件查询 4、and与or 且与或 5、in 显示在某个范围值内 的字段的信息 6、between 显示两个值范围内的数据记录 7、order by 对字…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...