[编程题]火车进站
- 热度指数：86049 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个整数
代表火车的数量。
个整数
代表火车的入站顺序。
输出描述:
示例1
输入
3 1 2 3
输出
1 2 3 1 3 2 2 1 3 2 3 1 3 2 1
说明
；
；
；
；
。
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)
该代码核心思想参考其它大神(并非自创)，我这边大概写一下我理解的思路
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)
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)
//对一位大神的双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)
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)
"""
栈的出栈序列排列问题”或称“卡特兰数问题”：
给定一个数组，该数组中的元素依次入栈。在入栈的过程中，允许在任意时刻进行出栈操作。
问题是：通过这些入栈和出栈操作，最后得到的出栈序列有哪些可能？以及有多少种可能的出栈序列？
使用递归回溯法
"""
def generate_stack_permutations(seq):
n = len(seq)
# 存储所有可能的出栈序列
results = []
# 递归函数来模拟栈操作
"""该递归函数会造成算力浪费"""
def backtrack(input_seq, stack, output_seq):
# 如果整个序列都已入栈并且栈已空，则输出序列是完成的
if not input_seq and not stack:
results.append(output_seq[:])
return
# 如果输入序列还有元素可入栈
"""
本步完成了一次输入序列的单元素入栈操作，并对剩下的序列继续调用函数
最后移除刚刚入栈的元素，回溯到原先的状态
"""
if input_seq:
# 模拟入栈操作
stack.append(input_seq[0])
backtrack(input_seq[1:], stack, output_seq)
"""回溯法"""
stack.pop() # 删除stack最后一个，回溯入栈操作
# 如果栈中有元素可出栈
if stack:
# 模拟出栈操作
popped = stack.pop() # 出栈一个元素
output_seq.append(popped) # 加入输出序列
backtrack(input_seq, stack, output_seq) # 递归
output_seq.pop() # 回溯，移除刚加入的元素
"""回溯法"""
stack.append(popped) # 回溯堆栈状态
# 开始递归
backtrack(seq, [], [])
return results
n = input()
input_sequence = [int(i) for i in input().split(' ')]
all_permutations = generate_stack_permutations(input_sequence)
# 输出所有可能的出栈序列，字典序排序
all_permutations = sorted(all_permutations)
for permutation in all_permutations:
print(" ".join([str(i) for i in permutation]))
# 输出总数量
# print("总出栈序列数量:", len(all_permutations))
编辑于 2024-08-30 12:29:24
回复(0)
数据量不大，用一个笨办法，生成1~N的所有排列，然后过滤掉不可能的出栈序列
from itertools import permutations
def judge(inseq, outseq, n):
# 检查outseq是否是入栈序列inseq的出栈序列
stack = []
j = 0
for i in range(n):
stack.append(inseq[i])
while j < n and stack and outseq[j] == stack[-1]:
stack.pop()
j += 1
return stack == []
n = int(input())
seq = list(map(int, input().strip().split()))
results = []
for seq_perm in permutations(seq):
if judge(seq, list(seq_perm), n):
result = ""
for num in seq_perm:
result += f"{num} "
results.append(result)
# 保持字典序
for result in sorted(results):
print(result.strip())
发表于 2021-04-02 18:42:34
回复(1)
问题信息
通过挑战的用户
查看代码-
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
相关试题
-
评论(838) 来自华为机试编程模拟题3
-
评论(4) 来自华为机试编程模拟题3
-
评论(7)
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
