[华为机试练习题]13.火车进站

题目

描述:给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。题目类别: 栈 难度: 高级 运行时间限制: 10Sec内存限制: 128MByte阶段: 入职前练习 输入: 有多组测试用例，每一组第一行输入一个正整数N（0<N<10），第二行包括N个正整数，范围为1到9。输出: 输出以字典序排序的火车出站序列号，，每个编号以空格隔开，每个输出序列换行，具体见sample。样例输入: 31 2 3样例输出: 1 2 31 3 22 1 32 3 13 2 1

思路

1、若n=1那么就一种排列方式。2、n>1时先求出n-1的出栈顺序，再分开将n插入n-1之前，n-1之后和每一个n-1之后的每一个数！

代码

/*—————————————* 日期：2015-06-30* 作者：SJF0115* 题目：火车进站* 来源：华为上机—————————————–*/;void helper(string &inTrain,vector<string> &outTrain,int index){if(index == inTrain.size()){return;}//ifif(index == 0){string outNum(“”);outNum += inTrain[index];outTrain.push_back(outNum);}//ifelse{vector<string> newOutTrain;// 出栈序列int size = outTrain.size();// 第index辆火车进栈for(int i = 0;i < size;++i){// 第i个出栈序列int count = outTrain[i].size();// 寻找前一个进栈的火车下标int targetIndex;for(int j = 0;j < count;++j){if(inTrain[index-1] == outTrain[i][j]){targetIndex = j;break;}//if}//forstring tmp(outTrain[i]);for(int j = targetIndex;j <= count;++j){tmp.insert(tmp.begin()+j,inTrain[index]);newOutTrain.push_back(tmp);tmp.erase(tmp.begin()+j);}//for}//forswap(outTrain,newOutTrain);}//elsehelper(inTrain,outTrain,index+1);}vector<string> TrainLeft(string inTrain){vector<string> result;int size = inTrain.size();if(size <= 0){result;}//ifhelper(inTrain,result,0);sort(result.begin(),result.end());return result;}int main(){int n;//freopen(“C:\\Users\\Administrator\\Desktop\\c++.txt”,”r”,stdin);while(cin>>n){string train(“”);int num;for(int i = 1;i <= n;++i){cin>>num;train += num + ‘0’;}//forvector<string> trainNum = TrainLeft(train);// 输出int size = trainNum.size();for(int i = 0;i < size;++i){int count = trainNum[i].size();for(int j = 0;j < count;++j){if(j == 0){cout<<trainNum[i][j];}//ifelse{cout<<” “<<trainNum[i][j];}//else}//forcout<<endl;}//for};}

时光的消化是这样的缓慢。虽然这也仅仅是无处可说的委屈。而不是痛苦。