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

题目

描写叙述: 给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列。一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。

题目类别: 栈 难度: 高级 执行时间限制: 10Sec 内存限制: 128MByte 阶段: 入职前练习 输入: 有多组測试用例。每一组第一行输入一个正整数N（0<N<10），第二行包含N个正整数，范围为1到9。 输出: 输出以字典序排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行。详细见sample。

例子输入: 3 1 2 3 例子输出: 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1

思路

1、若n=1那么就一种排列方式。

2、n>1时先求出n-1的出栈顺序，再分开将n插入n-1之前，n-1之后和每个n-1之后的每个数。

代码

/*--------------------------------------- * 日期：2015-06-30 * 作者：SJF0115 * 题目：火车进站 * 来源：华为上机 -----------------------------------------*/ #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; void helper(string &inTrain,vector<string> &outTrain,int index){ if(index == inTrain.size()){ return; }//if if(index == 0){ string outNum(""); outNum += inTrain[index]; outTrain.push_back(outNum); }//if else{ 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 }//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<string> TrainLeft(string inTrain){ vector<string> 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<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]; }//if else{ cout<<" "<<trainNum[i][j]; }//else }//for cout<<endl; }//for }//while return 0; }

转载于:https://www.cnblogs.com/bhlsheji/p/5269215.html

相关资源：数据结构—成绩单生成器