问题描述:

       你有一个破损的键盘。键盘上所有的键都可以正常工作,但有时候Home键或者End键会自动按下。你并不知道键盘存在这一问题,而是专心打稿子,甚至连显示器都没打开。当你打开显示器后,展现在你面前的是一段悲剧文本。你的任务是在打开显示器之前计算出这段悲剧文本。

       输入包含多组数据。每组数据占一行,包含不超过100000个字母、下划线、字符“【”或者“】”。其中字符“【”表示Home键,“】”表示End键。输入结束标志为文件结束符(EOF)。输入文件不超过5MB。对于每组数据,输出一行,即屏幕上的悲剧文本。

样例输入:

This_is_a_[Beiju]_text

样例输出:

BeijuThis_is_a_text

分析:(数据结构一链表的简单实现)

1.本题最简单的想法就是直接开数组保存,再用pos保存光标位置,但是由于数组中插入元素操作的时间复杂度为O(n),当数据量过大时时间复杂度爆炸。

2.因此我们可以运用数组模拟链表来保存字符。创建一个next数组来保存输出的顺序,cur表示模拟当前光标的位置,last表示文本末端。

这道题我当时对着书上的代码看了半天,也用手模拟着跑过好几次,感觉也是很玄乎Orz..

 话不多说,直接上代码

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX 100005
 4 char s[MAX];
 5 int next[MAX];
 6 int main()
 7 {
 8     while(scanf("%s",s+1)!=EOF)
 9     {
10         int i,cur=0,last=0,len=strlen(s+1);
11         next[0]=0;
12         for(i=1;i<=len;i++)
13         {
14             char ch=s[i];
15             if(ch=='[') cur=0;
16             else if(ch==']') cur=last;
17             else
18             {
19                 next[i]=next[cur];                //类似于  i->next=cur->next;cur->next=i; 
20                 next[cur]=i;
21                 if(cur==last) last=i;
22                 cur=i;
23             }
24         }
25         for(i=next[0];i!=0;i=next[i])        //类似于通过i=next[i]来访问数组
26             printf("%c",s[i]);
27         printf("\n");
28     }
29     return 0;
30
31 } 

还是很值得反复去琢磨一下的。如果有dalao有更好的方法,或者有更清晰明确的理解,欢迎在文章下面评论一下。 Orz

12-24 00:52