HJ77 火车进站 ●●

HJ77 火车进站 ●●

描述

给定一个正整数N代表火车数量，0 要求输出所有火车出站的方案，以字典序排序输出。

数据范围：$1\le n\le 10$

进阶：时间复杂度：$O(n!)$，空间复杂度：$O(n)$

输入描述：

第一行输入一个正整数N（0 < N <= 10），第二行包括N个正整数，范围为1到10。

输出描述：

输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。

示例

输入：
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. 全排列 + 验证出栈序列

#include 
#include 
#include 
#include 
using namespace std;vector<vector<int>> ans;
vector<int> path;bool check(vector<int>& list, vector<int>& path){    // 验证出栈序列stack<int> st;int idx = 0;for(int num : list){st.push(num);while(!st.empty() && st.top() == path[idx]){st.pop();++idx;}}return st.empty();
}void backtrack(vector<int>& list, vector<bool>& used){if(path.size() == list.size()){if(check(list, path)) ans.emplace_back(path);return;}for(int i = 0; i < list.size(); ++i){        // used数组标记、进行全排列if(used[i] == 0){path.emplace_back(list[i]);used[i] = 1;backtrack(list, used);used[i] = 0;path.pop_back();}}
}int main(){int n;while(cin >> n){vector<int> list(n, 0);for(int i = 0; i < n; ++i){cin >> list[i];}vector<bool> used(n, 0);backtrack(list, used);sort(ans.begin(), ans.end());for(auto nums : ans){for(int num : nums){cout << num << " ";}cout << endl;} }
}

2. dfs 回溯

每次 dfs 递归，存在两种操作：
1、从 list 数组中取一个数压入栈中；
2、取出栈顶元素。

因此，我们用回溯得到出栈序列的全排列，最后进行排序。

• 时间复杂度: $O(n!log(n!))$，回溯 + 排序。
• 空间复杂度: $O(n\ast n!)$

#include 
#include 
#include 
#include 
using namespace std;vector<vector<int>> ans;
vector<int> path;void backtrack(vector<int>& list, int idx, stack<int>& st){if(path.size() == list.size()){				// 排列完成ans.emplace_back(path);return;}for(int i = 1; i <= 2; ++i){				// 递归的两种选择if(i == 1){    					// 入栈if(idx < list.size()){st.push(list[idx]);				// 入栈backtrack(list, idx+1, st);		// list元素入栈，递归、指针右移st.pop();						// 回溯}}else{        					// 出栈if(!st.empty()){int temp = st.top();path.emplace_back(temp);		// 出栈st.pop();backtrack(list, idx, st);		// 未操作list数组，递归、指针不变st.push(temp);					// 回溯path.pop_back();}}} 
}int main(){int n;while(cin >> n){vector<int> list(n, 0);for(int i = 0; i < n; ++i){cin >> list[i];}stack<int> st;backtrack(list, 0, st);sort(ans.begin(), ans.end());		// 排序for(auto nums : ans){for(int num : nums){cout << num << " ";}cout << endl;} }
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！