题目链接：https://vjudge.net/problem/UVA-11988
题目大意：
键盘的home键和end键出现了问题。
在输入一段文本时，home键或end键可能会自动被按下，home键会使光标移动到文章开头，end键会使光标移动到文章结尾。
输入包含多组数据，每组数据一行，包含不超过100000个字母，表示输入文本。[表示home键按下，]表示end键按下。
对每组输入输出一行，表示你在显示屏上看到的文本。
Sample Input
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University
Sample Output
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University
stl 链表
#include <iostream> #include <cstdio> #include <string.h> #include <list> using namespace std; char str[1000100]; int main() { while(scanf("%s",str)!=EOF){ list<char> l; list<char>::iterator p = l.begin(); int len = strlen(str); for(int i=0; i<len; i++){ if(str[i]==‘[‘)p = l.begin(); else if(str[i]==‘]‘)p = l.end(); else l.insert(p, str[i]); } for(p = l.begin(); p!=l.end(); ++p)cout << *p; cout << endl; } return 0; }
模拟链表
#include <iostream> #include<string.h> #include <algorithm> using namespace std; const int maxn = 100000 + 5; char buf[maxn]; int Next[maxn]; int main(){ int cur, last,n; while (scanf("%s", buf+1)!=EOF){ n = strlen(buf + 1); cur = last = 0; for (int i = 1; i <= n; i++){ if (buf[i] == ‘[‘)cur = 0; //house键 else if (buf[i] == ‘]‘)cur = last; //end键 else{ Next[i] = Next[cur]; //字符i的下一个位置为cur的下一个位置 Next[cur] = i; //curr的下一个位置为i //更新cur和last if (cur == last)last = i; //cur等于i表示光标在显示屏最后一个字符 cur = i; //移动光标 } } Next[last] = 0; //结束位置 for (int i = Next[0]; i != 0; i = Next[i]) printf("%c", buf[i]); printf("\n"); } return 0; }
2018-03-30