给定一个正整数N代表火车数量，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
要求输出所有火车出站的方案，以字典序排序输出。
进阶：时间复杂度：%5C)
，空间复杂度：%5C)
[编程题]火车进站
- 热度指数：79197 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个正整数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]这个序列是不可能实现的。
// 要出来/要进去都没了 - 完成
// 要出来的没了 - 必须进去
// 要进去的没了 - 必须出来
// 进去/出来
while(n = +readline()) {
// const items = readline().split(' ').map(Number);
const res = [];
const stack = []; // 进站
let queue = []; // 待进站
queue = readline().split(' ').map(Number);
// getNT(items).map(item => console.log(item.join(' ')));
function operate(stack, queue, out, n) {
if (out.length == n*2 - 1) { // 全出来了
res.push(out);
} else if(queue.length && !stack.length) { // 没了 - 进入
const inItem = queue.slice(0, 1); // 进站
const addStack = [...stack, inItem];
const newQueue = queue.slice(1);
// console.log('in', addStack, newQueue, out, n);
operate(addStack, newQueue, out, n);
} else if (!queue.length && stack.length) { // 没要进去的了 - 必须有出来的
const outItem = stack.slice(-1); // 出战
const addOut = out.length ? out + ' ' + outItem : outItem;
const newStack = stack.slice(0, stack.length - 1);
operate(newStack, queue, addOut, n);
} else { // 可以先进去 || 可以先出来
const inItem = queue.slice(0, 1); // 进站
const addStack = [...stack, inItem];
const newQueue = queue.slice(1);
operate(addStack, newQueue, out, n);
const outItem = stack.slice(-1); // 出战
const addOut = out.length ? out + ' ' + outItem : outItem;
const newStack = stack.slice(0, stack.length - 1);
operate(newStack, queue, addOut, n);
}
}
// console.log('111', stack, queue, [], n)
operate(stack, queue, '', n);
res.sort();
// console.log(res);
res.map(item => console.log(item))
}
发表于 2022-04-07 19:15:19
回复(0)
import itertools as it #判断data2是不是按data1顺序进栈的输出序列，如isPopSerial([1,2,3],[3,1,2])返回False def isPopSerial(data1, data2): stack=[] j=0 for k in range(len(data1)): stack.append(data1[k]) while stack and stack[-1]==data2[j]: #一直进栈直到栈顶等于输出序列的最前端 stack.pop() #出栈 j+=1 #输出序列最前端往后一个位置，继续判断 if k==j-1: return True else: return False while True: try: N=int(input()) push=list(map(int,input().split())) pushsq=list(it.permutations(push)) popsq=[] for i in pushsq: if isPopSerial(push, i): popsq.append(list(i)) popsq.sort() for i in popsq: for j in i: print(j,end=" ") print() except: break
发表于 2021-09-01 16:00:59
回复(0)
def func(l,inTrains,outTrains,res):
if(len(l)==0 and len(inTrains)==0):
res.append(outTrains)
else:
if inTrains:
c_out = outTrains + inTrains[-1] + ' '
func(l,inTrains[:-1],c_out,res)
if l:
c_in = inTrains.copy()
c_in.append(l[0])
func(l[1:],c_in,outTrains,res)
while True:
try:
num = int(input())
trains = input().split()
res = []
func(trains.copy(), [], '', res)
res.sort()
for i in res:
print(i)
except:
break
if(len(l)==0 and len(inTrains)==0):
res.append(outTrains)
else:
if inTrains:
c_out = outTrains + inTrains[-1] + ' '
func(l,inTrains[:-1],c_out,res)
if l:
c_in = inTrains.copy()
c_in.append(l[0])
func(l[1:],c_in,outTrains,res)
while True:
try:
num = int(input())
trains = input().split()
res = []
func(trains.copy(), [], '', res)
res.sort()
for i in res:
print(i)
except:
break
发表于 2020-07-12 15:24:40
回复(1)
代码如下：
import java.util.*;
public class Main{
//in是在车站的火车，end是已出站的火车，train是输入的火车数组，list用来保存结果
public static int[] in;
public static int[] end;
public static int[] train;
public static List<String> list = new ArrayList<>();
public static void getOrder(int order){
/**
*火车进站后有两种选择，直接出站 和 不出站等待下一列火车进站
*我是先处理火车直接出站，再处理等待的，直到所有的火车都是等待状态，全部结束
*只要有火车出站，就进入递归判断下一列火车，然后递归方法结束后重置in和end数组
*/
int[] inRec = new int[in.length];
int[] endRec = new int[end.length];
for(int i=0; i<inRec.length; i++){
inRec[i] = in[i];
endRec[i] = end[i];
}
for(int i=0; i<train.length; i++){
//判断当前列车是否已出站
boolean flag = true;
for(int j=0; j<end.length; j++){
if(train[i] == end[j]){
flag = false;
break;
}
}
//判断当前列车是否 不在车站内 或者是 车站内最靠前的列车
boolean max = false;
boolean notIn = true;
for(int j=0; j<in.length; j++){
if(in[j] == train[i]){
notIn = false;
}
if(in[j]==0 && j!=0 && in[j-1]==train[i]){
max = true;
}
}
//符合条件表示可处理
if(flag && (max || notIn)){
//先让火车出站，加入出站数组，然后进入递归，然后重置
for(int j=0; j<end.length; j++){
if(end[j]==0 && i!=train.length-1){
end[j] = train[i];
for(int m=0; m<in.length; m++){
if(in[m] == train[i]){
in[m] = 0;
break;
}
}
getOrder(i);
end[j] = 0;
break;
}
}
//再让火车进入等待数组
for(int j=0; j<in.length; j++){
if(in[j] == 0){
in[j] = train[i];
break;
}
}
}
//如果当前处理的是最后一列火车，把当前方案记录下来
if(i == train.length-1){
String result = "";
for(int j=0; j<end.length; j++){
if(end[j] != 0){
result += end[j] + " ";
}
}
for(int j=in.length-1; j>=0; j--){
if(in[j] != 0){
result += in[j] + " ";
}
}
list.add(result.trim());
}
}
in = inRec;
end = endRec;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int[] train = new int[count];
for(int i=0; i<count; i++){
train[i] = sc.nextInt();
}
//初始化变量
Main.in = new int[count];
Main.end = new int[count];
Main.train = train;
Main.getOrder(-1);
//list转为数组排序输出
String[] result = Main.list.toArray(new String[Main.list.size()]);
Arrays.sort(result);
for(int i=0; i<result.length; i++){
System.out.println(result[i]);
}
sc.close();
}
}
发表于 2020-03-30 16:54:34
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
bool Ispoporder(vector<int>& pop_vec,vector<int>& push_vec){
stack<int> stack1;
int j=0;
for(int i=0; i<push_vec.size(); i++){
stack1.push(push_vec[i]);
while(!stack1.empty()&&stack1.top()==pop_vec[j]){
j++;
stack1.pop();
}
}
return j==pop_vec.size();
}
int main(){
int n;
while(cin>>n){
vector<int> vec;
int temp;
while(n--){
cin>>temp;
vec.push_back(temp);
}
vector<int> copy(vec);
sort(copy.begin(), copy.end());
do{
if(Ispoporder(copy,vec)){
for(int i=0; i<copy.size(); i++)
cout<<copy[i]<<' ';
cout<<endl;
}
}while(next_permutation(copy.begin(),copy.end()));
}
}
#include<vector>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
bool Ispoporder(vector<int>& pop_vec,vector<int>& push_vec){
stack<int> stack1;
int j=0;
for(int i=0; i<push_vec.size(); i++){
stack1.push(push_vec[i]);
while(!stack1.empty()&&stack1.top()==pop_vec[j]){
j++;
stack1.pop();
}
}
return j==pop_vec.size();
}
int main(){
int n;
while(cin>>n){
vector<int> vec;
int temp;
while(n--){
cin>>temp;
vec.push_back(temp);
}
vector<int> copy(vec);
sort(copy.begin(), copy.end());
do{
if(Ispoporder(copy,vec)){
for(int i=0; i<copy.size(); i++)
cout<<copy[i]<<' ';
cout<<endl;
}
}while(next_permutation(copy.begin(),copy.end()));
}
}
发表于 2020-02-28 18:25:49
回复(0)
package HUAWEI2;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
/**
* 火车进站
* @author Administrator
*
*/
public class Demo37 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int num = sc.nextInt();
int[] A = new int[num];
for(int i=0;i<num;i++){
A[i] = sc.nextInt();
}
int start = 0;
ArrayList<int[]> result = new ArrayList<>();
Permutation(A,start,num,result);
Set<String> sortResult = new TreeSet<>();
for(int[] out:result){
if(isLegal(A,out,num)){
StringBuilder sb = new StringBuilder();
for(int i=0;i<num-1;i++){
sb.append(out[i]+" ");
}
sb.append(out[num-1]);
sortResult.add(sb.toString());
}
}
for(String list:sortResult){
System.out.println(list);
}
}
sc.close();
}
private static boolean isLegal(int[] in,int[] out,int n){
Stack<Integer> stack = new Stack<>();
int i=0;
int j=0;
while(i<n){
if(in[i]==out[j]){
i++;
j++;
}else{
if(stack.isEmpty()){
stack.push(in[i]);
i++;
}else{
int top = stack.peek();
if(top==out[j]){
j++;
stack.pop();
}else if(i<n){
stack.push(in[i]);
i++;
}
}
}
}
while(!stack.isEmpty()&&j<n){
int top = stack.pop();
if(top==out[j]){
j++;
}else{
return false;
}
}
return true;
}
/**
* 求出所有排序 结果存在result中
* @param A
* @param start
* @param n
* @param list
*/
private static void Permutation(int[] A,int start,int n,ArrayList<int[]> result){
if(start==n){
return;
}
if(start==n-1){//存储最后的数据
int[] B = A.clone();
result.add(B);
return;
}
for(int i=start;i<n;i++){
swap(A,start,i);
Permutation(A,start+1,n,result);
swap(A,start,i);
}
}
private static void swap(int[] A,int i,int j){
int t = A[i];
A[i]=A[j];
A[j]=t;
}
}
发表于 2017-04-10 22:19:03
回复(1)
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std ;
bool ispop(string pushV , string popV)
{
stack<char> stack ;
int l = pushV.size() ;
int i =0 , j = 0;
while( j < l)
{
while( stack.empty() || stack.top() != popV[j])
{
if( i >= l)
return false ;
stack.push(pushV[i]) ;
i++ ;
}
j++ ;
stack.pop() ;
}
return true ;
}
void permutation(string pushV ,string ptemp , vector<string>& popV , int begin)
{
if( begin == pushV.size()-1)
{
if(ispop(pushV , ptemp))
popV.push_back(ptemp) ;
}
else
{
for(int j = begin ; j < pushV.size() ; j++ )
{
if( j != begin && ptemp[j] == ptemp[begin])
continue ;
swap(ptemp[j] , ptemp[begin]) ;
permutation(pushV , ptemp , popV , begin+1) ;
swap(ptemp[j] , ptemp[begin]) ;
}
}
}
int main()
{
int n ;
while(cin >> n)
{
char temp ;
string pushV = "" ;
vector<string> popV ;
for(int i = 0 ; i < n ; i++)
{
cin >> temp ;
pushV += temp ;
}
permutation(pushV ,pushV, popV, 0) ;
sort(popV.begin() , popV.end()) ;
for(int i = 0 ; i < popV.size() ; i++)
{
bool isfirst = true ;
for(int j =0 ; j < n ; j++ )
{
if(!isfirst)
cout << " ";
cout<<popV[i][j];
isfirst =false ;
}
cout <<endl ;
}
}
return 0 ;
}
先全排列，然后找出符合出栈入栈条件的，最后sort排列，输出
发表于 2016-08-10 14:59:38
回复(0)
思路：
用栈模拟火车进出站：对进站序列排序得到字典序的第一组，处理完第一组，用
next_permutation获取下一组排列。
对每组排列判断是否正确。在函数
isOutNum中实现：依次把进站序列压入栈，如果栈顶和出战序列相同就删除栈顶，不相同就继续压入进站序列。直到进站序列压入完毕。栈空表示所有元素可以顺利出栈，此组序列是正确的出栈序列。
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
bool isOutNum(int *push,int *pop,int len)//判断pop是不是push的出栈序列
{
if(push==NULL || pop==NULL ||len<=0)
return false;
stack<int> Stack;
int i=0,j=0;
for(i=0;i<len;i++)//依次把push中的数入栈
{
Stack.push(push[i]);
while(j<len && Stack.size()!=0 && pop[j]==Stack.top())//依次判断pop序列每个值是否与栈顶相等
{
Stack.pop();
j++;
}
}
return Stack.empty();
}
int main()
{
int N;
while(cin>>N)
{
int *pushNum=new int [N];
int *popNum=new int [N];
for(int i=0;i<N;i++)
{
cin>>pushNum[i];
popNum[i]=pushNum[i];
}
sort(popNum,popNum+N);
do
{
if(isOutNum(pushNum,popNum,N))//如果该排列正确，则输出
{
for(int i=0;i<N-1;i++)
cout<<popNum[i]<<" ";
cout<<popNum[N-1]<<endl;
}
}
while(next_permutation(popNum,popNum+N));//获取下一个排列
}
return 0;
}
编辑于 2016-09-03 17:01:37
回复(9)
python DFS就是香
class Solution:
def __init__(self):
self.ans = []
def dfs(self, wait, stack, leave):
if len(wait) == 0 and len(stack) == 0:
self.ans.append(leave)
if len(wait) > 0: # 从等待队列中 入栈
self.dfs(wait[1:], stack + [wait[0]], leave[:])
if len(stack) > 0: # 出栈
self.dfs(wait[:], stack[:-1], leave + [stack[-1]])
return self.ans
# 处理一些输入输出
if __name__ == '__main__':
while True:
try:
n = input()
nums = list(map(int, input().split()))
sol = Solution()
ret = sol.dfs(nums, [], [])
for line in sorted(ret):
print(" ".join(map(str, line)))
except:
break
发表于 2021-09-08 10:54:06
回复(0)
看了题解和讨论区都是用传统的进出栈来求解的，我这里提出一种新的思路，运用递归的方法：
1）我们从对车的操作来考虑，构造一个对车进行操作的标记序列，例如[1,2,2,1]就代表1号车进站，2号车进站，2号车出站，1号车出站的一个操作流程，从这里我们不难看出，序列中第一次出现的序号代表该序号进站，第二次出现代表出站。
2）这里我们着重考虑最后一辆车进出站的情况，不难发现最后一辆车进站发生在前一辆进站之后的任意时刻都满足条件，而最后一辆车进站后由于没有车还能进站因此必须立即出站，因此在操作序列中，最后一辆车的序号必是连续的。
3）有了以上两点结论后我们便可以构造递归函数：
1）我们从对车的操作来考虑，构造一个对车进行操作的标记序列，例如[1,2,2,1]就代表1号车进站，2号车进站，2号车出站，1号车出站的一个操作流程，从这里我们不难看出，序列中第一次出现的序号代表该序号进站，第二次出现代表出站。
2）这里我们着重考虑最后一辆车进出站的情况，不难发现最后一辆车进站发生在前一辆进站之后的任意时刻都满足条件，而最后一辆车进站后由于没有车还能进站因此必须立即出站，因此在操作序列中，最后一辆车的序号必是连续的。
3）有了以上两点结论后我们便可以构造递归函数：
def cal(x,s): if x == 1: return [[s[0],s[0]]] #只有一辆车时递归终止 else: res = [] for i in cal(x-1,s[0:x-1]): add = i.index(s[x-2]) #获得x-1辆车的操作序列中第x-1辆车编号第一次出现时的下标 for j in range(add+1,len(i)+1): #在第x-1辆车编号第一次出现之后的任意位置均可插入连续的第x辆车编号获得新序列 temp = i[:] temp.insert(j,s[x-1]) temp.insert(j,s[x-1]) res.append(temp) return res函数的输入参数x和s分别表示的是车的数量和进站的编号序列，递归的重点是车只有一辆时，只有进站出站一种排列方式，对于车有x辆时，由开头得出的两个结论，x辆车时的操作序列可以由x-1辆车时的操作序列中插入连续的第x辆车编号来获得。
现在我们得到了操作序列后我们需要由操作序列得到出站序列，显然我们只要把每辆车编号的第一次出现删除即可
while True:
try:
n = int(input())
sou = [int(x) for x in input().split()]
ans = cal(n,sou) #得到操作序列
for i in ans:
for j in range(1,n+1):
i.remove(j) #删除每辆车编号的第一次出现
ans.sort()
for i in ans:
print(' '.join([str(x) for x in i]))
except:
break
编辑于 2020-08-15 14:30:56
回复(1)
import java.util.*;
public class Main {
static ArrayList<String> l=new ArrayList<String>(); //储存结果
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
while(in.hasNext()) {
l.clear(); //静态变量，每次先清空
int nums=in.nextInt();
int[] id=new int[nums];
Stack<Integer> stack=new Stack<Integer>();
for(int i=0;i<nums;i++) {
id[i]=in.nextInt();
}
trainOut(id,0,stack,"",0);
Collections.sort(l); //对结果集排序
for(String str:l) {
System.out.println(str);
}
}
in.close();
}
//i为入栈次数，n为出栈次数，str存储一趟结果
public static void trainOut(int[] id,int i,Stack<Integer> s,String str,int n) {
if(n==id.length) {
l.add(str); //如果所有火车均出栈则将当前结果保存
}
if(!s.empty()) { //栈非空时出栈
int temp=s.pop();
trainOut(id,i,s,str+temp+" ",n+1);
s.push(temp); //恢复现场
}
if(i<id.length) { //若所有火车没有都入栈则入栈
s.push(id[i]);
trainOut(id,i+1,s,str,n);
s.pop(); //恢复现场
}
}
}
发表于 2020-02-25 22:46:24
回复(9)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int[] A = new int[n];
for(int i=0;i<n;i++){
A[i] = in.nextInt();
}
int start = 0;
ArrayList<int[]> result = new ArrayList<int[]>();
Permutation(A,start,n,result);
Set<String> sortResult = new TreeSet<String>();
for(int[] out:result){
if(isLegal(A,out,n)){
StringBuilder sb = new StringBuilder();
for(int i=0;i<n-1;i++){
sb.append(out[i]+" ");
}
sb.append(out[n-1]);
sortResult.add(sb.toString());
// System.out.println(sb.toString());
}
}
for(String list:sortResult){
System.out.println(list);
}
}
in.close();
}
private static boolean isLegal(int[] in,int[] out,int n){
LinkedList<Integer> stack = new LinkedList<Integer>();
int i=0;
int j=0;
while(i<n){ // in 还有元素的时候都需要判断
if(in[i] == out[j]){ // 相等时候就不用入栈，直接后移
i++;
j++;
}else{
if(stack.isEmpty()){ //空stack 就只有入栈了
stack.push(in[i]);
i++;
}else{
int top = stack.peek(); // 栈顶元素相等，进行出栈
if(top ==out[j]){
j++;
stack.pop();
}else if(i<n){ // 不等时候入栈
stack.push(in[i]);
i++;
}
}
}
}
while(!stack.isEmpty() && j<n){ // in 的结束后，栈中元素进程出栈序列应该和out剩余的元素 相同
int top = stack.pop();
if(top == out[j]){
j++;
}else{
return false;
}
}
return true;
}
/**
* 求出所有排列
* @param A
* @param start
* @param n
* @param result
*/
private static void Permutation(int[] A,int start,int n,ArrayList<int[]> result){
if(start == n){
return;
}
if(start == n-1){
int[] B = A.clone();
result.add(B);
return;
}
for(int i=start;i<n;i++){
swap(A,start,i);
Permutation(A,start+1,n,result);
swap(A,start,i);
}
}
private static void swap(int[] A,int i,int j){
int t = A[i];
A[i] = A[j];
A[j] = t;
}
}
发表于 2016-08-12 21:13:47
回复(2)
# 吃水不忘挖井人，先贴上思路来源（Java)http://blog.csdn.net/DERRANTCM/article/details/51433148
# 解题思路：使用三个变量，分别表示待进站火车、待出站火车、出站火车。
# 每次作业（只操作一辆车）有两种情况发生，一种是进站作业，一种是出站作业
# 将作业结果当作参数递归下去，递归结束标志是待进站火车和待出站火车都没有了
import copy
def handle(pre_station, in_station, after_station):
if not pre_station and not in_station: # 没有待进站的，也没有待出站的车，一种情况产生了
result.append(" ".join(after_station))
else:
if in_station: # 出站作业，先检查站内是否有车
temp_pre = copy.copy(pre_station)
temp_in = copy.copy(in_station)
temp_after = copy.copy(after_station)
temp_after.append(temp_in.pop())
handle(temp_pre, temp_in, temp_after) # 进行下一步作业
if pre_station: # 进站作业，先检查是否还有待进站车辆
temp_pre = copy.copy(pre_station)
temp_in = copy.copy(in_station)
temp_after = copy.copy(after_station)
temp_in.append(temp_pre.pop(0))
handle(temp_pre, temp_in, temp_after) # 进行下一步作业
count = int(raw_input()) # 火车数量，没有用到，但是是题目输入格式要求，故保留
row_2 = raw_input()
result = [] # 记录最终数据
pre_station = [x for x in row_2.split(" ")] # 待进站的车辆
in_station = [] # 待出站车辆
after_station = [] # 出站后的车辆
handle(pre_station, in_station, after_station)
result.sort() # 要字典序输出，排个序咯
for rs in result:
print rs
编辑于 2016-08-10 16:35:11
回复(6)
该代码核心思想参考其它大神(并非自创)，我这边大概写一下我理解的思路
n, nums = input(), input().split()
res = []
def dfs(w, i, o):
# 如果没有 待需要进栈的火车 和 需要出栈的火车，证明所有火车都已出栈
# 需要将都已出栈的火车添加到res
if not w and not i:
res.append(' '.join(map(str, o)))
# 如果有 待需要进栈的火车，那么则安排一辆火车进栈
if w:
dfs(w[1:], i + [w[0]], o)
#如果有进栈的火车，那么可以安排火车出栈
if i:
dfs(w, i[:-1], o + [i[-1]])
dfs(nums, [], [])
#sorted 按照题目要求，字典序输出
for i in sorted(res):
print(i)
发表于 2023-05-05 22:44:31
回复(2)
res = []
def find(a,b,c):
if not a and not b:
res.append(' '.join(map(str,c)))
if b:
c.append(b.pop())
find(a,b,c)
b.append(c.pop())
if a:
b.append(a.pop(0))
find(a,b,c)
a.insert(0,b.pop())
n = input()
n = int(n)
pre = list(map(int,input().split()))
ins,outs = [],[]
find(pre,ins,outs)
res.sort()
for i in res:
print(i)
发表于 2019-01-29 10:20:45
回复(2)
//对一位大神的双dfs代码进行了注释
#include<vector>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int> nums, int index, stack<int> st){
//栈为空的条件很重要，说明后续出栈流程已经完成可以得到完整的出栈路径(顺序)了
if(index >= nums.size() && st.empty()){
res.push_back(path);
}
//入栈并且暂时不弹出 dfs1
if(index < nums.size()){
st.push(nums[index]);
//注意dfs1中的index+1代表继续入栈下一个元素
dfs(nums, index + 1, st);
st.pop(); //回溯
}
//入栈后立即弹出 dfs2
if(!st.empty()){
path.push_back(st.top());
st.pop();
//注意dfs2中index不变,因为这里为弹出操作，后续还有元素需要继续入栈
dfs(nums, index, st);
st.push(path.back()); //回溯
path.pop_back();
}
}
int main(){
int n;
stack<int> st;
while(cin >> n){
vector<int> nums(n);
for(int i = 0; i < n; ++i){
cin >> nums[i];
}
dfs(nums, 0, st);
sort(res.begin(), res.end()); //结果按字典序排序
for(int i = 0; i < res.size();++i){
for(int j = 0; j < res[0].size();++j){
cout << res[i][j] << ' ' ;
}
cout << endl;
}
}
return 0;
}
发表于 2022-09-05 15:00:51
回复(0)
简洁Java代码
import java.util.*;
public class Main {
public static List<String> res = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int[] nums = new int[n];
Stack<Integer> stk = new Stack<>();
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
helper(nums, 0, stk, "", 0);
Collections.sort(res);
for (String s : res) {
System.out.println(s);
}
}
}
public static void helper(int[] nums, int i, Stack<Integer> stk, String s, int n) {
if (n == nums.length)
res.add(s);
if (!stk.empty()) {
int tmp = stk.pop();
helper(nums, i, stk, s + tmp + " ", n +1);
stk.push(tmp);
}
if (i < nums.length) {
stk.push(nums[i]);
helper(nums, i + 1, stk, s, n);
stk.pop();
}
}
}
发表于 2022-04-06 11:12:10
回复(0)
问题信息
难度：
232条回答
3541收藏
38433浏览
通过挑战的用户
查看代码-
2023-02-24 21:29:22
-
2023-01-08 10:14:38 -
2022-10-27 17:03:23
-
2022-10-09 11:20:47 -
2022-10-08 07:56:38
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
