牛客NC272 栈的压入、弹出序列

描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

示例1

输入：

[1,2,3,4,5],[4,5,3,2,1]

返回值：

true

说明：

可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true

示例2

输入：

[1,2,3,4,5],[4,3,5,1,2]

返回值：

false

说明：

由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

首先对这个问题进行分析，使用两个数组来表示栈的压入和弹出序列，对于示例1，有：

压入序列：

1

2

3

4

5

弹出序列：

4

5

3

2

1

由栈的后入先出（LIFO）特性和弹出序列可知，如果要使 4 这个元素第一个弹出，那么在弹出 4 时，这个元素一定在栈顶。又由栈的操作受限特性和压入序列可知，要使 元素4 在栈顶并且成为此次弹出元素，那么在元素4之前并且尚未入栈的元素一定要先入栈，并且在此过程中不能有出栈操作，否则4将不是本次弹出元素。所以，在4出栈之前，元素1，2，3，4都需要入栈，接着弹出栈顶元素，栈中剩余元素为1，2，3。经过上述过程，弹出序列中的第一个元素是合法的，下面依照上述过程讨论剩下的序列（用绿色表示栈中元素，红色表示已经合法的弹出序列）。

1，2，3，4入栈：

1

2

3

4

4出栈与弹出序列的第一个元素匹配（用紫色表示出栈）： 

1

2

3

4

4

5

3

2

1

这时栈中只剩元素1，2，3：

1

2

3

接下来要使元素5出栈，由于这时栈中本身已有元素，所以5可能位于栈顶，也可能还未入栈，如果5位于栈顶，则栈顶元素出栈与弹出序列中的5匹配，否则，根据刚才的分析，需要根据压入序列对尚未入栈的元素入栈，直到5入栈。如果发现栈顶元素不为5并且后续入栈的所有元素都不为5，那么说明这个弹出序列不是合法的栈的弹出序列。

所以，栈顶元素为3，不等于5，那么压入序列中的剩余元素依次入栈直到5入栈：

1

2

3

5

接下来，5出栈并与弹出序列匹配：

1

2

3

5

4

5

3

2

1

此时，栈中剩余元素为1，2，3

1

2

3

到此，压入序列中的所有元素已经入栈，所以接下来只有出栈操作，显然，栈的出栈顺序与弹出序列的剩余元素顺序相同，所以这个弹出序列是合法的。

根据上述分析过程就可以分析出示例2是一个非法序列，首先1，2，3，4入栈，接着4，3出栈；5入栈，5出栈；最后可以发现，如果1要比2先出栈，那么1必须在2后面入栈，这显然是不可能的。

下面给出这道题的代码：

typedef struct stack {int arr[1000];int topofstack;
} stack;int IsEmpty(stack* s) {return s->topofstack == -1;
}void push(stack* s, int k) {s->arr[++s->topofstack] = k;
}int top(stack* s) {return s->arr[s->topofstack];
}int pop(stack* s) {return s->arr[s->topofstack--];
}//此行以上均是栈的实现//pushV表示压入序列，popV表示弹出序列
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {// write code herestack* s = (stack*)malloc(sizeof(stack));//创建一个栈if (s == NULL) {printf("内存分配失败\n");return false;}s->topofstack = -1;int tmp[1000];//为了方便理解，使用一个临时数组来存放在压入序列下的真实弹出序列int ptmp=-1;int ppush = 0; //用来记录当前对比的输入序列的位置int ppop = 0; //记录当前对比的输出序列的位置while (ppop < popVLen && ppush < pushVLen) {//如果有一个指针越界就停止循环if (IsEmpty(s)) {//当栈为空时，不需要考虑栈顶元素if (pushV[ppush] != popV[ppop]) {//压入序列中的元素不等于弹出序列中的元素push(s, pushV[ppush]);//就将压入序列中的这个元素入栈，并且压入序列的指针向后移动一位，直至找到与弹出序列此元素相同的元素ppush++;} else {//找到相同的元素tmp[++ptmp]=popV[ppop];//将其弹出并保存在临时数组中ppush++;//两个序列的指针均向后移动一位ppop++;continue;}} else {//当栈不为空时，需要考虑栈顶元素if (top(s) == popV[ppop]) {//当栈顶元素等于此次需要对比的弹出序列的元素tmp[++ptmp]=popV[ppop];//将其弹出，并保存在临时数组中ppop++;//弹出序列的指针向后移动一位pop(s);} else {//其余逻辑与上面相同if (pushV[ppush] != popV[ppop]) {push(s, pushV[ppush]);ppush++;} else {tmp[++ptmp]=popV[ppop];ppop++;ppush++;continue;}}}}//这里可以使用临时数组与弹出序列比较，如果相同则合法，否则非法//还可以不使用临时数组if(IsEmpty(s)){//当栈为空时，如果弹出序列对比完成，说明是合法的，因为只有两个序列中元素相同时才会进行出栈操作，所以实际上当栈为空时，序列一定合法，可以不需要判断ppopif(ppop==popVLen)return true;elsereturn false;}else{//当栈不为空时，根据代码的逻辑，ppop一定不会越界if(ppop==popVLen)//所以这层判断也可以删掉return false;else{while(!IsEmpty(s)){if(pop(s)!=popV[ppop++])return false;}}}return true;
}

查看全文

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

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

相关文章：

牛客NC272 栈的压入、弹出序列

描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就……

编程日记2023/4/12 20:52:22

COCO数据集相关知识

COCO整个人体关键点数据集：https://github.com/jin-s13/COCO-WholeBody…

编程日记2023/4/12 20:52:08

C# 浅析并行任务同步机制——Interlocked

一、定义：为多个线程共享的变量提供原子操作。 i和i– 这种原子操作，都不是线程安全的，它的操作包括从内存中读取一个值，给值递增或递减，然后再将它存储回内存。这些操作都有可能会被线程调度器打断。 以线程安全的方式……

编程日记2023/4/12 20:51:56

【C++】继承—上（继承的引入及使用详解、切片赋值和作用域）

前言： 我们在学习C的第一节课就了解到C是一门面向对象的语言，面向对象的语言有三大特性：
封装、继承、多态 此前我们学习了封装，比如模拟实现vector，string或者迭代器等，不仅有利于我们的维护和管理&#……

编程日记2023/4/12 20:51:36

53 openEuler搭建PostgreSQL数据库服务器-管理数据库

文章目录53 openEuler搭建PostgreSQL数据库服务器-管理数据库53.1 创建数据库创建数据库示例53.2 选择数据库选择数据库示例53.3 查看数据库查看数据库示例53.4 删除数据库删除数据库示例53.5 备份数据库备份数据库示例53.6 恢复数据库恢复数据库示例53 openEuler搭建PostgreSQ……

编程日记2023/4/12 20:51:26

【 C语言运算符优先级及结合方向】

C语言运算符优先级及结合方向 🍉 C语言曾经有一段极简风，这些核心代码不用括号调整优先级，而且当下还在linux 核心中保存，所以还是要把优先级整理一下。 扩建点龙眼 单目右先算 移位在比较 等亦不等闲 位与异或或 双逻与或观 三目……

编程日记2023/4/12 20:51:15

华为手表开发：WATCH 3 Pro（16）传感器订阅气压

华为手表开发：WATCH 3 Pro（16）传感器订阅气压初环境与设备气压传感器介绍与说明鸿蒙开发文件夹：文件新增展示的文本标记index.hmlindex.cssindex.js初
希望能写一些简单的教程和案例分享给需要的人
鸿蒙可穿戴开发
环境与设备 ……

编程日记2023/4/12 20:51:02

4.12每日一练

题目：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数……

编程日记2023/4/12 20:50:52

修改Mtatlab中ASAP2相关配置文件生成自定义A2L文件

一、自定义ASAP2文件的内容 　　ASAP2相关的TLC文件使您可以自定义从Simulink模型生成的ASAP2文件的格式。 大多数自定义是通过修改或添加matlabroot / toolbox / rtw / targets / asap2 / asap2 / user（open）文件夹中包含的文件来完成的。 此文中将此文……

编程日记2023/4/12 20:50:49

Matlab替换A2L文件中的地址生成完整A2L文件的方法小结

引言 　　基于模型的开发（ＭＢＤ）方式在汽车电子嵌入式软件行业中发展迅速。关于其Ｎ多好处不去瞎说了，自然有mathwork的工作人员去宣传。基于模型的开发在模型生成代码的过程中，如果软件……

编程日记2023/4/12 20:50:49

深度分析Palantir的投资价值，Palantir2023年将实现强劲反弹?

来源：猛兽财经 作者：猛兽财经 在本文中，猛兽财经将通过对Palantir的股票关键指标、商业模式、盈利能力、影响Palantir2023年股价的关键利好因素等方面，对Palantir进行全面、深度的分析。 Palantir股票的关键指标 自从Palantir(PL……

编程日记2023/4/16 15:02:09

Pandas入门实践2 -数据处理

为了准备数据进行分析，我们需要执行数据处理。在本节中，我们将学习如何清理和重新格式化数据（例如，重命名列和修复数据类型不匹配）、对其进行重构/整形，以及对其进行丰富（例如，离散化……

编程日记2023/4/16 15:01:42

一、lua基础知识1

一、lua 的数据类型
–类型 a1; –number print(type(a)) –number b"HelloWorld"; print(type(b)) –string 两种数据类型 ctrue; print(type(c)) –boolean true 或者 false d print; d("HelloWorld"); print(type(d)); –function类型 ……

编程日记2023/4/16 15:01:28

二、lua语言基础2

1.lua的类型有哪些？答：lua的数据类型有：number,string,nil function,table,thread,userdata(用户自定义的类型),boolean（布尔类型) 2.什么是尾调用，尾调用有什么优点尾调用：在一个函数的最后一步开始调用另……

编程日记2023/4/16 15:01:27

quick-cocos2dx-luaUI控件讲解

–MyApp部分 require("config") require("cocos.init") require("framework.init") local MyApp class("MyApp", cc.mvc.AppBase) function MyApp:ctor() MyApp.super.ctor(self) end function MyApp:run() cc.FileUti……

编程日记2023/4/16 15:01:27

quick-cocos2dx lua语言讲解 (动作，定时器，触摸事件，工程的类的讲解)

–MainScene部分
— display.newScene 创建一个场景 — 在quick里面我们的控件、精灵 一般是加载到场景上的 local MainScene class("MainScene", function() return display.newScene("MainScene") end) function MainScene:ctor() –创……

编程日记2023/4/16 15:01:26

使用quick-cocos2dx-lua 实现的小游戏（包含碰撞检测，触屏发子弹）

–主界面local MainScene class("MainScene", function()return display.newScene("MainScene")end)ON true;function MainScene:ctor()local bg cc.Sprite:create("main_background.png");bg:setScale(2);bg:setPosition(display.cx,display……

编程日记2023/4/16 15:01:26

cocos2d-js 中scrollview详解

/****
开头的一些废话：
1、多思考，善于思考
2、懂得变通
3、多多查询API首先复制一段 API中的源码：（UIScrollView.js）这段代码可以看出 scrollview
中的容器是一个node，并且他的位置是：代码最后……

编程日记2023/4/16 15:01:24

cocos2d-js中的回调函数中世界坐标系和节点坐标系的相互转换

世界坐标系和节点坐标系都是OPENGL 坐标系 1、世界坐标系原点就是屏幕的左下角； 2、节点坐标系的原点就是一个节点的左下角； 3、两个坐标系可以通过已经写好的cocosAPI进行想换转换； 4、所有的节点需要转为一个节点上或者是统一的世界坐标系……

编程日记2023/4/16 15:01:24

通过JavaScript实现漂浮

<html>
<head><meta http-equiv"Content-Type" content"text/html"; charset"gb2312" /><title>漂浮广告</title><style type"text/css">div{position:absolute;}</style>
</head>
&……

编程日记2023/4/16 15:01:23