【題解】UVa 11988 【Broken Keyboard (a.k.a. Beiju Text)】

人生苦短,我用STL

显然本题应该使用链表这种数据结构,因为炒鸡多的数据会被移动,如果使用数组,那时间复杂度灰常大。

STL已经帮咱们写了一个链表:list

使用时只需导入头文件list,然后用命名空间std即可;

注意这个玩意在内部是离散放置数据的,它没有定义[]操作附,所以就不支持随机访问。不过它在任意位置的插入和删除都快的飞起,因为只需要改一下指针就好了,而且这些细节都是封装好了的,咱们就只管调用就好了。(人生苦短,我用STL)

正应为它无法使用[]运算符,所以应该使用迭代器来访问,,,迭代器可是STL的灵魂呢

详细的细节在代码里。

//头文件
#include<cstdio>
#include<list>
#include<iostream>
#include<string>

//不想导入整个命名空间是因为会有变量名重复,然后我想要的变量名无法使用,不开心qwq
void solve(std::string s){
    std::list<char> text;//创建一个保存char类型的链表

    std::list<char>::iterator it = text.begin();//创建迭代器并赋初值

    //判断每一位
    for(int i = 0;i < s.length();i++){
        char c = s[i];

        if(c == '['){//如果是Home键
            it = text.begin();//就把迭代器指向开头,就是Home键的功能啦Da Da
        }else if(c == ']'){//如果是End键
            it = text.end();//就把迭代器指向末尾,就是End键的功能
        }else{//并在不会把“[”和“]”输入到list里面去,仔细想想为啥咯
            it = text.insert(it,c);//将数据按照上面的指针方向插&#x2642;入(qwq不要和谐我啦)
            it++;//然后指向下一位
        }
    }

    //依靠迭代器顺序输出list的内容
    for(it = text.begin();it != text.end();it++){
        std::cout << *it;
    }

    s.clear();//清空好习惯

    std::cout << std::endl;//记得换行
}

int main(){
    std::string s;//读入
    while(std::cin >> s){
        solve(s);//解题
    }

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注