笔记 | 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),…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
