笔记 | P4387 【深基15.习9】验证栈序列 题解
题解
问题描述
给出两个序列 pushed 和 poped,分别表示入栈和出栈操作的顺序。我们需要判断给定的出栈序列是否可能对应于给定的入栈序列。如果可能,则输出 “Yes”;否则,输出 “No”。
解题思路
-
读取输入:读取询问次数
q和每次询问的入栈和出栈序列。 -
模拟栈操作:通过使用一个栈(
s1)和一个队列(s2),我们可以模拟栈的入栈和出栈操作。
a. 入栈操作:按顺序遍历入栈序列pushed,每次将元素推入栈s1。
b. 出栈操作:每次入栈后,检查栈顶元素是否与队列s2的前端元素相匹配。如果匹配,则从栈和队列中弹出元素,并继续检查下一个元素,直到不匹配或栈为空。 -
检查结果:如果所有出栈元素都被成功弹出,则输出 “Yes”。否则,输出 “No”。
-
清理数据结构:为下一次查询准备,确保栈和队列为空。
原始代码的错误
原始代码中的错误在于缺乏对连续出栈操作的处理。在模拟过程中,可能存在连续几个元素需要出栈的情况,但原始代码在每次入栈后只执行了一次出栈操作。这意味着对于某些入栈和出栈序列组合,代码可能在执行完所有的入栈操作后仍然留有未匹配的出栈元素。
错误代码部分:
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,分别表示入栈和出栈操作的顺序。我们需要判断给定的出栈序列是否可能对应于给定的入栈序列。如果可能,则输出 “Yes”;否则,输出 “No”。 解题思路 读取输入:读取询问…...
PyTorch中nn-XXX与F-XXX的区别
nn.XXX与F.XXX PyTorch中torch.nn**(以下简写为nn)中的模块和torch.nn.functional(以下简写为F)**中的模块都提供了常用的神经网络操作,包括激活函数、损失函数、池化操作等。它们的主要区别如下: nn中的…...
zookeeper集群和kafka的相关概念就部署
目录 一、Zookeeper概述 1、Zookeeper 定义 2、Zookeeper 工作机制 3、Zookeeper 特点 4、Zookeeper 数据结构 5、Zookeeper 应用场景 (1)统一命名服务 (2)统一配置管理 (3)统一集群管理 (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…...
微信小程序中的分包使用介绍
一、分包的好处 可以优化小程序首次启动的下载时间 在多团队共同开发时可以更好的解耦协作 主包:放置默认启动页面/TabBar 页面,公共资源/JS 脚本 分包:根据开发者的配置进行划分 限制:所有分包大小不超过 20M,单…...
【云原生】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屏幕渲染有两种方式:产生离屏渲染的原因:既然离屏渲染这么耗性能,为什么有这套机制呢?什么情况会离屏渲染?既然离屏渲染这么不好,为什么我们还要强制开启呢?如何避免离屏渲染?…...
基于人工智能的中医图像分类系统设计与实现
华佗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 避免列表被遮挡住一部分(底部是浮窗的时候,需要动态的现实隐藏) <!DOCTYPE html> <html lang"en"&…...
解密HTTP代理爬虫中的IP代理选择与管理策略
在当今数据驱动的世界中,HTTP代理爬虫作为一项重要的数据采集工具,其成功与否往往取决于IP代理的选择与管理策略。作为一家专业的HTTP代理产品供应商,我们深知IP代理在数据采集中的重要性。在本文中,我们将分享一些关于HTTP代理爬…...
pytorch入门
详细安装教程和环境配置可以看:Python深度学习:安装Anaconda、PyTorch(GPU版)库与PyCharm_哔哩哔哩_bilibili 跟学课程:B站我是土堆 pytorch中两个实用函数: dir():打开 help():说明书…...
Redis | 主从模式
Redis | 主从模式 1. 简介 Redis主从模式(Replication)是Redis提供的一种数据备份和高可用性解决方案。通过主从复制,可以将一个Redis服务器的数据复制到其他多个从服务器,从而实现数据的备份和读写分离,提高系统的性…...
C# Blazor 学习笔记(8):row/col布局开发
文章目录 前言相关文章代码row和col组件B_rowB_col结构 使用 前言 可能是我用的element ui和 uView这种第三方组件用的太多了。我上来就希望能使用这些组件。但是目前Blazor目前的生态其实并不完善,所以很多组件要我们自己写。 我们对组件的要求是 我们在组件化一共…...
金融供应链智能合约 -- 智能合约实例
前提 Ownable:监管者合约,有一个函数能转让监管者。 SupplyChainFin:供应链金融合约,银行、公司信息上链,公司和银行之间的转账。 发票:记录者交易双方和交易金额等的一种记录数据。如:我在超市买了一瓶水,超市给我开了一张发票。 Ownable // SPDX-…...
论文《Contrastive Meta Learning with Behavior Multiplicity for Recommendation》阅读
论文《Contrastive Meta Learning with Behavior Multiplicity for Recommendation》阅读 论文概况论文主要贡献Background & Motivation方法论单行为图神经网络(Behavior-aware GNN)多行为对比学习元对比编码模型训练 实验部分论文总结 论文概况 今…...
K8S 部署 RocketMQ
文章目录 添加模板部署本地访问 集群使用 kubesphere 作为工具 添加模板 添加 helm 模板 helm repo add rocketmq-repo https://helm-charts.itboon.top/rocketmq helm repo update rocketmq-repo编写 value.yaml 文件 配置主从节点的个数,例子为单节点 broker:…...
[Docker]入门之docker-compose
一,Docker-compose简介 1,Docker-compose简介 Docker-Compose项目是Docker官方的开源项目,负责实现对Docker容器集群的快速编排。 Docker-Compose将所管理的容器分为三层,分别是工程(project),…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
