首页 > 代码库 > Broken Keyboard（悲剧文本）
Broken Keyboard（悲剧文本）
你有一个键盘，键盘上所有的键都能正常使用，只是Home键和End键有时会自动按下。你并不知道这一情况，而是专心地打稿子，甚至连显示器都没开电源。当你打开显示器之后，展现在你面前的是一段悲剧文本。你的任务是根据给出的键盘上实际输入的内容，计算并输出这段悲剧文本（即显示器上展现的文本）
Input:
一行文本不超过1000000个字符，只包括字母、下划线、字符‘[‘（表示Home键）和字符‘]‘（表示End键盘）。
Output:
一个字符串，即符合题目描述的悲剧文本。
Example:
Input:
This_is_a_[Beijing]_tex
Output:
BeijingThis_is_a__text
___________________________________________________________________________________________________________
问题分析：
该问题最简单的想法是利用数组来保存这些数据，然后用一个变量来保存光标位置，输入一个字符相当于在数组中插入一个字符，但是没插入一个字符将要移动大量的数据，程序的开销会很大。
为了解决这个问题，我们可以利用静态链表解决这个问题
先用一个字符串将每个字符储存起来，s[1-n]，对每个s[i]都会对应一个next[i]游标，储存的是下一个结点的下标，同时利用一个curr，表示光标位置，并用last记录最后元素位置，s[0]是一个虚拟字符，用作头结点。
#include<iostream>#include<string>using namespace std;const int size=100000+1;int last; //显示屏上的最后一个字符int cur; //光标位置，总在当前s[i]的左方char s[size]; //用以储存stringint main(){ int next[size]={0}; //每个s[i]的游标，初始化为0 while(scanf("%s",s+1)==1) { //初始化 int n=strlen(s+1); //真正的字符从s[1]开始，s[0]是一个虚拟字符 last=0; cur=0; //重排next for(int i=1;i<=n;i++) { if(s[i]==‘[‘) cur=0; //home键 else if(s[i]==‘]‘) cur=last; //end键 else { next[i]=next[cur]; next[cur]=i; if(cur==last)last=i; //当从string的最后插入时，last要+1 cur=i; } } //输出 for(int j=next[0];j!=0;j=next[j]) //依据next中指定的顺序输出 cout<<s[j]; cout<<endl; } return 0;}
Broken Keyboard（悲剧文本）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。