题解 | #火车进站#

火车进站

http://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109

qin非空就把qin.front入栈st并qin.pop
当检测栈非空且st.top==qout.front,就st.pop; qout.pop;
最终检测栈空,则出栈序列合法,不空则出栈序列非法
注意使用next_permutation做排序时要先对原序列进行升序排序

总代码:
/*hj77火车进站
思路:全排列,再判断全排列顺序是否可以由入栈顺序构成
*/
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
int checkstack(int in[],int out[],int n)//参数为入栈序列和待检查序列   长度 
{
    queue<int>qin;
    queue<int>qout;
    stack<int>st;
    for(int i=0;i<n;i++)//入栈顺序队列 
    {
    	qin.push(in[i]);
	}
    for(int i=0;i<n;i++)//出栈顺序队列 
    {
    	qout.push(out[i]);
	}
	while(!qin.empty())
	{
		st.push(qin.front());//进入检测栈 
		qin.pop();
		while(!st.empty()&&st.top()==qout.front())
		{
			st.pop();
			qout.pop();
		}
	}
	if(st.empty()) return 1;
	else return 0;
}
int main()
{
    int n;
    cin>>n;
    int a[10];
    for(int i=0;i<n;i++) cin>>a[i];    
    int b[10];
    for(int i=0;i<n;i++) b[i]=a[i]; 
    sort(b,b+n);
    do
    {
    	if(checkstack(a,b,n))//出栈顺序合法 
    	{
    		for(int i=0;i<n;i++) cout<<b[i]<<" ";
        	cout<<endl;
		}        
    }while(next_permutation(b,b+n));
}


全部评论

相关推荐

06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
10
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务