您当前位置：首页 > php开源 > 综合技术 > [置顶] 华为OJ铁路栈问题（分析+源码）

[置顶] 华为OJ铁路栈问题（分析+源码）

来源：程序员人生发布时间：2015-05-27 08:29:20 阅读次数：6194次

题目标题：铁路栈问题

铁路的调度站以下：

火车编号为：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; }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 高仿微信多图选择

下一篇 JAVA 反射

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点