首页 > 试题广场 >

火车进站

[编程题]火车进站
  • 热度指数：82598 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}火车站一共有 n 辆火车需要入站，每辆火车有一个编号，编号为 1 到 n。
\hspace{15pt}同时，也有火车需要出站，由于火车站进出共享一个轨道，所以后入站的火车需要先出站。换句话说，对于某一辆火车，只有在它之后入站的火车都出站了，它才能出站。

\hspace{15pt}现在，已经知道了火车的入站顺序，你需要计算，一共有多少种不同的出站顺序。按照字典序从小到大依次输出全部的出站顺序。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 10\right) 代表火车的数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq n\right) 代表火车的入站顺序。


输出描述:
\hspace{15pt}输出若干行，每行输出 n 个整数，代表一种出站顺序。你需要按照字典序从小到大依次输出。
示例1

输入

3
1 2 3

输出

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

说明

\hspace{15pt}在这个样例中，每一种出栈顺序的详细出入站状况为（黑色普通字体代表入站、橙色加粗字体代表出站）：
\hspace{23pt}\bullet\,1 \to {\color{orange}{\bf 1}} \to 2 \to {\color{orange}{\bf 2}} \to 3 \to {\color{orange}{\bf 3}}；
\hspace{23pt}\bullet\,1 \to {\color{orange}{\bf 1}} \to 2 \to 3 \to {\color{orange}{\bf 3}} \to {\color{orange}{\bf 2}}；
\hspace{23pt}\bullet\,1 \to 2 \to {\color{orange}{\bf 2}} \to {\color{orange}{\bf 1}} \to 3 \to {\color{orange}{\bf 3}}；
\hspace{23pt}\bullet\,1 \to 2 \to {\color{orange}{\bf 2}} \to 3 \to {\color{orange}{\bf 3}} \to {\color{orange}{\bf 1}}；
\hspace{23pt}\bullet\,1 \to 2 \to 3 \to {\color{orange}{\bf 3}} \to {\color{orange}{\bf 2}} \to {\color{orange}{\bf 1}}。
算法知识视频讲解
开通博客
头像 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:] 展开全文
去ta的博客 赞 (103) 回复(17) 收起
头像 牛客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 展开全文
去ta的博客 赞 (69) 回复(14) 收起
头像 鲸鱼要好好学习呀
发表于 2020-08-15 14:29:48
看了题解和讨论区都是用传统的进出栈来求解的，我这里提出一种新的思路，运用递归的方法：1）我们从对车的操作来考虑，构造一个对车进行操作的标记序列，例如[1,2,2,1]就代表1号车进站，2号车进站，2号车出站，1号车出站的一个操作流程，从这里我们不难看出，序列中第一次出现的序号代表该序号进站，第二次出 展开全文
去ta的博客 赞 (43) 回复(1) 收起
头像 牛客390110585号
发表于 2022-03-09 16:44:39
import java.util.*; // 思路：主要思想是递归，之所以产生很多方案的原因就是，每次进来一辆火车后，我们将其压入栈中，然后我们可以有两种选择，一是不弹出，二是弹出； // 对于第二种弹出元素，弹出的个数的范围取决于当前栈中元素的个数，所以遍历每种情况，在遍历每种情况的时候再递归到 展开全文
去ta的博客 赞 (25) 回复(2) 收起
头像 莫不是
发表于 2021-06-25 14:25:18
todo : 增加说明 #include <algorithm> #include <iostream> #include <stack> #include <vector> using namespace std; void dfs(const v 展开全文
去ta的博客 赞 (24) 回复(7) 收起
头像 katha815
发表于 2022-05-03 23:16:00
引用代码：https://blog.csdn.net/qq_35061334/article/details/117338687 我在条件里加了print()感觉容易理解多了，希望也能帮到其他学习者！ def func(): while True: try: 展开全文
去ta的博客 赞 (22) 回复(4) 收起
头像 迪士尼在逃米老鼠
发表于 2020-02-18 20:47:04
每次操作只有两种选项， 输入的元素压栈； 栈顶的元素出栈； 后一次操作不受前一次操作影响。故可以使用递归实现。递归终止条件即输入序列用完。 #include <iostream> #include <queue> #include <algorithm> #i 展开全文
去ta的博客 赞 (20) 回复(3) 收起
头像 qinzhiwei
发表于 2021-10-04 12:05:26
import java.util.*; // 队列表示未进站的火车 // 栈表示已进站的火车 // 每次火车进站后有两种选择：1.直接出站 2.等待下列火车进站 使用递归考虑 public class Main {    &nb 展开全文
去ta的博客 赞 (17) 回复(2) 收起
头像 AimerAimer
发表于 2021-12-06 21:53:12
题意：         给定入栈序列，输出所以的以字典序从小到大排序的出栈序列。 方法一： 全排列函数+栈 思路：    &n 展开全文
去ta的博客 赞 (15) 回复(1) 收起
头像 Damonhmz
发表于 2022-03-13 22:16:33
import java.util.*; /** * HJ77 火车进站 - 中等 */ public class HJ077 { public static List<String> resList = new ArrayList<>(); publ 展开全文
去ta的博客 赞 (15) 回复(2) 收起

问题信息

栈
难度：
239条回答 39789浏览

热门推荐

通过挑战的用户

查看代码

相关试题

火车进站

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号