首页 > 代码库 > UVa11988 Broken Keyboard (a.k.a. Beiju Text) （链表）
UVa11988 Broken Keyboard (a.k.a. Beiju Text) （链表）
链接：http://acm.hust.edu.cn/vjudge/problem/18693
分析：链表。用nxt[i]保存s[i]右边字符在s中的下标。增加一个虚拟字符s[0]，那么nxt[0]就是显示屏中最左边的字符。cur表示光标位置左边的字符在s数组中的下标，last表示显示屏中最后一个字符在s数组中的下标。其实就是用nxt链表重新组织s数组的输出顺序，输入一个字符，先将新插入字符的nxt[i]指向nxt[cur],再将nxt[cur]指向i，就是在链表元素cur后插入元素i,更新最后一个字符的编号也就是链表中最后一个元素,移动光标位置，移动到新插入元素（插入字符在s中的下标）结点的位置。‘[‘移动到最左边cur=0,‘]‘移动到最后。
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 5 const int maxn = 100000 + 5; 6 7 int cur, last, nxt[maxn]; 8 char s[maxn]; 9 10 int main() {11 while (scanf("%s", s + 1) == 1) {12 int n = strlen(s + 1);13 last = cur = 0;14 nxt[0] = 0;15 for (int i = 1; i <= n; i++) {16 if (s[i] == ‘[‘) cur = 0;17 else if (s[i] == ‘]‘) cur = last;18 else {19 nxt[i] = nxt[cur];20 nxt[cur] = i;21 if (cur == last) last = i;22 cur = i;23 }24 }25 for (int i = nxt[0]; i; i = nxt[i])26 printf("%c", s[i]);27 printf("\n");28 }29 return 0;30 }
UVa11988 Broken Keyboard (a.k.a. Beiju Text) （链表）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。