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

笔记 | P4387 【深基15.习9】验证栈序列 题解

题解

问题描述

给出两个序列 pushedpoped,分别表示入栈和出栈操作的顺序。我们需要判断给定的出栈序列是否可能对应于给定的入栈序列。如果可能,则输出 “Yes”;否则,输出 “No”。

解题思路

  1. 读取输入:读取询问次数 q 和每次询问的入栈和出栈序列。

  2. 模拟栈操作:通过使用一个栈(s1)和一个队列(s2),我们可以模拟栈的入栈和出栈操作。
    a. 入栈操作:按顺序遍历入栈序列 pushed,每次将元素推入栈 s1
    b. 出栈操作:每次入栈后,检查栈顶元素是否与队列 s2 的前端元素相匹配。如果匹配,则从栈和队列中弹出元素,并继续检查下一个元素,直到不匹配或栈为空。

  3. 检查结果:如果所有出栈元素都被成功弹出,则输出 “Yes”。否则,输出 “No”。

  4. 清理数据结构:为下一次查询准备,确保栈和队列为空。

原始代码的错误

原始代码中的错误在于缺乏对连续出栈操作的处理。在模拟过程中,可能存在连续几个元素需要出栈的情况,但原始代码在每次入栈后只执行了一次出栈操作。这意味着对于某些入栈和出栈序列组合,代码可能在执行完所有的入栈操作后仍然留有未匹配的出栈元素。

错误代码部分:

for(int i=0;i<n;i++) {s1.push(pushed[i]);if(!s1.empty() && s1.top() == s2.front()) {s2.pop();s1.pop();}
}

修正

修正代码主要在于增加一个内部循环,其实是把原先 if 语句改成 while 循环,用于在每次入栈后连续检查栈顶元素与队列头部元素的匹配,直到不匹配或栈为空。

修正的代码块:

for(int i=0;i<n;i++) {s1.push(pushed[i]);while(!s1.empty() && s1.top() == s2.front()) {s2.pop();s1.pop();}
}

复杂度分析

时间复杂度:O(n),空间复杂度:O(n)。

代码简洁化

经过这一修正,原始代码中的第二个 while 循环成为多余,并被删除。最终的代码版本更精简,也更符合问题描述中的逻辑。

最终版本的完整代码:

#include<bits/stdc++.h>
using namespace std;
int pushed[100005];
int poped[100005];
stack<int> s1;
queue<int> s2;
int main() {int q;cin>>q;while(q--) {int n;cin>>n;for(int i=0;i<n;i++) {cin>>pushed[i];}for(int i=0;i<n;i++) {cin>>poped[i];s2.push(poped[i]);}for(int i=0;i<n;i++) {s1.push(pushed[i]);while(!s1.empty() && s1.top() == s2.front()) {s2.pop();s1.pop();}}if(s1.empty())cout<<"Yes"<<endl;elsecout<<"No"<<endl;while(!s1.empty()) s1.pop();while(!s2.empty()) s2.pop();}return 0;
}

这个版本的代码更精简,也更符合问题描述中的逻辑。

相关文章:

笔记 | P4387 【深基15.习9】验证栈序列 题解

题解 问题描述 给出两个序列 pushed 和 poped&#xff0c;分别表示入栈和出栈操作的顺序。我们需要判断给定的出栈序列是否可能对应于给定的入栈序列。如果可能&#xff0c;则输出 “Yes”&#xff1b;否则&#xff0c;输出 “No”。 解题思路 读取输入&#xff1a;读取询问…...

PyTorch中nn-XXX与F-XXX的区别

nn.XXX与F.XXX PyTorch中torch.nn**&#xff08;以下简写为nn&#xff09;中的模块和torch.nn.functional&#xff08;以下简写为F&#xff09;**中的模块都提供了常用的神经网络操作&#xff0c;包括激活函数、损失函数、池化操作等。它们的主要区别如下&#xff1a; nn中的…...

zookeeper集群和kafka的相关概念就部署

目录 一、Zookeeper概述 1、Zookeeper 定义 2、Zookeeper 工作机制 3、Zookeeper 特点 4、Zookeeper 数据结构 5、Zookeeper 应用场景 &#xff08;1&#xff09;统一命名服务 &#xff08;2&#xff09;统一配置管理 &#xff08;3&#xff09;统一集群管理 &#xff08;4&a…...

第4集丨Vue 江湖 —— 计算属性

目录 一、基本使用1.1 在computed中定义1.1.1 案例1.1.2 控制台调用getter1.1.3 控制台中的data和computed 1.2 缓存效果1.3 完整写法1.3.1 案例1.3.2 效果图 1.4 简写形式 二、案例的其他实现2.1 methods实现2.2 插值语法实现 三、体会计算属性的好处3.1 复杂任务时3.2 使用计…...

Docker 容器化学习

文章目录 前言Docker架构 1、 docker安装2、启动docker服务3、设置docker随机器一起启动4、docker体验5、docker常规命令5.1、容器操作docker [run|start|stop|restart|kill|rm|pause|unpause]docker [ps|inspect|exec|logs|export|import] 5.2、镜像操作docker images|rmi|tag…...

springboot第34集:ES 搜索,nginx

#用search after解决深分页性能问题 #第一页 GET /bank/_search {"size": 10,"sort": [{"account_number": {"order": "asc"}}] }#第二页 GET /bank/_search {"size": 10,"sort": [{"account_numb…...

微信小程序中的分包使用介绍

一、分包的好处 可以优化小程序首次启动的下载时间 在多团队共同开发时可以更好的解耦协作 主包&#xff1a;放置默认启动页面/TabBar 页面&#xff0c;公共资源/JS 脚本 分包&#xff1a;根据开发者的配置进行划分 限制&#xff1a;所有分包大小不超过 20M&#xff0c;单…...

【云原生】K8S二进制搭建二:部署CNI网络组件

目录 一、K8S提供三大接口1.1容器运行时接口CRI1.2云原生网络接口CNI1.3云原生存储接口CSI 二、Flannel网络插件2.1K8S中Pod网络通信2.2Overlay Network2.3VXLAN2.4Flannel 三、Flannel udp 模式的工作原理3.1ETCD 之 Flannel 提供说明 四、vxlan 模式4.1Flannel vxlan 模式的工…...

【iOS】—— 离屏渲染

文章目录 离屏渲染UIView和CALayer关系GPU屏幕渲染有两种方式:产生离屏渲染的原因&#xff1a;既然离屏渲染这么耗性能,为什么有这套机制呢?什么情况会离屏渲染&#xff1f;既然离屏渲染这么不好&#xff0c;为什么我们还要强制开启呢&#xff1f;如何避免离屏渲染&#xff1f…...

基于人工智能的中医图像分类系统设计与实现

华佗AI 《支持中医,永远传承古老文化》 本存储库包含一个针对中药的人工智能图像分类系统。该项目的目标是通过输入图像准确识别和分类各种中草药和成分。 个人授权许可证 版权所有 2023至2050特此授予任何获得华佗AI应用程序(以下简称“软件”)副本的人免费许可,可根据以…...

spring security + oauth2 使用RedisTokenStore 以json格式存储

1.项目架构 2.自己对 TokenStore 的 redis实现 package com.enterprise.auth.config;import org.springframework.data.redis.connection.RedisConnection; import org.springframework.data.redis.connection.RedisConnectionFactory; import org.springframework.data.redis…...

css position: sticky;实现上下粘性布局,中间区域滚动

sticky主要解决的问题 1、使用absolute和fixed中间区域需要定义高度2、使用absolute和fixed底部需要写padding-bottom 避免列表被遮挡住一部分&#xff08;底部是浮窗的时候&#xff0c;需要动态的现实隐藏&#xff09; <!DOCTYPE html> <html lang"en"&…...

解密HTTP代理爬虫中的IP代理选择与管理策略

在当今数据驱动的世界中&#xff0c;HTTP代理爬虫作为一项重要的数据采集工具&#xff0c;其成功与否往往取决于IP代理的选择与管理策略。作为一家专业的HTTP代理产品供应商&#xff0c;我们深知IP代理在数据采集中的重要性。在本文中&#xff0c;我们将分享一些关于HTTP代理爬…...

pytorch入门

详细安装教程和环境配置可以看&#xff1a;Python深度学习&#xff1a;安装Anaconda、PyTorch&#xff08;GPU版&#xff09;库与PyCharm_哔哩哔哩_bilibili 跟学课程&#xff1a;B站我是土堆 pytorch中两个实用函数&#xff1a; dir()&#xff1a;打开 help():说明书…...

Redis | 主从模式

Redis | 主从模式 1. 简介 Redis主从模式&#xff08;Replication&#xff09;是Redis提供的一种数据备份和高可用性解决方案。通过主从复制&#xff0c;可以将一个Redis服务器的数据复制到其他多个从服务器&#xff0c;从而实现数据的备份和读写分离&#xff0c;提高系统的性…...

C# Blazor 学习笔记(8):row/col布局开发

文章目录 前言相关文章代码row和col组件B_rowB_col结构 使用 前言 可能是我用的element ui和 uView这种第三方组件用的太多了。我上来就希望能使用这些组件。但是目前Blazor目前的生态其实并不完善&#xff0c;所以很多组件要我们自己写。 我们对组件的要求是 我们在组件化一共…...

金融供应链智能合约 -- 智能合约实例

前提 Ownable:监管者合约,有一个函数能转让监管者。 SupplyChainFin:供应链金融合约,银行、公司信息上链&#xff0c;公司和银行之间的转账。 发票&#xff1a;记录者交易双方和交易金额等的一种记录数据。如:我在超市买了一瓶水,超市给我开了一张发票。 Ownable // SPDX-…...

论文《Contrastive Meta Learning with Behavior Multiplicity for Recommendation》阅读

论文《Contrastive Meta Learning with Behavior Multiplicity for Recommendation》阅读 论文概况论文主要贡献Background & Motivation方法论单行为图神经网络&#xff08;Behavior-aware GNN&#xff09;多行为对比学习元对比编码模型训练 实验部分论文总结 论文概况 今…...

K8S 部署 RocketMQ

文章目录 添加模板部署本地访问 集群使用 kubesphere 作为工具 添加模板 添加 helm 模板 helm repo add rocketmq-repo https://helm-charts.itboon.top/rocketmq helm repo update rocketmq-repo编写 value.yaml 文件 配置主从节点的个数&#xff0c;例子为单节点 broker:…...

[Docker]入门之docker-compose

一&#xff0c;Docker-compose简介 1&#xff0c;Docker-compose简介 Docker-Compose项目是Docker官方的开源项目&#xff0c;负责实现对Docker容器集群的快速编排。 Docker-Compose将所管理的容器分为三层&#xff0c;分别是工程&#xff08;project&#xff09;&#xff0c…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

Qt的学习(二)

1. 创建Hello Word 两种方式&#xff0c;实现helloworld&#xff1a; 1.通过图形化的方式&#xff0c;在界面上创建出一个控件&#xff0c;显示helloworld 2.通过纯代码的方式&#xff0c;通过编写代码&#xff0c;在界面上创建控件&#xff0c; 显示hello world&#xff1b; …...