当前位置: 代码迷 >> 综合 >> UVa 11988 Broken Keyboard (a.k.a. Beiju Text)【链表】
  详细解决方案

UVa 11988 Broken Keyboard (a.k.a. Beiju Text)【链表】

热度:71   发布时间:2024-01-27 01:01:51.0

读了半天题,没看懂什么意思。
然后发现是这样的,home和end键按下去后会回到这一行的开始和结束。如果不知道这个可能不会读懂题目。(这俩键平时也没人用啊,在键盘的角落上,出个题也不解释一下)

下面说题:
数组复杂度太高,超时,用链表。
也就是说,一旦按下home键,之后的文字就接在头部,一旦按下end键,之后的文字就接在尾部,这样就简单了。

根据home和end来构建一个链表,用next数组表示,然后根据链表输出。

next[i] = next[cur];
next[cur] = i;
if(cur == last) last = i;
cur = i;
第一句用来保证更新链表终点
第二句用来更新下一个点
第三句及时更新尾指针
第四句更新当前位置

参照紫书代码:

const int maxn = 100000+5;
int last,cur,next[maxn];
char s[maxn];int main(){while(scanf("%s",s+1)==1){int n = strlen(s+1); //保存在s[1],s[2]...中last = cur = 0;next[0] = 0; //next[i]的意思是指第i位置的下一个位置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;
}
  相关解决方案