原题链接

当涉及到频繁地改变元素位置的时候,我们考虑用链表解决问题,这里有两种解决方法

一、STL的List(deque貌似也可)

二、数组模拟链表

两种方法本质都是先找插入位置再插入

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 100010;
 4 char word[N];
 5 int main()
 6 {
 7     freopen("in.txt","r",stdin);
 8 //    freopen("out.txt","w",stdout);
 9     while(scanf("%s",word)!=EOF){//scanf("%s",word)!=EOF
10         //printf("%s\n",word);
11         list<char> lst;
12         auto it = lst.begin();
13         for(int i=0;i<strlen(word);i++){//这里使用auto i:word是错的 
14             if(word[i]=='[') it=lst.begin();
15             else if(word[i]==']') it = lst.end();
16             else lst.insert(it,word[i]);//使用迭代器模拟鼠标,不必想得太复杂,当光标移动到前面时,仍然是尾插 
17         }
18         for(auto its:lst) printf("%c",its);
19         printf("\n");
20     }
21     return 0;
22 }

STL

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 100010;
 4 char word[N];
 5 int main()
 6 {
 7 //    freopen("in.txt","r",stdin) ;
 8     while(scanf("%s",word+1)!=EOF){
 9         int idx = 0,head = 0,ne[N],e[N],last = 0;
10         ne[0] = -1;
11         int len = strlen(word+1);
12         for(int i=1;i<=len;i++){
13             if(word[i]==']') idx = last;
14             else if(word[i]=='[') idx = head;//选好插入位置 
15             else{
16                 e[i] = word[i];//本质就是在k的后面插入一个结点 
17                 ne[i] = ne[idx];
18                 ne[idx] = i;
19                 if(idx==last) last= i;//更新 
20                 idx = i;
21             }
22         }
23         for(int i=ne[head];i!=-1;i=ne[i]) printf("%c",e[i]);
24         printf("\n");
25     }
26 }

数组模拟

注意： 当涉及数组范围开得很大而又没有全部利用的时候,我们不用auto 遍历

补充：STL的代码,it保存的是初始的begin迭代器,当在it插入时,个人理解it随着所指向元素位置改变而改变(但是看调试又没有改变),这个问题让我有点费解

可能it = insert();it++更好理解点