【日常学习】【非指针链表】Uva11988 - Broken Keyboard (a.k.a. Beiju Text)题解

浅浅的花香味﹌ 2022-08-07 02:50 103阅读 0赞

这道题目拖了好几天，因为鄙人有两大天敌——链表和树TUT看了这个题材知道原来链表可以不用指针写，不过原理也是一样的，相当于是用数组模拟了个链表而不实用结构体，结构体里的指针就换成了两个变量cur和last了。这道题目本来测出来非常奇怪和合因为UVA AC HDU TLE SPOJ RE我正在奇怪，才发现同名的不同题目有三道TUT

题目的详解已经写在了注释里，上代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    
    const int maxn=100000+5;
    int last,cur,next[maxn];
    char s[maxn];
    
    int main(){
    	while (scanf("%s",s+1)==1){
    		int n=strlen(s+1);//输入从s[1]开始存储 
    		last=cur=0;
    		next[0]=0;//0位置的下一个数初始化为0 ，会改变 
    		for (int i=1;i<=n;i++){//按照字符的编号排列顺序输出字符，顺序是排列好的编号序列，该序列储存在next中 
    			char ch=s[i];
    			if (ch=='[') cur=0;
    			else if (ch==']') cur=last;
    			else {
    				next[i]=next[cur];//现在字符位置的下一个是当前光标的下一个【未插入之前当前光标下一个】 a|c 
    				next[cur]=i;//当前光标的下一个是现在插入的字符位置，即此时光标还是在原来的前一个字符后面 a|bc 
    				if (cur==last) last=i;//如果当前已是最后，最后编号更新 last指向最后一个 next[last]为空 先比较再移动cur 
    				cur=i;//移动光标到当前插入字符后面 ab|c 
    			}
    		}
    		for (int i=next[0];i!=0;i=next[i]) printf("%c",s[i]);//注意占位符，另外其实next数组应该初始化为0 
    		printf("\n");
    	}
    	return 0;
    }

——高祖尝徭咸阳，纵观，观始皇帝，喟然太息曰：“嗟乎，大丈夫当如此也！”