本文共 2014 字，大约阅读时间需要 6 分钟。
题目
描述: 给定一个正整数N代表火车数量，0<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。题目类别: 栈 难度: 高级 运行时间限制: 10Sec内存限制: 128MByte阶段: 入职前练习 输入: 有多组测试用例，每一组第一行输入一个正整数N（0 <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* 题目：火车进站* 来源：华为上机-----------------------------------------*/#include#include #include #include using namespace std;void helper(string &inTrain,vector &outTrain,int index){ if(index == inTrain.size()){ return; }//if if(index == 0){ string outNum(""); outNum += inTrain[index]; outTrain.push_back(outNum); }//if else{ vector 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 }//for string 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 }//for swap(outTrain,newOutTrain); }//else helper(inTrain,outTrain,index+1);}vector TrainLeft(string inTrain){ vector result; int size = inTrain.size(); if(size <= 0){ result; }//if helper(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'; }//for vector 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<
转载地址：http://jwnka.baihongyu.com/