题目
描述:
给定一个正整数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之后的每一个数!
代码
#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(index == 0){
string outNum("");
outNum += inTrain[index];
outTrain.push_back(outNum);
}
else{
vector<string> newOutTrain;
int size = outTrain.size();
for(int i = 0;i < size;++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;
}
}
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);
}
}
swap(outTrain,newOutTrain);
}
helper(inTrain,outTrain,index+1);
}
vector<string> TrainLeft(string inTrain){
vector<string> result;
int size = inTrain.size();
if(size <= 0){
result;
}
helper(inTrain,result,0);
sort(result.begin(),result.end());
return result;
}
int main(){
int n;
while(cin>>n){
string train("");
int num;
for(int i = 1;i <= n;++i){
cin>>num;
train += num + '0';
}
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];
}
else{
cout<<" "<<trainNum[i][j];
}
}
cout<<endl;
}
}
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
华为机试一霸教你过华为机试演讲稿..pdf
华为OD机试(..75.rar
华为机试真题(非牛客网试练题)OD考试真题,不定期更新,文档含代码解答
华为机试一霸教你过华为机试.doc
华为机试一霸教你过华为机试。大菊厂招聘有三关,心理测试,机试,面试。
。。。
。。。
华为机试算法题总结 经验分享
华为机试oj练习题2014
华为机试一霸教你过华为机试e-18页.pdf
本人在准备2014年华为机试的时候,进行整理的,代码全部运行成功。如有错误,请大家见谅。
火车进站问题 给定一个正整数N代表火车数量,0,接下来输入火车入站的序列,一共N辆火车,每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。 输入: 有多组测试用例,每一组第一行输入一个正整数N(0...
华为OD系列--华为OD机试
华为机试题目100题练习题
华为机试成功归来,与小伙伴们分享下经验
大师兄教你如何过华为机试
贰壹贰叁零华为OD机试.pptx 华为OD机试.pptx 华为OD机试.pptx
里面有几十道华为历届考过的机试题,可供大家研究和参考,主要是里面的思想,只要理解透了里面的思想,非常有助于机试。
华为机试.md
2014重邮华为机试(2013.9.14和2013.9.15)一共三场的题目