UVa514 解析:火车车厢重排序问题的模拟栈实现

来源:UVa514 铁轨 Rails。

这是一个火车车厢重排序的问题,通过模拟栈操作的算法实现。这种算法非常适用于具有栈结构特性的问题,比如括号匹配货物堆放编译器中语法检查。本文给出了C++的两种代码实现和Python的一种实现。

题目描述

某城市有一个火车站,铁轨铺设如图。有 n ( n < = 1000 ) n(n<=1000) n(n<=1000) 节车厢从A方向驶入车站,按进站的顺序编号为 1 ~ n 1~n 1n 。你的任务是判断是否能让他们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如,出站顺序 5 4 1 2 3 是不可能的,但 5 4 3 2 1 是可能的。

在这里插入图片描述
为了重组车厢,你可以借助中转站C。这是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶出C。对于每节车厢,一旦从A移入C,就不能返回A了;一旦从C移入B,就不能返回C了。也就是说,在任意时刻,只有两种选择:A到C和C到B。

输入

对于每一组数据,第一行是一个整数 N N N 。接下来若干行数据,每行 N N N 个数,代表 1 1 1 ~ N N N 车厢的出站顺序,每组最后一行数据只有一个整数 0 0 0

最后一组数据只有包含 0 0 0 的一行。

输出

对于每一组输入数据,除了第一行和最后一行,对于其它每行数据,如果是可能的出站顺序,则输出 Yes,否则输出 No。 每组最后输出空行。

最后一组数据的 N = 0 N=0 N=0 ,不输出。

输入样例

5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0

输出样例

Yes
NoYes

算法分析

核心算法思想是 借助栈来模拟火车车厢的出站过程,从而判断给定的出栈顺序是否可行。以下是该算法的详细分析。

问题描述

给定一列从编号 1n 的车厢,它们按顺序进入一个车站。车站的设计允许车厢进入一个中转站(即栈),但由于栈的后进先出(LIFO)性质,进入栈的车厢必须按相反的顺序出栈。我们希望判断给定的车厢出栈顺序是否可能实现。

算法思想

算法利用栈来模拟车站中转站的作用。对于给定的车厢出栈顺序,我们需要模拟车厢的进出站过程,遵循以下操作:

  1. 直接出站:如果当前车厢编号等于目标出栈顺序的当前编号,则该车厢无需进入中转站,直接出站。
  2. 中转站出栈:如果栈顶车厢符合当前的目标出栈顺序,则该车厢出栈,进入最终出站顺序。
  3. 中转站入栈:如果当前车厢编号不等于目标出栈顺序的当前编号,则将车厢推入栈中。
  4. 无解判定:当没有更多车厢可以入栈,且栈顶车厢不符合目标出栈顺序时,判断出栈顺序不可能实现。

算法复杂度分析

  • 时间复杂度 O ( n ) O(n) O(n),因为每个车厢最多只会入栈一次、出栈一次。
  • 空间复杂度 O ( n ) O(n) O(n),栈的最大空间需求为 n

算法适用场景

这种模拟栈操作的算法非常适用于具有栈结构特性的问题,比如:

  • 括号匹配(有效的括号序列)。
  • 货物堆放问题(货物按特定顺序出栈)。
  • 编译器中语法检查(例如词法分析器的匹配)。

总结

该算法利用栈结构的后进先出(LIFO)特点,以模拟火车车厢重排序问题,能够高效地判断是否可以通过合法的中转站操作实现目标出栈顺序。


代码实现

C++ 代码

1. 方法一
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/10297.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

ENSP OSPF和BGP引入

路由协议分为&#xff1a;内部网关协议和外部网关协议。内部网关协议用于自治系统内部的路由&#xff0c;包括&#xff1a;RIP和OSPF。外部网关协议用于自治系统之间的路由&#xff0c;包括BGP。内部网关协议和外部网关协议配合来共同完成网络的路由。 BGP:边界网关路由协议(b…

华为OD机试真题-矩形绘制

题目描述 实现一个简单的绘图模块&#xff0c;绘图模块仅支持矩形的绘制和擦除 当新绘制的矩形与之前的图形重善时&#xff0c;对图形取并集 当新擦除的矩形与之前的图形重善时&#xff0c;对图形取差集 给定一系列矩形的绘制和擦除操作&#xff0c;计算最终图形的面积。下…

Android下的系统调用 (syscall),内联汇编syscall

版权归作者所有&#xff0c;如有转发&#xff0c;请注明文章出处&#xff1a;https://cyrus-studio.github.io/blog/ 什么是系统调用 (syscall) 系统调用是操作系统提供给应用程序的一组接口&#xff0c;允许用户空间程序与内核进行交互。 在 Android&#xff08;基于 Linux …

初始JavaEE篇 —— 网络编程(2):了解套接字,从0到1实现回显服务器

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a;JavaEE 目录 TCP 与 UDP Socket套接字 UDP TCP 网络基础知识 在一篇文章中&#xff0c;我们了解了基础的网络知识&#xff0c;网络的出…

【月之暗面kimi-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …

架构师备考-概念背诵(软件工程)

软件工程 软件开发生命周期: 软件定义时期:包括可行性研究和详细需求分析过程,任务是确定软件开发工程必须完成的总目标,具体可分成问题定义、可行性研究、需求分析等。软件开发时期:就是软件的设计与实现,可分成概要设计、详细设计、编码、测试等。软件运行和维护:就是…

[FBCTF 2019]rceservice 详细题解

知识点: json字符串 PHP正则表达式元字符 PCRE回溯机制绕过正则表达式 %0a 换行符绕过正则表达式(详细讲解) 提示 Enter command as JSON 题目还有一个附件,打开是index.php文件源码 <?php putenv(PATH/home/rceservice/jail); if (isset($_REQUEST[cmd])) {$json $_…

【竞技宝】DOTA2-梦幻联赛S24:圣剑美杜莎强拆基地终结比赛

北京时间11月9日,DOTA2的梦幻联赛S24继续进行。本日迎来第二阶段的B组二、三名加赛PARI对阵spirit。本场比赛双方前两局战至1-1平,决胜局同样是难分胜负打到了六十分钟之后,关键时刻spirit主动出击,圣剑美杜莎强拆基地成功一波结束比赛,最终spirit让一追二击败PARI。以下是本场…

计算机的错误计算(一百四十九)

摘要 探讨 MATLAB 中 的计算精度问题。当 为含有小数的大数或整数附近数时&#xff0c;输出会有错误数字。 例1. 已知 计算 直接贴图吧&#xff1a; 另外&#xff0c;16位的正确值分别为 0.6374239897486897e0、-0.6613118653236519e0、0.3769911184298822e-5 与…

力扣 多数元素

用了排序跟抵消。 题目 由题可知&#xff0c;多数元素是指在数组中出现次数大于一半的元素&#xff0c;且总是存在多数元素。不难想到&#xff0c;把数组排序后&#xff0c;这个数组的中间数一定是这个要找的元素。 用了sort排序&#xff0c;时间复杂度O&#xff08;nlogn&am…

Oracle OCP认证考试考点详解082系列11

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 51. 第51题&#xff1a; 题目 51.View the Exhibit and examine the description of the tables You execute this SQL statement Whi…

前端小知识:如何理解这个新特性 ?= 运算符

在日常的JavaScript开发中&#xff0c;我们经常会处理一些异步任务&#xff0c;避免代码出错&#xff0c;这时候常见的工具就是 try-catch 块和 async-await 语法。这些工具虽好&#xff0c;但当我们代码量一多&#xff0c;整个代码结构可能会显得很臃肿&#xff0c;阅读起来也…

Redhat切换其他源

1. 效果图 2. 安装 RPM 包的命令 rpm -ivh --nodeps --force epel-release-latest-8.noarch.rpm rpm -ivh --nodeps --force yum-4.7.0-4.el8.noarch.rpm rpm -ivh --nodeps --force yum-utils-4.0.21-3.el8.noarch.rpm 3. 修改默认源 vi /etc/yum.repos.d/redhat.repo[BaseO…

如何使用OpenCV和Python进行相机校准

《------往期经典推荐------》 一、AI应用软件开发实战专栏【链接】 项目名称项目名称1.【人脸识别与管理系统开发】2.【车牌识别与自动收费管理系统开发】3.【手势识别系统开发】4.【人脸面部活体检测系统开发】5.【图片风格快速迁移软件开发】6.【人脸表表情识别系统】7.【…

「Mac畅玩鸿蒙与硬件32」UI互动应用篇9 - 番茄钟倒计时应用

本篇将带你实现一个番茄钟倒计时应用&#xff0c;用户可以设置专注时间和休息时间的时长&#xff0c;点击“开始专注”或“开始休息”按钮启动计时&#xff0c;应用会在倒计时结束时进行提醒。番茄钟应用对于管理时间、提升工作效率非常有帮助&#xff0c;并且还会加入猫咪图片…

Qt/C++ 海康SDK开发示例Demo

*** 工业相机在机器视觉中起到关键作用&#xff0c;本文基于海康 SDK 详细解读了设备连接与控制的各个步骤。内容涵盖设备枚举、句柄创建、图像采集回调以及设备异常处理&#xff0c;帮助开发者快速理解如何通过代码控制相机&#xff0c;实时采集并处理图像数据。*** 1. 搜索并…

探索 Python 的新边疆:sh 库的革命性功能

文章目录 **探索 Python 的新边疆&#xff1a;sh 库的革命性功能**第一部分&#xff1a;背景介绍第二部分&#xff1a;sh 库是什么&#xff1f;第三部分&#xff1a;如何安装 sh 库&#xff1f;第四部分&#xff1a;简单库函数使用方法1. 执行 ls 命令2. 使用 grep 搜索文件内容…

深度学习——前向传播与反向传播、神经网络(前馈神经网络与反馈神经网络)、常见算法概要汇总

文章目录 &#x1f33a;深度学习面试八股汇总&#x1f33a;前向传播与反向传播前向传播&#xff08;Forward Propagation&#xff09;反向传播&#xff08;Back Propagation&#xff09;总结 神经网络简介结构类型前馈神经网络&#xff08;Feedforward Neural Network, FFNN&am…

MySQL 中的索引下推功能

看到索引&#xff0c;应该大家都可以联想到这个是和查询效率有关系的&#xff0c;既然有这个功能&#xff0c;那么那句古话说的好啊&#xff1a;存在即合理。那么这个就是说有了这个功能&#xff0c;可以提升查询效率。 什么是索引下推 我们先有一个大概的理解&#xff1a;在…

#渗透测试#SRC漏洞挖掘# 操作系统-Linux系统之基本命令、资源耗尽脚本编写

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…