UVA11988(破损键盘) 使用数组模拟链表插入

开始刷数据结构相关的题了，在笔试和面试过程中如果要写出指针形式的链表时间上可能不够。该题很好地训练了怎么使用数组来模拟链表
破损的键盘（又名：悲剧文本）（Broken Keyboard（a.k.a. Beiju Text）,
UVa 11988）
你有一个破损的键盘。键盘上的所有键都可以正常工作，但有时Home键或者End键会自
动按下。你并不知道键盘存在这一问题，而是专心地打稿子，甚至连显示器都没打开。当你
打开显示器之后，展现在你面前的是一段悲剧的文本。你的任务是在打开显示器之前计算出
这段悲剧文本。
输入包含多组数据。每组数据占一行，包含不超过100000个字母、下划线、字符“[”或
者“]”。其中字符“[”表示Home键，“]”表示End键。输入结束标志为文件结束符（EOF）。输
入文件不超过5MB。对于每组数据，输出一行，即屏幕上的悲剧文本。
样例输入：
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University
样例输出：
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

按照紫书中的讲解，最简单的想法便是用数组来保存这段文本，然后用一个变量pos保存“光标位置”。这样，输入一个字符相当于在数组中插入一个字符（需要先把后面的字符全部右移，给新字符
腾出位置）。很可惜，这样的代码会超时。为什么？因为每输入一个字符都可能会引起大量字符移动。在极端情况下，例如，2500000个a和“[”交替出现，则一共需要0+1+2+…+2499999=6*1012次字符移动。解决方案是采用链表（linked list）。每输入一个字符就把它存起来，设输入字符串是s[1～n]，则可以用next[i]表示在当前显示屏中s[i]右边的字符编号（即在s中的下标）。
使用了一个next数组来进行位置索引，用cur和last变量来记录字符串删除起始点和终止点。最后输出由i=Next[0]开始，i==0时作为停止条件，i = Next[i]作为每次循环的刷新。

这里提供两幅图来理解这个算法，next数组里面存的值是指向了下一次next数组索引的序号以及这次我们在字符串数组s中索引到的值。第一幅是无’[’ ‘]’的情况

这里写图片描述

// UVA11988（破损键盘）.cpp : 定义控制台应用程序的入口点。
//

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

char s[101000];
int Next[101000];

int main()
{
    int cur, last;//cur为光标位置，last为显示屏最后一个字符
    while (~scanf("%s", s + 1))
    {
        memset(Next, 0, sizeof(Next));
        int len = strlen(s + 1);
        Next[0] = 0;
        cur = last = 0;
        for (int i = 1; i <= len; i++)
        {
            if (s[i] == '[')
                cur = 0;
            else if (s[i] == ']')
                cur = last;
            else
            {
                //模拟插入链表过程
                Next[i] = Next[cur];//第i个字符指向光标位置
                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");
        memset(s, 0, sizeof(s));
    }

    return 0;
}

UVA11988(破损键盘) 使用数组模拟链表插入

浏览过的版块