传送门

题目大意:一个字符串,将[]内的字符提前。

题解:链表,数组元素高效交换

cur表示目前元素插入下标为cur的元素后面。

所以,假设目前把下标为i的元素插到cur后面。

那么,next[i]=next[cur],为cur后面的元素成为i后面的元素

next[cur]=i,cur后面的元素就是i了。

如果遇到'[',说明要把后面到'['插到开头了,cur赋值为0,

last表示最后输出答案的下标。

如果遇到']',那么cur=last,继续从最后一个元素开始插入。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100009
using namespace std; char s[maxn];
int cur,last,next[maxn]; int main(){
while(scanf("%s",s+)!=EOF){
int len=strlen(s+);
next[]=;last=cur=;
for(int i=;i<=len;i++){
if(s[i]=='[')cur=;
else if(s[i]==']')cur=last;
else{
next[i]=next[cur];
next[cur]=i;
if(cur==last)last=i;
cur=i;
}
}
for(int i=next[];i;i=next[i])
printf("%c",s[i]);
printf("\n");
}
return ;
}

AC

05-20 22:09
查看更多