UVA11988 破损的键盘 Broken Keyboard (a.k.a. Beiju Text)

UVA11988 破损的键盘 Broken Keyboard (a.k.a. Beiju Text)

​​题意翻译​​

你在输入文章的时候，键盘上的Home键和End键出了问题，会不定时的按下。你却不知道此问题，而是专心致志地打稿子，甚至显示器都没开。当你打开显示器之后，展现你面前的数一段悲剧文本。你的任务是在显示器打开前计算出这段悲剧的文本。 给你一段按键的文本，其中’[‘表示Home键，’]'表示End键，输入结束标志是文件结束符（EOF）。 输入

This_is_a_[Beiju]_text[[]][][]Happy_Birthday_to_Tsinghua_University

输出

BeijuThis_is_a__textHappy_Birthday_to_Tsinghua_University

思路1:由于home 和end键,所以会涉及到字符的插入,如果使用数组,那么插入元素会涉及到数组元素的移动,时间复杂度是很大的。经常插入，我们想到了链表这一数据结构.通过判断home键/end键我们改变迭代器的位置,然后进行后序字符的插入。记得insert函数使用后会返回插入的字符的迭代器（指向该字符），然后插入下一个字符之前记得更新迭代器的位置，不然就会出错我就在这里错了好久

参考代码1

#includeusing namespace std;string str;list L;void solve(string &s){ L.clear(); list::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::iterator it1 = L.begin(); it1 != L.end(); it1++){ cout<<*it1; } cout<>str){ solve(str); } return 0;}

思路2：由于字符串具有拼接简便的特性，所以可以利用字符串来搞。对于每个字符串s，遍历每个字符，然后判断，如果是home键,就把之后的字符放到一个临时字符串s2中,然后当下一次遇到end键之时进行更新主串s3 = s2+s3; 最后一步也要需要处理.

参考代码

#includeusing 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<>s){ solve(s); } return 0;}

注意:思路二存在一定的漏洞,可能某些细节没处理好,样例通过了但不能AC.希望能够看出问题的小伙伴留言,交流下.

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。