[置顶] 华为OJ铁路栈问题（分析+源码）
栏目：综合技术时间：2015-05-27 08:29:20
题目标题：铁路栈问题
铁路的调度站以下：
火车编号为：1~9，且不重复。
如：编号分别为“1”、“2”、“3”、“4”、“5”的5个火车顺序进站，那末进站序列为“12345”，全部进站后再顺序出站，则出站序列为“54321”，如果先进1,2，然后2出站，然后1出站，然后再3进站、出站，4进站、出站，5进站、出站，那末出站序列就为21345.
详细描写：
int JudgeTrainSequence (int maxNum, char *pOutSeq);
输入参数：
int maxNum：进站的火车最大编号
char* pOutSeq：使用字符串表示火车出站序列
输出参数（指针指向的内存区域保证有效）：
无。
返回值：
Int: 根据输入的进站序列判断，如果输入的出站序列是可能的，返回1，否则返回0；
分析+代码：
这个题目已提示是栈的问题，有点数据结构基础的娃儿就知道这个入栈出栈的操作，关键的地方在于对某1个序号n入栈，则如果有小于n的数还没有出栈，那末它们出栈以后必定是降序排列的。对每个数都是如此，但是对本题太过简单，最快最暴力的方法就是摹拟栈操作，这也是ACMer知道的经典的数据结构算法，你可以利用STL里已定义好的stack操作，对本题由于入栈从1开始编号，而且是顺序的，也就是说入栈序列是不变的，所以用个数组就能够摹拟它，首先编号1入栈（放入数组每个元素），然后从数组确当前位置开始向前走，顺次比较和出栈序列的相应元素是不是相等，直到不相等的时候，放入编号2.....类似，代码很简单，容易看懂，时间复杂度是O(n^2)，没时间优化，欢迎回帖交换~
//#include<iostream>
//#include<string>
//#include<algorithm>
//#include<cmath>
//#include<vector>
//#include<stack>
//#include<iomanip>
//using namespace std;
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
/*
详细描写：
int JudgeTrainSequence (int maxNum, char *pOutSeq);
输入参数：
int maxNum：进站的火车最大编号
char* pOutSeq：使用字符串表示火车出站序列
输出参数（指针指向的内存区域保证有效）：
无。
返回值：
Int: 根据输入的进站序列判断，如果输入的出战序列是可能的，返回1，否则返回0；
*/
int JudgeTrainSequence (int maxNum, char *pOutSeq)
{
if(strlen(pOutSeq)!=maxNum)return 0;
char *ss=(char *)malloc(sizeof(char));
int i,j=0,k=0;
for(i=1;i<=maxNum;i++)
{
ss[j]=i+'0';
while(ss[j]==pOutSeq[k] && k<maxNum){
k++;
j--;
}
if(k==maxNum)return 1;
j++;
}
return 0;
}
int main()
{
char *ss=NULL;
printf("%d
",JudgeTrainSequence (5, "53421"));
// cout<<JudgeTrainSequence (5, "53421")<<endl;//12345;34215
return 0;
}
------分隔线----------------------------
------分隔线----------------------------