程序员人生 网站导航

[置顶] 华为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; }



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

最新技术推荐