当前位置: 首页 > 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 对字…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...