专栏首页Java小白成长之路刷题第3篇:重复字符串的删除

刷题第3篇:重复字符串的删除

题目描述

LeetCode----T1209

给你一个字符串 s,「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母,并删除它们,使被删去的字符串的左侧和右侧连在一起。你需要对 s 重复进行无限次这样的删除操作,直到无法继续为止。在执行完所有删除操作后,返回最终得到的字符串。本题答案保证唯一。

示例如下所示:

解题思路

当时看到这道题的第一印象,觉得就是循环遍历,直到没有可以再次删除的重复字符串为止。但是这样会出现一种浪费,每一次的遍历只能删除当前字符串中连接在一起的字符串。

比如,K=3,S=“aabbdddbcceeecf”,当我们第一次进行遍历的时候,只能后删除“ddd”和“eee”,然后得到一个新的字符串,再去删除新字符串中剩下的重复字符串。这显然会导致较高的时间复杂度。

于是就想着换一个思路来解决,我们再引入一个容器,用于存放S中每个字符char出现时,在char相邻的前一个字符char是否与当前的char相同,如果相同,我们就将前一个char连续的次数加1,当做当前char的连续出现的次数。

于是我们可以从新的容器中获取每个字符已经重复的次数,当此字符的重复次数等于k的时候,则进行删除操作。

下面会提供两种解法,解法一是我自己的代码,时间和内存都消耗较大,作为一个反面教材吧,突出一下解法二的优越。

实现代码一:

public String removeDuplicates(String s, int k) {
    int count = 1 ;
    int lastIndex = -1;
    StringBuilder sb = new StringBuilder();
    List<Integer> sb1 = new ArrayList<>();//记录每个字符对应的重复次数
    for (char c : s.toCharArray()) {
        if(sb.length()>0 && sb.charAt(lastIndex)==c){//sb的最后字符与新的字符c相等
            count = sb1.get(lastIndex) + 1;//重复的字符数目+1
            if (count == k){//找到了连续的K个字符
                sb.delete(lastIndex-k+2,lastIndex+1);
                List<Integer> temp = sb1.subList(0, lastIndex - k + 2);
                sb1 = temp;
                lastIndex -= k-1;
            }else{//没有找到连续的k个字符,继续将其增加在sb的后面
                sb.append(c);
                sb1.add(count);
                lastIndex++;
            }
        }else {//当前stack为空,或者顶部元素与新元素c不相同
            count = 1;//则计数置位为1
            sb.append(c);
            sb1.add(count);
            lastIndex++;
        }
    }
    return sb.toString();
}

上面想法的实现也踩过一些坑,也与大家分享一下:

  1. 最开始我使用的是stack来存放每一个字符,然后将每一个遍历的s的字符与对应stack.peak()进行比较,然后计数,完成相应的stack.pop()操作即可。可是得到最后的结果之后,使用stack.toString()转换为字符串操作,得到的是一个数组形式的字符串,数组中存放的是每一个character元素。并不是最后想要的字符串形式。
  2. 面对上面的问题,有一种解决方案:可以再使用一次循环,遍历stack,将所有的元素重新用StringBuilder来接受,然后转化为字符串即可。但是这种方法当时没有想到,事后才想起来的。我当时就直接将stack换掉,使用StringBuilder来作为容器进行接收字符,同时也使用另一个StringBuilder类型的sb1对象,来接收每一次的字符重复次数。于是就产生了另一个问题。
  3. 当我使用sb1(SringBuilder类型)进行接收的时候,我忽略了一点,StringBuilder类型在取出每一个索引的位置时,仅仅取出一个字符。这会产生一个问题,比如:一个字母“c”重复了11次,即:count=11,那么我使用sb1.append(count)的时候,sb1的最后面直接增加一个11,可是我使用lastIndex进行取出的时候,sb1.get(lastIndex)取出来的是一个字符“1”,而不是"11",这会导致计数的错误。
  4. 于是,我就在想用什么类型来存储计数值。用数组么?我觉得不太靠谱,数组类型需要提前声明大小,不能随意改变其容量大小,而我需要时刻知道最后一个索引位置的值,所以我最后选择了List来存放。不过现在回想起来,可能用stack会更好一点,直接不断的获取最上面的元素peak就好了,可能会更加方便一点。
  5. 还有一个容易踩坑的地方,就是对lastIndex的初始值选取。我最开始对lastIndex的初始值赋值为0,但是有个问题,在StringBuilder中,起始索引值为0,如果我们将lastINdex赋值为0的话,就代表了sb中一开始就已经有了1个元素,这样的话,在后面取出StringBuilder的元素时,会报空指针异常。这个问题也是折腾了好久才发现这个问题。最后就将lastIndex的初始值赋值为-1比较好。

实现的解法二:

后来看看评论区,又是一个新解法(代码中附有链接),顺便粘出来也分享一下吧。

这个解法使用的是纯数组。看完这个解法,顿时觉得自己的思想太狭隘。在实现的时候,我只想着当前容器最好可以随着字符串的长度变化而变化,也就是不要浪费内存,所以我拒绝了使用数组。

但是,当我们使用数组的时候,内部占用的内存却要比stack和list都要小得多的多。即使浪费一点,最后开辟的空间依旧比stack和list占用的小得多。所以下面这个解法在时间和内存方面,完全碾压我的代码。此时也就提醒自己,8个基本类型所占用的内存会小的多,有时候我们可以为了整体最优,浪费一点小内存,是完全有必要的。最后的效果也会非常好!

//纯数组实现   消耗:6 ms   37.3 MB
    public static String removeDuplicates(String s, int k) {
        char[] ss = s.toCharArray();
        int index = 0;//模拟栈大小
        char[] chStack = new char[ss.length];//字符栈
        int[] numStack = new int[ss.length];//计数栈
        for (char ch : ss) {
            // 栈为空或者ch和栈顶元素不相同,入栈,并初始化连续出现数量为1
            if (index == 0 || chStack[index - 1] != ch) {
                chStack[index] = ch;
                numStack[index++] = 1;
            } else if (chStack[index - 1] == ch) {
                // 字符栈顶元素已连续出现k-1次,且加上当前字符后满足连续k个,2个栈顶都出栈
                if (numStack[index - 1] + 1 == k) {
                    index--;
                } else {
                    // 与字符栈顶元素相同但未满足k,计数栈栈顶加1
                    numStack[index - 1]++;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < index; i++) {
            for (int j = 0; j < numStack[i]; j++) {
                sb.append(chStack[i]);
            }
        }
        return sb.toString();
    }

作者:hteason
链接:https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string-ii/solution/javachun-shu-zu-mo-ni-zhan-by-hteason/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

以上就是本周分享的一道题了吧!受益比较大的可能就是这个数组解法吧,自己的眼界还是太小了!以后要多看看相关的题目!fighting!

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 第29次文章:事务机制

    -连接到数据库上,并执行一条DML语句(insert、update或delete)。

    鹏-程-万-里
  • 第19次文章:类加载器的加密解密+内部类

    在上一期的文章中,我们介绍了自定义类加载器做法的整个流程,还没有理解同学可以点击回看哈!《第18次文章:JVM中的类加载机制》。在日常生活中,我们有时候需要将一...

    鹏-程-万-里
  • 第18次文章:JVM中的类加载机制

    -主要用来加载java的核心库,是用原生代码C语言来实现的,并不继承自java.lang.ClassLoader。

    鹏-程-万-里
  • 使用ASP.NET Core开发GraphQL服务器 -- 预备知识(上)

    为了介绍使用ASP.NET Core构建GraphQL服务器,本文需要介绍一下GraphQL,其实看官网的文档就行。

    solenovex
  • 5G位移下的封装产业“地壳运动”

    在5G手机的新品发布会上,SoC芯片绝对是最值得被率先拿出来大书特书的“核心竞争力”。

    脑极体
  • 你确定 SQL 查询都是以 SELECT 开始的?

    不过,最近我跟别人解释什么是窗口函数,我在网上搜索”是否可以对窗口函数返回的结果进行过滤“这个问题,得出的结论是”窗口函数必须在 WHERE 和 GROUP B...

    Java技术栈
  • Sprint为5G网络斥资10亿美元用于Massive MIMO

    在T-Mobile收购之前,Sprint正在为网络投入大量资金。在上周的Wells Fargo 5G论坛上,Sprint首席技术官John Saw表示,在过去几...

    SDNLAB
  • 学界 | 我们还缺多少基础理论,才能在高中开设深度学习课程?

    AI 科技评论按:这篇文章来自资深机器学习专家、NIPS 2017 「时间检验奖」( Test of Time Award ) 获得者 Ali Rahimi。上...

    AI科技评论
  • 从0系统学Android-2.4隐式Intent

    相对于显示 Intent ,隐式 Intent 比较含蓄。这种方式不明确指出我们想要启动哪一个 Activity。而是定义了一系列更为抽象的 action 和 ...

    开发者
  • C++核心准则C.120:类层次体系只用于表现固有的阶层结构‍

    C.120: Use class hierarchies to represent concepts with inherent hierarchical st...

    面向对象思考

扫码关注云+社区

领取腾讯云代金券