(链表,插入元素)破损的键盘

xiaoxiao2021-03-01  10

题目:

你有一个破损的键盘。键盘上的所有键都可以正常工作,但有时Home键或者End键会自 动按下。你并不知道键盘存在这一问题,而是专心地打稿子,甚至连显示器都没打开。当你 打开显示器之后,展现在你面前的是一段悲剧的文本。你的任务是在打开显示器之前计算出 这段悲剧文本。 输入包含多组数据。每组数据占一行,包含不超过100000个字母、下划线、字符“[”或 者“]”。其中字符“[”表示Home键,“]”表示End键。输入结束标志为文件结束符(EOF)。输 入文件不超过5MB。对于每组数据,输出一行,即屏幕上的悲剧文本。 样例输入: This_is_a_[Beiju]_text [[]][][]Happy_Birthday_to_Tsinghua_University 样例输出: BeijuThis_is_a__text Happy_Birthday_to_Tsinghua_University

分析与解答:

这题怎么说呢,刘汝佳一上来就把链表的核心抛出来了,我足足看了两个小时才理解,不过利用数组表示单链表也掌握了 0.为了方便起见,常常在链表第一个元素之前放一个虚拟节点s[0] 1.光标cur,最后一个字符编号last,其实只是由于这题home,end的条件限制 如果用数组建立单链表,只需要next[i]和s[i] 2.其中next[i]是s[i]连的下一个字符的编号,比如: s[0],next[0]=3连下一个字符-> s[next[0]],next[next[0]] 3.在本题中,如果next[i]=0,说明不知道这个节点连哪个下一个节点,如果全部插入完节点,遇到next[i]=0,就意味着这个链表已经结束 所以有如下对链表遍历的方法:

for(int i=next[0];i!=0;i=next[i]) printf("%c",s[i]);

4.下面说说怎么插入 s[i]对应一个next[i],那么s[i]下一个连的是s[next[i]],next[next[i]] 如果在s[i]后面插入s[j]next[j] 只需next[j]=next[i],next[i]=j 新节点j先插到后面next[i]的前面,再把前面i的后面连的那个节点改为新插入的那个j 5.再来说说本题 a.只需改变s的输出顺序,输出s[next[i]] b.多了个[],就是说插入的位置会发生变化,怎么办? 光标派上用场, 先看一般情况:s[0]0a1b2c3,注意光标的意思,假设光标一开始是0,你输入a,那1就是此时光标的位置,假设s[1]=a,那我们还没遍历到b的时候,next[1]=0(看不懂得话看上面的黑色重点字体),next[0]=1,这是在s[0]后面插入s[1],(看不懂的话看重新看上面的4),此时如果光标等于最后一个字符的编号(比如last,cur初始值是0,那么你加了一个字符,最后一个字符编号自然需要更新)就更新最后一个字符编号,然后把光标改成1 再看特殊的: 如果碰见[,光标跑到0了,把cur改成0 碰见],光标跑到最后一个了数的后面了,你们发现了吗,最后一个数的下标正好是光标的下标,所以cur=last 6.悟道是acmer的必经之路,多看几个小时,就明白了

#include <cstdio> #include <cstring> const int maxn=100000+5; int last,cur,next[maxn]; char s[maxn]; int main(){ while(scanf("%s",s+1)){ int n=strlen(s+1); last=cur=0; next[0]=0; for(int i=1;i<=n;i++){ char ch=s[i]; if(ch=='[') cur=0; else if(ch==']') cur=last; else{ next[i]=next[cur]; next[cur]=i; if(cur==last) last=i; cur=i; } } for(int i=next[0];i!=0;i=next[i]) printf("%c",s[i]); printf("\n"); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-4050034.html

最新回复(0)