首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。 比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因
输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。 比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因
admin
2019-03-29
61
问题
输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。
比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列:push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
选项
答案
///////////////////////////////////////////////////////////////////////////// // Given a push order of a stack, determine whether an array is possible to // be its corresponding pop order // Input: pPush - an array of integers, the push order // pPop - an array of integers, the pop order // nLength - the length of pPush and pPop // Output: If pPop is possible to be the pop order of pPush, return true. // Otherwise return false ///////////////////////////////////////////////////////////////////////////// bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength) { bool bPossible = false; if(pPush && pPop && nLength > 0) { const int *pNextPush = pPush; const int *pNextPop = pPop; // ancillary stack std::stack
stackData; // check every integers in pPop while(pNextPop - pPop < nLength) { // while the top of the ancillary stack is not the integer // to be poped, try to push some integers into the stack while(stackData.empty() || stackData.top() != *pNextPop) { // pNextPush == NULL means all integers have been // pushed into the stack, can’t push any longer if(!pNextPush) break; stackData.push(*pNextPush); // if there are integers left in pPush, move // pNextPush forward, otherwise set it to be NULL if(pNextPush - pPush < nLength - 1) pNextPush ++; else pNextPush = NULL; } // After pushing, the top of stack is still not same as // pPextPop, pPextPop is not in a pop sequence // corresponding to pPush if(stackData.top() != *pNextPop) break; // Check the next integer in pPop stackData.pop(); pNextPop ++; } // if all integers in pPop have been check successfully, // pPop is a pop sequence corresponding to pPush if(stackData.empty() && pNextPop - pPop == nLength) bPossible = true; } return bPossible; }
解析
这到题除了考查对栈这一基本数据结构的理解,还能考查我们的分析能力。
这道题的一个很直观的想法就是建立一个辅助栈,每次push的时候就把一个整数push进入这个辅助栈,同样需要pop的时候就把该栈的栈顶整数pop出来。
我们以前面的序列4、5、3、2、1为例。第一个希望被pop出来的数字是4,因此4需要先push到栈里面。由于push的顺序已经由push序列确定了,也就是在把4 push进栈之前,数字1,2,3都需要push到栈里面。此时栈里的包含4个数字,分别是1,2,3,4,其中4位于栈顶。把4 pop出栈后,剩下三个数字1,2,3。接下来希望被pop的是5,由于仍然不是栈顶数字,我们接着在push序列中4以后的数字中寻找。找到数字5后再一次push进栈,这个时候5就是位于栈顶,可以被pop出来。接下来希望被pop的三个数字是3,2,1。每次操作前都位于栈顶,直接pop即可。
再来看序列4、3、5、1、2。pop数字4的情况和前面一样。把4 pop出来之后,3位于栈顶,直接pop。接下来希望pop的数字是5,由于5不是栈顶数字,我们到push序列中没有被push进栈的数字中去搜索该数字,幸运的时候能够找到5,于是把5 push进入栈。此时pop 5之后,栈内包含两个数字1、2,其中2位于栈顶。这个时候希望pop的数字是1,由于不是栈顶数字,我们需要到push序列中还没有被push进栈的数字中去搜索该数字。但此时push序列中所有数字都已被push进入栈,因此该序列不可能是一个pop序列。
也就是说,如果我们希望pop的数字正好是栈顶数字,直接pop出栈即可;如果希望pop的数字目前不在栈顶,我们就到push序列中还没有被push到栈里的数字中去搜索这个数字,并把在它之前的所有数字都push进栈。如果所有的数字都被push进栈仍然没有找到这个数字,表明该序列不可能是一个pop序列。
转载请注明原文地址:https://kaotiyun.com/show/ZxmZ777K
0
程序员面试
相关试题推荐
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
.net中读写数据库需要用到哪些类?他们的作用
已知流行音乐为共享文件,搜索该文件夹。
设置拨号连接属性使得用户在使用拨号连接时需要使用我的Windows登录名和密码。
请恢复金山反垃圾邮件过滤列表。
将金山网镖应用程序规则列表中的应用程序QQ2009删除。
利用"开始"菜单的"运行"选项,启动"计算器"应用程序,计算器应用程序的标识为:c:\windows\system32\calc.exe(在"打开"中直接填写标识名)。
在Word中把一个已经打开的文件以新的名字存盘,起备份旧文件的作用,应选()命令。A.自动保存B.保存C.另存为D.全部保存
在页面设置中不可设置的内容为()A.页边距B.页面边框C.纸张大小D.页码
某商标注册人委托某印刷厂印制商标标识30万套,而印刷厂印制了36万套,该印刷厂多印制6万套商标标识的做法属(63)行为。
随机试题
男性,72岁。因胸痛24小时,诊断急性前壁心肌梗死入院,按常规接受药物治疗。入院后第4天,患者再次感心前区疼痛,持续约30分钟,查体心尖部内侧可闻及收缩中晚期高调、短促附加音伴收缩晚期杂音,与呼吸运动无关。(2015年第91题)该患者新出现的附加音最
A.绝对不应期B.相对不应期C.超常期D.低常期Na+通道失活的时相是
小王与小薇是同村的邻居,2009年5月,小王向小薇借款6000元,并写了借据,言明2010年5月之前还清。2010年7月,小薇向小王催要借款,并请同村的老李来劝说小王还款。在小薇向小王出示借条时,小王将欠条夺过并撕毁,小薇又将借条抢回并用胶水修补好,但借条
报关员调往其他企业从事报关工作,应持调入企业的证明文件及有效的报关员资格证书,向调入企业所在地海关申请办理重新注册手续。()
对不同的借款形式,印花税暂行条例规定了不同的计税方法。下列表述中,处理正确的有( )。
如果会计师事务所在拟承接乙公司财务报表审计业务时,发现由于时间关系很可能不能按时完成该审计业务,则会计师事务所的下列做法中恰当的是()。
《白石道人歌曲》一书中共有()首词调令、慢、近、犯。
根据一定标准和原则所划定的调整同一类社会关系的法律规范的总和被称为()。
公文写作之前要()。
和谐的世界应该是
最新回复
(
0
)