#1039:字符串消除

作者: 贪婪的君子 | 来源:发表于2018-03-30 21:34 被阅读16次

提取主要需求:即消除连续出现的两个以上的字符,直到新生成的字符串不满足条件。

初步分析

设置一个flag标志前一次循环是否有消除操作,如果有,则开始下一次的循环。可该如何判断是否可以消除字符呢?

  • 此时追加一个for循环,将字符串的起始位置设为标记点,检查其后的字符是否与标记点字符相同;

  • 若相同,则将其位置置为终止位置;若不同,则删除首位置元素(放入最终字符串变量result中,该字符串记录算法终止时不可消除的字符);

伪代码如下:

flag = true; result = "";
while flag 
    j = 2;
    len = input.length;
    for i = 1 to len
        if 下一个字符与首位置字符相同 then : j = j+1;
        else if j > 1 then : 删除j之前的元素; flag = true;
                             截取j之后的子串,替换input;
        else 将首元素加入result,用作下一轮的while消除;
    input = result;

插入操作则可使用for循环,遍历所有课插入位置,得到最高分。

再度思考

基于初步的分析,不难看出插入字符操作并未要求得到插入的具体位置,那么这是否意味着我们可以先进行消除得到一个未插入状态的最终字串,然后再进行插入得到最终字串呢?

好像是可以的?但实际并不对,思考有这种情况:“BCBB”,先进行消除得到未插入字符状态的最终字串,即“BC”,然后插入再消除,发现无论如何插入,最终字串都至少含有一个字符。显然,如果是先进行插入操作得到“BCCBB”,再进行消除得到的最终字串为空串

对比之下可知,这一步是不可实现的。

那么,消除函数应该是可以更进一步的吧?在初步分析中,假设while循环执行N次(但实际上是不可能执行N次的),for循环N次,我们只记if中的判断条件为有效的基础运算,即3次(最大),则有3N*N = 3N2 = O(N2) 的最坏时间复杂度,这么看来,是有提升空间的。

基于以上分析,这一次的消除函数选用来进行:

  1. 若上一次有发生消除操作,则进入本次的消除检查。
  2. 从字符串其实位置开始,主次入栈,每次如栈前检查栈顶元素 == 准备入栈元素。
  3. 若不等,栈空间>2则舍弃栈中所有元素,并压入下一元素;否则弹出栈顶元素,计入result字串中。

算法结束时返回最终串与初始串的长度差。

粗略计算,while循环N次(实际并不是),内部的有效基本运算记为m,则算法时间复杂度为 m*N = O(N) 线性阶。

不完整的伪代码如下(这里其实有个小问题使得算法没能达到线性阶,在哪里呢?):

flag = true; i = 0; result = "";
while flag 
    s.push(input[i]);
    while input[i++] = s.top()
        s.push(input[i];
    if s.size() > 1 then : s.clear(); flag = true;
    else result += s.top(); s.pop();
    input = result; result = "";

这里只有分析,具体的AC代码和题目链接我都放在了GitHub上,点蓝字即可转到,或者:https://github.com/ai977313677/hihoCoder
如果你有更好的想法,欢迎讨论。

相关文章

  • #1039:字符串消除

    提取主要需求:即消除连续出现的两个以上的字符,直到新生成的字符串不满足条件。 初步分析 设置一个flag标志前一次...

  • hihoCoder1039 字符消除

    题目: 时间限制:1000ms单点时限:1000ms内存限制:256MB描述小Hi最近在玩一个字符消除游戏。给定一...

  • ES6 - ECMA2019 - 学习总结

    新的概念与方法 概略图: 基本使用 字符串扩展 trimStart() 消除字符串行首空格 trimEnd() 消...

  • 1039

  • 1039

    2022.10.31 星期一 多云 今早送云灿去站点儿然后做核酸。 这两天工作上比较忙碌,要干的事都挤...

  • 如何拆分字符串后,消除空白成员

    拆分字符串后,消除 string.IsNullOrWhiteSpace 成员 方案1 方案2 相关链接[http:...

  • 【基础知识】消除ES6模板字符串中的空格

    转:消除ES6模板字符串中的空格 在开发中经常要用模板字符串,在拼接HTML文件时会遇到模板字符串中的空格问题比如...

  • 亲子(1039)

    2020.2.4 星期二 阴 今日立春 春天到了,愿扫除一切阴霾,还我们日朗风清,花香鸟鸣(〜^㉨...

  • 日记1039

    2022年11月23日,星期日 晴天 周日,完完全全属于自己的一天。儿子早上六点半出发上学,所以早上五点不到半起来...

  • 关于文本换行处理的问题

    对这类文本的换行处理消除字符串间的换行,首先需要遍历目录下的所有文件。打印出一个文本中的字符串检查字符串的类型,每...

网友评论

    本文标题:#1039:字符串消除

    本文链接:https://www.haomeiwen.com/subject/rgkwcftx.html