首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入两个整数序列。其中一个序列表示栈的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
150
问题
输入两个整数序列。其中一个序列表示栈的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
程序员面试
相关试题推荐
删除串中指定的字符
输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
ASP.NET与ASP相比,主要有哪些进步?
在【站点管理器】中使用鼠标右键菜单方式,修改FTP站点名为:“video”的站点属性,使“video”的站点“启动过滤”功能,并区分大小写进行过滤。
利用“开始”菜单“所有程序”启动“计算器”应用程序。
Dreamweaver的编辑(Edit)菜单命令中,SelectAll表示______。A.将剪贴板拷贝至当前光标位置B.从文档中删除当前选区C.选取当前文档中所有元素D.使用HTML代码将当前选区拷贝到剪贴板
下列叙述中,不属于结构化程序设计方法的主要原则的是()。
下列有关break和continue语句的叙述中,正确的是________。
802.11n使用哪一类型的复用技术?A、空间复用B、OFDMC、DSSSD、FHSS
若某航空公司的飞机订票系统有n个订票终端,系统为每个订票终端创建一个售票终端的进程。假设Pi(i=1,2,…,n)表示售票终端的进程,Hj(j=1,2,…,m)表示公共数据区,分别存放各个航班的现存票数,Temp为工作单元。Pi进程的工作流程如图6-3所
随机试题
《拉奥孔》是______的雕塑作品。()
血吸虫病引起的肠道病变包括
女,56岁。剔牙后牙龈出血约1年。高血压病史10年,服用长效心痛定控制较平稳,从未牙周治疗。检查:全口口腔卫生差,牙石(++)~(+++),普遍龈乳头暗红肿大,半球形,覆盖牙面1/3,探诊易出血,漱后可止,PD4~8mm,多数牙I度松动,个别下前牙Ⅱ度松动
A.安氏Ⅰ类B.安氏Ⅱ类,Ⅰ分类C.安氏Ⅱ类,Ⅱ分类D.安氏Ⅲ类E.安氏Ⅲ类,亚类磨牙关系中性,前牙拥挤
患者,男性,38岁。因呼吸道感染伴咳嗽、发热到医院就诊,医嘱给予青霉素80万U肌内注射,每日2次。皮试后5分钟,患者出现胸闷、气急伴濒危感,面色苍白、出冷汗,患者可能发生
根据企业所得税法律制度的规定。下列各项中,属于不征税收入的有()。
保荐机构及其保荐代表人有权列席发行人的股东大会和股东会,但不得参加发行人的监事会。()
构成保险必须具备的要素包括()。
社会主义初级阶段的科学含义是()
下面关于PC机主板芯片组的叙述中,错误的是
最新回复
(
0
)