火车进站

[编程题]火车进站

热度指数：79197 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个正整数N代表火车数量，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。

要求输出所有火车出站的方案，以字典序排序输出。

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

输入描述:

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

输出描述:

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

示例1

输入

3
1 2 3

输出

说明

第一种方案：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]这个序列是不可能实现的。

算法知识视频讲解

BSF

发表于 2021-10-21 10:35:34

res = [] def dfs(wait, stack, out): if not wait and not stack: res.append(' '.join(map(str, out))) if wait: # 入栈 dfs(wait[1:] 展开全文

牛客931628554号

发表于 2021-11-07 16:44:33

import java.util.*; public class Main{ static List<String> l = new ArrayList<>(); //储存结果 public static void main(String[] args) { Sca 展开全文

鲸鱼要好好学习呀

发表于 2020-08-15 14:29:48

看了题解和讨论区都是用传统的进出栈来求解的，我这里提出一种新的思路，运用递归的方法：1）我们从对车的操作来考虑，构造一个对车进行操作的标记序列，例如[1,2,2,1]就代表1号车进站，2号车进站，2号车出站，1号车出站的一个操作流程，从这里我们不难看出，序列中第一次出现的序号代表该序号进站，第二次出展开全文

牛客390110585号

发表于 2022-03-09 16:44:39

import java.util.*; // 思路：主要思想是递归，之所以产生很多方案的原因就是，每次进来一辆火车后，我们将其压入栈中，然后我们可以有两种选择，一是不弹出，二是弹出； // 对于第二种弹出元素，弹出的个数的范围取决于当前栈中元素的个数，所以遍历每种情况，在遍历每种情况的时候再递归到展开全文