描述
给定一个正整数N代表火车数量，0 < N <
10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9
编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
要求输出所有火车出站的方案，以字典序排序输出。
数据范围：1≤ n ≤10 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]这个序列是不可能实现的。
思路：
方法一：全排列
算法步骤：
- 从小到大全排列所有的出栈顺序
- 根据入栈顺序判断出栈顺序是否合法
- 如果合法就输出该出栈顺序
问题一：如何全排列？
可以调用next_permutation来进行全排列
1
2
3
4
5
6
7
8
9
10
| sort(tmp.begin(), tmp.end());
do{
if(check(tmp)){
for(int i = 0; i < n; i++){
cout << tmp[i] << " ";
}
cout << endl;
}
}while(next_permutation(tmp.begin(), tmp.end()));
|
问题二：如何判断出栈顺序是否合法？
例如：
入栈顺序为： 1 2 3
出栈顺序为：3 1 2
我们直接看，可以明显的看出是不合法的。那么计算机应该如何判断呢？我们只需要借助栈模拟下输出即可。
我们先让nums的元素入栈，然后判断栈是否为空和栈顶元素是否等于出栈顺序的首数字，如果等于出栈顺序
+ 1，并且把栈顶元素出栈，最后判断栈是否为空，空就代表合法，否则非法
我们可以写出如下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool check(vector<int>& tmp){
stack<int> st;
int j = 0;
for(int i = 0; i < tmp.size(); i++){
st.push(nums[i]);
while(!st.empty() && tmp[j] == st.top()){
st.pop();
j++;
}
}
return st.empty();
}
|
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
int n;
vector<int> nums;
bool check(vector<int>& tmp){
stack<int> st;
int j = 0;
for(int i = 0; i < tmp.size(); i++){
st.push(nums[i]);
while(!st.empty() && tmp[j] == st.top()){
st.pop();
j++;
}
}
return st.empty();
}
int main(){
cin >> n;
nums.resize(n,0);
for(int i = 0; i < n; i++){
cin >> nums[i];
}
vector<int> tmp(nums);
sort(tmp.begin(), tmp.end());
do{
if(check(tmp)){
for(int i = 0; i < n; i++){
cout << tmp[i] << " ";
}
cout << endl;
}
}while(next_permutation(tmp.begin(), tmp.end()));
return 0;
}
|
全排列的时间复杂度为O(n!)，判断出栈序列是否合法为O(n)，所以总的时间复杂度为：O(n*n!)
空间复杂度为：O(n)
方法二：dfs
dfs
遍历整个全排列，最坏情况下全排列都要输出，时间复杂度为O(n!log2(n!))
空间复杂度为：O(n * n!)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <bits/stdc++.h>
using namespace std;
int n;
int nums[15],c[15],tmp[15], vis[15];
bool check(int b[]){
stack<int> st;
int j = 0;
for(int i = 0; i < n; i++){
st.push(nums[i]);
while(!st.empty() && b[j] == st.top()){
st.pop();
j++;
}
}
return st.empty();
}
void dfs(int x){
if(x == n){
if(check(tmp)){
for(int i = 0; i < n; i++){
cout << tmp[i] << " ";
}
cout << endl;
}
return;
}
for(int i = 0; i < n; i++){
int y = c[i];
if(vis[y] == 0){
vis[y] = 1;
tmp[x] = y;
dfs(x + 1);
vis[y] = 0;
}
}
}
int main(){
while(cin >> n){
for(int i = 0; i < n; i++){
cin >> nums[i];
c[i] = nums[i];
}
sort(c, c + n);
dfs(0);
}
return 0;
}
|