UVA11988:悲剧文本(模拟链表)

You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed (internally). You’re not aware of this issue, since you’re focusing on the text and did not even turn on the monitor! After you finished typing, you can see a text on the screen (if you turn on the monitor). In Chinese, we can call it Beiju. Your task is to find the Beiju text.

你在电脑上敲字,但是键盘是坏的,额,还不是特别坏,只是键盘有时候会自动按下Home键和End键。你敲字的时候没看显示器,光看手稿上的文字了。等你敲完整篇手稿,你发现杯具了......你需要找到那些错的文字。

Input There are several test cases. Each test case is a single line containing at least one and at most 100,000 letters, underscores and two special characters ‘[’ and ‘]’. ‘[’ means the “Home” key is pressed internally, and ‘]’ means the “End” key is pressed internally. The input is terminated by end-of-file (EOF). Output For each case, print the Beiju text on the screen.

Sample Input

This_is_a_[Beiju]_text

[[]][][]Happy_Birthday_to_Tsinghua_University

Sample Output

BeijuThis_is_a__text

Happy_Birthday_to_Tsinghua_University

概译:我们在用键盘输入字符串,如果出现' [ '光标就跳到最前面,如果出现' ] '就跳到最后面,给出输入时的字符串输出实际得到的字符串,详见样例。

思路:水题轻喷……模拟,链表插入,可以用数组实现模拟链表。我模拟链表不太熟,第一次是用STL模拟的。可以用一个双端队列deque储存最终结果,遇到一个' [ '就把后面的字符放在stack里,再遇到' [ '或' ] '时把stack里的字符放在deque的front里。PS:可能WA的数据:abc[123[456[ef

STL比较慢,100msAC

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    while(getline(cin,s))
    {
        s+=']';
        deque<char>dq;
        stack<char>st;
        bool state=false;

        for (int i = 0; s[i]; ++i)
        {
            if (s[i]=='[')    state=true;    
            else if (s[i]==']')    state=false;

            if(state)   
            {
                if(s[i]!='[')    
                    st.push(s[i]);
                else
                    while(!st.empty())
                    {
                        dq.push_front(st.top());
                        st.pop();
                    }
            }
            else
            {
                if(s[i]!=']')
                    dq.push_back(s[i]);
                while(!st.empty())
                {
                    dq.push_front(st.top());
                    st.pop();
                }
            }     
        }

        while(!dq.empty())
        {
            printf("%c",dq.front());
            dq.pop_front();
        }
        printf("\n");
    }
    return 0;
}

模拟链表是用一个next数组代替链表中的next指针,比如第一个字符s[1]的下一个是s[2],则next[1]=2。思想上和链表是一样的。另外众所周知,链表的题常常会把第0个作为不储存数据的辅助头结点,第一个下标才开始储存数据。

标程的思路是设置一个光标cur,但这个cur不是当前遍历到的位置i,而代表着位置i的字符应该插入在cur的右侧。期间cur有时会跳至左端即cur=0;有时要回到右端,所以还要开一个last变量保存最右端的下标,使cur=last跳回右端。

代码更精简,30ms,如下:

#include <bits/stdc++.h>
using namespace std;
#define maxl 100005

int main()
{
    char s[maxl];
    while(~scanf("%s",s+1))
    {
        int Next[maxl]={0};
        int cur=0,last=0;

        for (int i = 1; s[i]; ++i)
        {
            if(s[i]=='[')    cur=0;
            else if(s[i]==']')    cur=last;
            else
            {
                //链表插入操作
                Next[i]=Next[cur];
                Next[cur]=i;
                //last的更新
                if(cur==last)    last=i;
                //cur的更新
                cur=i;
            }
        }

        for (int i = Next[0]; i != 0; i = Next[i])
            if (s[i]!='['&&s[i]!=']')
                printf("%c",s[i]);
        printf("\n");    
    }
    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-07-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏lgp20151222

java 核心技术 读后总结

如 AbcController和AbcService两个文件,javac Abc*.java 即可一次性编译两个

8720
来自专栏java架构师

【SQL Server】系统学习之三:逻辑查询处理阶段-六段式

一、From阶段 针对连接说明: 1、笛卡尔积 2、on筛选器 插播:unknown=not unknuwn 缺失的值; 筛选器(on where having...

371110
来自专栏人工智能LeadAI

共享变量 tensorflow解读

你可以在怎么使用变量中所描述的方式来创建,初始化,保存及加载单一的变量.但是当创建复杂的模块时,通常你需要共享大量变量集并且如果你还想在同一个地方初始化这所有的...

13220
来自专栏小灰灰

ForkJoin 学习使用笔记

ForkJoin 学习使用笔记 Fork/Join框架是Java7提供了的一个用于并行执行任务的框架, 是一个把大任务分割成若干个小任务,最终汇总每个小任务结...

324100
来自专栏偏前端工程师的驿站

PLT:说说Evaluation strategy

Brief                                 在学习方法/函数时,我们总会接触到 按值传值 和 引用传值 两个概念。像C#是按值传...

21760
来自专栏海天一树

图的广度优先搜索

广度优先搜索算法是最简便的图的搜索算法之一,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索...

15320
来自专栏Python小屋

Python花式编程案例锦集(1)

首先解答上一篇文章详解Python中的序列解包(2)中最后的习题,该题答案为5,表达式功能为迭代求解序列中元素的最大值。 -----------------分割...

41850
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版7.7节 set对象

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

11410
来自专栏desperate633

HashMap 与 HashTable的对比

而负载因子表示一个散列表的空间的使用程度,有这样一个公式:initailCapacity*loadFactor=HashMap的容量。

9720
来自专栏我的技术专栏

C++ 顺序容器基础知识总结

22850

扫码关注云+社区

领取腾讯云代金券