链表Broken Keyboard (a.k.a. Beiju Text)

2019-11-08 20:05:46

字体：大中小

来源：转载

供稿：网友

https://vjudge.net/PRoblem/UVA-11988

Sample Input

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

Sample Output

BeijuThis_is_a__text Happy_Birthday_to_Tsinghua_University

1 题目给定一个字符串要求通过一序列的模拟输出最后的字符串 2 根据题目的意思[]，分别表示的是键盘上的home和end键，home键的作用是跳到起始位置，end的作用是到最后一个位置。

①汝佳神题，代码越看越屌，用数组实现，设计很巧妙。

②或者用list或者deque实现。

①

#include <stdio.h>#include<cstring>const int maxn = 100000+5;int last,cur,next[maxn];//cur为光标或者理解为标记 flag,temp char s[maxn];int main(int argc, char *argv[]){ while(scanf("%s",s+1)==1) { int n=strlen(s+1);//输入保存在s[1],s[2]..中 last = cur =0; next[0] =0; 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];//将cur一直传递储存下来 //遍历到i的时候能够跳回cur(数组中为下标为0)的位置 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;}遍历顺序

这里写图片描述

用deque实现

#include<deque>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int MAXN = 100010;char str[MAXN];deque<string>dqe;void insert(bool front , bool rear , string s){ if(front) dqe.push_front(s); if(rear) dqe.push_back(s);}void output(){ while(!dqe.empty()){ cout<<dqe.front(); dqe.pop_front(); } puts("");}void solve(){ int len = strlen(str); bool front , rear; string s = ""; front = false;//或改true，因为原来deq为空 rear = true;//或改为false for(int i = 0 ; i < len ; i++){ if(str[i] == '['){ insert(front , rear , s); s = ""; front = true; rear = false; } else if(str[i] == ']'){ insert(front , rear , s); s = ""; front = false; rear = true; } else{ s += str[i]; } } insert(front , rear , s); output();}int main(){ while(scanf("%s" , str) != EOF) solve(); return 0;}

③用list实现 STL的链表

#include<list>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int MAXN = 100010;list<char>ls;int main(){ char str[MAXN]; while(gets(str)){ ls.clear(); int len = strlen(str); list<char>::iterator it = ls.begin(); for(int i = 0 ; i < len ; i++){ if(str[i] == '[') it = ls.begin(); else if(str[i] == ']') it = ls.end(); else{ ls.insert(it,str[i]); } } for(it = ls.begin(); it != ls.end() ; it++) printf("%c" , *it); puts(""); } return 0;}

it==begin 在第一个位置插入即从前面插入 it==end 在末尾插入

这道题解法一很重要一定要学会使用解法二和解法三用到了deque和list 平时用不到的东西自然也没有想到不应该

参考博客http://blog.csdn.net/chenguolinblog/article/details/9494381

上一篇：String,StringBuilder,StringBuffer

下一篇：linux中passwd_shadow_group详解