打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
华为机试HJ77:火车进站

作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

题目描述:

给定一个正整数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;
}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序,算一算2024你的财运
【原创】栈和队列的数据结构实现
精明的程序员——堆栈和队列的相互转换
474,翻转二叉树的多种解决方式
二叉树的创建及遍历(递归与非递归)
剑指offer之两个栈实现队列问题
C语言实现,顺序队列,循环队列,和栈!
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服