题解 UVA11988 【Broken Keyboard (a.k.a. Beiju Text)】

UKE自动稽 · 2018-03-06 14:22:15 · 题解

【分析】 最简单的想法使用数组保存这段文字，然后用一个变量pos来保存“光标位置”，这样输入一个字符相当于在数组中插入一个字符（需要先把后面的字符全部右移，给新字符腾出位）。但是这样会超时，因为每输入一个字符都可能引起大量字符往后移。例如，2500000个a和[交替出现，则一共需要0+1+2+3+4+5+6+7+。。。。。2499999=6*10^12次字符移动。

所以要用链表实现。

指针链表：

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
struct Node {
    char c;
    Node *next;
};
Node *head;
Node *tail;
Node *p;
int main() {
    string words;
    while(cin >> words) {
        head = new Node;
        head->next = NULL;
        tail = head;
        p = head;
        for(int i = 0; i < words.length(); i++) {
            char c = words[i];
            if(c == '[') {  
                p = head;
            } else if (c == ']') {  
                p = tail;
            } else {
                Node *n = new Node;
                n->c = c;
                n->next = p->next;
                p->next = n;
                p = n;
                if(p->next == NULL) {
                    tail = p;
                }
            }
        }
        for(p=head->next;p!=NULL;p=p->next) 
        cout<<p->c;
        printf("\n");
    }
    return 0;
}

文刂氵女亻圭大氵去：

#include<iostream>  
#include<cstdio>  
#include<cmath>  
using namespace std;  
char s[100005];  
int next[100005];//next存的值为当前光标的位置后接的下一个值的位置；  
int main()  
{  
    int cur,last;  
    while(~scanf("%s",s+1))//从1，2，3，4，。。。n开始存。  
    {  
        cur=last=0;  
        next[0]=0;//存储链表第一个元素的位置  
        for(int i=1;s[i]!='\0';i++)  
        {  
            char ch=s[i];  
            if(ch=='[') cur=0;//光标移动到最前面  
            else if(ch==']') cur=last;//next[last]=0；把这个等价看作next[0]，类似于从头开始存，，  
            else  
            {  
                next[i]=next[cur];//输入的值连往next光标位置存的值；  
                next[cur]=i;//当前光标连接往后一个输入的值  
                if(last==cur) last=i;  
                cur=i;//光标变到后一个值得位置  
            }  
        }  
        for(int i=next[0];i!=0;i=next[i])  
        {  
            printf("%c",s[i]);  
        }  
        printf("\n");  
    }  
    return 0;  
}