首页 > 试题广场 >

火车进站

[编程题]火车进站

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

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

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

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

进阶：时间复杂度： $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]这个序列是不可能实现的。

算法知识视频讲解

Python

大溪地渔民

def helper(trains, stack, output):
    global total
    if not trains and not stack:
        total.append(output)
        return
    if stack:
        t = stack.pop()
        helper(trains, stack, output+t)
        stack.append(t)
    if trains:
        stack.append(trains.pop())
        helper(trains, stack, output)
        trains.append(stack.pop())


while True:
    try:
        n = int(input())
        trains = input().split()[::-1]
        stack, total = [], []
        helper(trains, stack, "")
        for s in sorted(total):
            print(" ".join(s))
    except:
        break

发表于 2020-12-18 15:53:58 回复(0)

Python

混分兽

递归可能比较好理解一点：

all_res=[]
def solver(prefix,my_stack,remain):
    global all_res
    if remain==[]:
        if not my_stack:
            all_res.append(prefix[:])
            return 
        else:
            while my_stack:
                prefix.append(my_stack.pop())
            all_res.append(prefix[:])
            return
    if not my_stack:
        solver(prefix[:],[remain[0]], remain[1:])
    else:
        solver(prefix[:], my_stack[:]+[remain[0]], remain[1:])
        while my_stack:
            prefix.append(my_stack.pop())
            solver(prefix[:], my_stack[:]+[remain[0]], remain[1:])
while True:
    try:
        all_res=[]
        number=int(input())
        remain=input().split()
        solver([], [], remain)
        all_res.sort()
        for string in all_res:
            print(' '.join(string))
    except:
        break

发表于 2020-09-18 14:28:29 回复(0)

Python

牛客904525060号

看答案都是用递归处理，分享个另类思路。性能略差，比较直白

1：先求出所有车的排列，作为出站序列

2：循环判断该出站序列是否符合要求

判断逻辑：

1：任意车n出站后，其前车0~n-1必然在车站内(如果已出站则移除)，n+1~-1则在车站外

2：下一车 x 出站，判断x是在站内还是站外。如果是站内则必然是栈顶元素，判断是否相等，如果不相等就撞车了，移除

3：剩下的就是所有出站序列的集合，排序输出

import itertools

while True:
    try:
        n = input()
        l = input().split(" ")
        all = itertools.permutations(l)

        allc = []
        for out in all:
            b = l.copy()
            station = []
            bool = False
            for car in out:
                if car in station and car != station.pop():
                    # allc.remove(out)
                    bool = True
                    # print(out, "撞车了")
                    break
                station = b[:b.index(car)]
                b.remove(car)
                # print(f"{car}号小火车走了,站内还有{station}")
            if not bool:
                allc.append(" ".join(out))
        allc.sort()

        print("\n".join(allc))
    except:
        break

编辑于 2020-09-07 18:24:59 回复(0)

Python

鲸鱼要好好学习呀

看了题解和讨论区都是用传统的进出栈来求解的，我这里提出一种新的思路，运用递归的方法：
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)

Python

走:路

明晰易懂的递归实现

'''
栈  火车出站问题
恭喜你通过本题
运行时间：29ms
占用内存：3920k
'''
def station_scedule(wait_in, wait_out, leave):

    if (not wait_in) and (not wait_out):
        train_out.append(' '.join(leave))
    if wait_in:
        wait_in_ = wait_in[:]
        wait_out_ = wait_out[:]
        leave_ = leave[:]
        wait_out_.append(wait_in_.pop(0))
        station_scedule(wait_in_, wait_out_, leave_)
    if wait_out:
        wait_in_ = wait_in[:]
        wait_out_ = wait_out[:]
        leave_ = leave[:]
        leave_.append(wait_out_.pop())
        station_scedule(wait_in_, wait_out_, leave_)
while True:
    try:
        N, train_in = int(input()), input().strip().split(' ')
        train_out = []
        leave = []
        station_scedule(train_in, [], leave)
        for i in sorted(train_out):
            print(i)
    except:
        break

发表于 2020-07-20 16:08:19 回复(0)

Python

君临天下201804050931706

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

发表于 2020-07-12 15:24:40 回复(1)

Python

坚定的小饼干在投简历

# 经典递归 a:进栈口 container:栈 b:出栈记录 b_list:保存出栈记录的列表

import copy

while True:
try:
num = input()
a =input().split(" ")
b_list = []
def handel(a,container=[],b=""):
if container==[] and a ==[]:
b_list.append(b)
return
elif container == []:
container.append(a.pop(0))
handel(a,container,b)
elif a == []:
b += container.pop()
handel(a,container,b)
else:
a1,container1 = copy.copy(a),copy.copy(container)
container.append(a.pop(0))
handel(a,container,b)

b += container1.pop()
handel(a1,container1,b)

handel(a)
b_list = sorted(b_list)
for i in b_list:
print(i.replace(""," ").strip())
except:
break

发表于 2020-06-10 19:22:15 回复(0)