华为机试HJ77:火车进站

简介: 华为机试HJ77:火车进站

题目描述:

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

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

输入描述:

有多组测试用例,每一组第一行输入一个正整数N

输出描述:

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

示例:

输入:

3

1 2 3

输出:


1 2 3

1 3 2

2 1 3

2 3 1

3 2 1

说明:


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


解题思路:

本题是入栈出栈问题。用队列in存放火车入站的顺序,用out存放出站的顺序,用stack栈模仿入站出站操作;solve函数是递归求解函数,当bool为true时表示入站,为false表示出站;入站则将in弹出一个数据,stack存放一个数据,出站则stack弹出,out存放,出站先判断栈内有无数据,无数据直接返回;递归操作,进行一次出站再进行一次入站;当in队列空了则说明火车全部进站完毕,此时若还进站则直接返回,若栈内还有数据则依次弹出;用write_result函数记录out的结果,格式如1 2 3;递归全部完成则表示所有可能的情况都遍历过了;因为题目要求结果按字典排序,用sort排序后输出即可。

测试代码:

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
vector<string> result;
// 写入结果
void write_result(queue<int> q)
{
    string str;
    while(!q.empty())
    {
        str+=to_string(q.front());
        str+=' ';
        q.pop();
    }
    result.push_back(str);
}
// 递归求解
void solve(queue<int> in,stack<int> t,queue<int> out,bool flag)
{
    if(in.empty())            // in队列空了就说明都进完了
    {
        if(flag)              // in队列空了不能再进了
            return;
        while(!t.empty())     // 栈里若还有数据直接弹出到out队列里
        {
            out.push(t.top());
            t.pop();
        }
        write_result(out);    // 记录本次结果
        return;
    }
    else{
        if(flag)              // 入栈
        {
            t.push(in.front());
            in.pop();
        }
        else{                 // 出栈
            if(t.empty())     // 没得出直接返回
                return;
            out.push(t.top());
            t.pop();
        }
        // 递归
        solve(in,t,out,false); 
        solve(in,t,out,true);
    }
}
int main()
{
    int num;
    while(cin>>num)
    {
        int sequence;
        queue<int> in,out;
        stack<int> t;
        for(int i=0;i<num;++i)
        {
            cin>>sequence;
            in.push(sequence);
        }
        solve(in,t,out,true);
        // 按字典顺序排序结果
        sort(result.begin(),result.end());
        for(auto it=result.begin();it!=result.end();++it)
        {
            cout<<*it<<endl;
        }
        result.clear();
    }
    return 0;
}
相关文章
|
7月前
华为机试HJ72:百钱买百鸡问题
华为机试HJ72:百钱买百鸡问题
|
7月前
|
机器学习/深度学习 算法 数据安全/隐私保护
华为机试HJ28:素数伴侣
华为机试HJ28:素数伴侣
|
7月前
|
机器学习/深度学习 测试技术
华为机试HJ55:挑7
华为机试HJ55:挑7
|
7月前
华为机试HJ88:扑克牌大小
华为机试HJ88:扑克牌大小
|
7月前
|
算法 测试技术
华为机试HJ67:24点游戏算法
华为机试HJ67:24点游戏算法
|
7月前
华为机试HJ103:Redraiment的走法
华为机试HJ103:Redraiment的走法
149 2
|
7月前
|
存储
华为机试HJ43:迷宫问题
华为机试HJ43:迷宫问题
|
7月前
华为机试HJ105:记负均正II
华为机试HJ105:记负均正II
|
7月前
|
Serverless 测试技术
华为机试HJ97:记负均正
华为机试HJ97:记负均正
100 1
|
7月前
|
算法
华为机试HJ76:尼科彻斯定理
华为机试HJ76:尼科彻斯定理

热门文章

最新文章