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

2020 年 2 月 25 日
筆記

题目描述

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();  }

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

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