火车进站

[编程题]火车进站

热度指数：73399 时间限制：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]这个序列是不可能实现的。

算法知识视频讲解

Javascript_V8

徐海超201812091924948

// 要出来/要进去都没了 - 完成
// 要出来的没了 - 必须进去
// 要进去的没了 - 必须出来
// 进去/出来
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)

Javascript_V8

我走路带風

let n;
while(n = readline()){
    var trains = readline().split(" ")
    var max = []
    var wuwu = function(num,list,arriving){
        if(num<trains.length){
            var list2 = list
            var arriving2 = arriving
            if(list.length>0){
               wuwu(num,list.slice(0,list.length-1),arriving+list[list.length-1]) 
            }
            
            wuwu(num+1,list+trains[num],arriving2)
        }else{
             for(let i =list.length-1;i>=0;i--){
                 arriving += list[i]
             }
            max.push(parseInt(arriving))
        }
    }
    wuwu(0,"","")
    
    max = max.sort(function(a,b){return a-b})
    
    for(let i =0;i<max.length;i++){
        let zf = max[i].toString().split("")
        let zz = ""
        for(let j=0;j<n;j++){
            zz += zf[j] + " "
        }
        console.log(zz.slice(0,2*n-1))
    }
}

发表于 2021-12-05 21:21:33 回复(0)