华为机试HJ77 火车进站
首先看一下题
描述
给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
要求输出所有火车出站的方案，以字典序排序输出。
数据范围： 1≤n≤10
进阶：时间复杂度：O(n!) ，空间复杂度： O(n)
输入描述：
第一行输入一个正整数N（0 < N <= 10），第二行包括N个正整数，范围为1到10。
输出描述：
输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。
示例1
输入：
3 1 2 3输出：
1 2 3 1 3 2 2 1 3 2 3 1 3 2 1说明：
第一种方案：1进、1出、2进、2出、3进、3出 第二种方案：1进、1出、2进、3进、3出、2出 第三种方案：1进、2进、2出、1出、3进、3出 第四种方案：1进、2进、2出、3进、3出、1出 第五种方案：1进、2进、3进、3出、2出、1出 请注意，[3,1,2]这个序列是不可能实现的。
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.给定一个正整数N代表火车数量，N大于0小于10，
2.接下来输入火车入站的序列，
3.一共N辆货车，每辆火车以数字1-9编号，
4.火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出战了，先进站的才能出站。
5.要求输出所有火车出站的方案，以字典序排列输出
6.数据范围：n大于等于1小于等于10
7.进阶：时间复杂度：O（n！），空间复杂度：O（n）
8.输入描述：第一行输入一个正整数N（0 < N <= 10)，第二行包括N个正整数，范围为1到10.
9.输出描述：输出以字典序从小到大排序的火车出战序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。
二、解题思路
1.引入标准输入输出库和字符串处理库
#include <stdio.h>
#include <string.h>
2.定义一个const int sz = 12;用来限制数组的大小
int n, in[sz], ind_i, stk[sz], ind_s, out[sz], ind_o, cnt;
char res[5000][sz];
n表示火车数量，in数组用于存储火车进站序列，ind_i时in数组的索引
stk数组模拟栈，用于暂存或者。ind_s时stk数组的索引。
out数组用于存储火车出战序列。ind_o时out数组的索引。
res是一个二维字符数组，用于存储所有可能的出站序列字符串形式。
cnt用于记录不同出站序列的数量。
3.定义一个比较函数，用于qsort函数进行字典序比较。它比较两个字符串的大小，返回值表示两个字符串的比较结果。
int comp(const void* a, const void* b) {
return strcmp(a, b);
}
4.定义深度优先搜索函数
void dfs(void) {
5.如果出站序列的长度等于火车数量n，说明找到了一种完整的出站序列。将out数组中的数字转换为字符形式存入res数组，并增加cnt表示找到的出站序列数量加一，然后返回。
if(ind_o == n) {
int i;
for(i = 0; i < ind_o; ++i) res[cnt][i] = out[i] + '0';
res[cnt++][i] = '\0';
return;
}
6.如果进站序列还没有处理完，将进站序列中的下一个火车放入栈中，然后递归调用dfs函数继续搜索。搜索完后，将刚才放入栈中的火车弹出（恢复现场），即减少ind_s和ind_i。
if(ind_i < n) {
stk[ind_s++] = in[ind_i++];
dfs();
--ind_s, --ind_i;
}
7.如果栈不为空，说明可以有火车出站。将栈顶的火车弹出放入出站序列中，然后递归调用dfs函数继续搜索。搜索完后，将刚才出站的火车重新放入栈中（恢复现场），即增加ind_s和减少ind_o.
if(ind_s) {
out[ind_o++] = stk[--ind_s];
dfs();
stk[ind_s++] = out[--ind_o];
}
8.主函数开始
int main() {
9.循环读取火车数量n，直到输入结束。
while(scanf("%d", &n) == 1) {
10.读取火车进站序列，并初始化相关索引和计数器。
for(int i = 0; i < n; ++i) scanf("%d", in+i);
in_i = ind_o = ind_s = cnt = 0;
11.调用深度优先搜索函数，开始寻找所有可能的火车出站序列。
dfs();
12.对找到的所有出站序列进行字典排序。
qsort(res, cnt, sizeof(res[0]), comp);
13.输出所有排序后的火车出站序列，每个序列占一行。最后主函数返回0，表示程序正常结束。
for(int i = 0; i < cnt; ++i) {
for(int j = 0; j < n; ++j) printf("%c ", res[i][j]);
putchar('\n');
}
}
}
return 0;
}
三、具体步骤
使用的语言是C
#include <stdio.h>
#include <string.h>
const int sz = 12;
int n;
int in[sz];
int ind_i;
int stk[sz];
int ind_s;
int out[sz];
int ind_o;
char res[5000][sz];
int cnt;
int comp(const void* a, const void* b) {
return strcmp(a, b);
}
void dfs() {
if(ind_o == n) {
int i;
for(i = 0; i < ind_o; ++i) res[cnt][i] = out[i] +'0';
res[cnt++][i] = '\0';
return;
}
if(ind_i < n) {
stk[ind_s++] = in[ind_i++];
dfs();
--ind_s, --ind_i;
}
if(ind_s) {
out[ind_o++] = stk[--ind_s];
dfs();
stk[ind_s++] = out[--ind_o];
}
}
int main() {
while (scanf("%d", &n) == 1) {
for(int i = 0; i < n; ++i) scanf("%d", in + i);
ind_i = ind_o = ind_s = cnt = 0;
dfs();
qsort(res, cnt, sizeof(res[0]), comp);
for(int i = 0; i < cnt; ++i) {
for(int j = 0; j < n; ++j) printf("%c ", res[i][j]);
putchar('\n');
}
}
return 0;
}