题意翻译
你在输入文章的时候，键盘上的Home键和End键出了问题，会不定时的按下。你却不知道此问题，而是专心致志地打稿子，甚至显示器都没开。当你打开显示器之后，展现你面前的数一段悲剧文本。你的任务是在显示器打开前计算出这段悲剧的文本。 给你一段按键的文本，其中’[‘表示Home键，’]'表示End键，输入结束标志是文件结束符（EOF）。
输入
This_is_a_[Beiju]_text [[]][][]Happy_Birthday_to_Tsinghua_University
输出
BeijuThis_is_a__text Happy_Birthday_to_Tsinghua_University
思路1:由于home 和end键,所以会涉及到字符的插入,如果使用数组,那么插入元素会涉及到数组元素的移动,时间复杂度是很大的。经常插入，我们想到了链表这一数据结构.通过判断home键/end键我们改变迭代器的位置,然后进行后序字符的插入。记得insert函数使用后会返回插入的字符的迭代器（指向该字符），然后插入下一个字符之前记得更新迭代器的位置，不然就会出错我就在这里错了好久
参考代码1
#include<bits/stdc++.h> using namespace std; string str; list<char> L; void solve(string &s){ L.clear(); list<char>::iterator it = L.begin(); for(int i = 0; i < s.size();i++){ if(s[i]=='['){ it = L.begin(); }else if(s[i]==']'){ it = L.end(); }else{ it= L.insert(it,s[i]);//在it后面插入一个字符 it++; } } for(list<char>::iterator it1 = L.begin(); it1 != L.end(); it1++){ cout<<*it1; } cout<<endl; } int main() { while(cin>>str){ solve(str); } return 0; }
思路2：由于字符串具有拼接简便的特性，所以可以利用字符串来搞。对于每个字符串s，遍历每个字符，然后判断，如果是home键,就把之后的字符放到一个临时字符串s2中,然后当下一次遇到end键之时进行更新主串s3 = s2+s3; 最后一步也要需要处理.
参考代码
#include<bits/stdc++.h> using namespace std; string s; void solve(string &s){ string s2 = "",s3 = "";//s2:用于暂存头部操作的字符串 s3 :主字符串 int flag = 0;//用于标记在头部操作还是尾部 for(int i = 0; i < s.length(); i++){ if(s[i]=='['){ flag = 1;//标记光标最前面 }else if(s[i]==']'){ s3 = s2+s3; s2 = ""; flag = 0;//最后面 }else{ if(flag){ s2 += s[i]; } else{ s3 += s[i]; } } } s3 = s2+s3; cout<<s3<<endl; } int main() { while(cin>>s){ solve(s); } return 0; }
注意:思路二存在一定的漏洞,可能某些细节没处理好,样例通过了但不能AC.希望能够看出问题的小伙伴留言,交流下.
