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
新聞熱點
疑難解答
