资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/华为机试HJ77：火车进站

华为机试HJ77：火车进站

muzhuyu / 2329人阅读

摘要：要求输出所有火车出站的方案，以字典序排序输出。输入描述有多组测试用例，每一组第一行输入一个正整数输出描述输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见。

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

题目描述：

给定一个正整数N代表火车数量，0

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

输入描述：

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

输出描述：

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

示例：

输入：

31 2 3

输出：

1 2 31 3 22 1 32 3 13 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 #include #include #include #include using namespace std;vector result;// 写入结果void write_result(queue q){    string str;    while(!q.empty())    {        str+=to_string(q.front());        str+=" ";        q.pop();    }    result.push_back(str);}// 递归求解void solve(queue in,stack t,queue 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 in,out;        stack t;        for(int i=0;i>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<
云服务器 专线服务 进站检查包裹图像识别 vps77 cdn77 html机试

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/120812.html

相关文章

  • 华为机试HJ57：高精度整数加法

    摘要：字符串的长度不超过。本题含有多组样例输入。保证字符串只含有字符输出描述输出求和后的结果示例输入输出解题思路本题通过字符串操作实现超高精度的整数加法。 作者：Steven 版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处 题目描述： 输入两个用字符串表示的整数，求它...

    AdolphLWQ 评论0 收藏0

  • 太原，这是我曾经和现在居住的城市，记录一个前端仔的三年。

    摘要：年，我离开了工作一年的杭州。火车站，是进入一个城市的入口。对于常年混迹于太原前端圈的我，发现最近两年太原招聘市场的一个发展趋势是，前端开发已经和一样，成为公司招聘的标配。后记太原并不大，也不繁华，但她是我生活的城市，我很热爱她。 showImg(https://segmentfault.com/img/bVZHg4?w=1000&h=565); 前言 这篇文章写给准备踏入互联网的萌新，...

    tomlingtm 评论0 收藏0

  • ChemiCloud：黑五优惠汇总，全年最便宜，续费永久优惠50%，首购高达80%优惠

    摘要：注意最优惠价格是三年付款。简单一句，优惠码有有效期，一旦在优惠码期内使用优惠无有效期永久有效。优惠三全托管首月折扣也提供虚拟专用服务器，而且是全托管的，独立性强于共享托管主机，而且还有独立。 官方网站 点击直达ChemiCloud官网 Chemicloud优惠一：共享主机高达80%优惠 ChemiCloud 的黑色星期五，这是一年中最大的活动！疯狂享受ChemiClo...

    Hujiawei 评论0 收藏0

  • #网络星期一#ChemiCloud：全托管VPS首月50%折扣，$39.98/月起，共享主机高达80

    摘要：今年的黑色星期五活动结束，马上开启了网络星期一活动，共享主机高达优惠，低至月托管主机续费永久折扣，月起全托管首月折扣，首购月，有需要的可以围观一下。 ChemiCloud今年的黑色星期五活动结束，马上开启了网络星期一活动，共享主机高达80%优惠，低至$1.58/月；托管主机续费80%永久折扣，$7.90/月起；全托管VPS首月50%折扣，首购$39.97/月，有需要的可以围观一下。 ...

    不知名网友 评论0 收藏0

发表评论

登陆后可评论

0条评论

muzhuyu

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<