:-: 6.4 压缩字符串 ***** **题干：** 给定一组字符，使用原地算法将其压缩。压缩后的长度必须始终小于或等于原数组长度。数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。在完成原地修改输入数组后，返回数组的新长度。 进阶： ``` 你能否仅使用O(1) 空间解决问题？ ``` 示例 1： ``` 输入： ["a","a","b","b","c","c","c"] 输出： 返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"] 说明： "aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。 ``` 示例 2： ``` 输入： ["a"] 输出： 返回1，输入数组的前1个字符应该是：["a"] 说明： 没有任何字符串被替代。 ``` 示例 3： ``` 输入： ["a","b","b","b","b","b","b","b","b","b","b","b","b"] 输出： 返回4，输入数组的前4个字符应该是：["a","b","1","2"]。 说明： 由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。注意每个数字在数组中都有它自己的位置。 ``` 注意： ``` 所有字符都有一个ASCII值在[35, 126]区间内。 1 <= len(chars) <= 1000。 ``` **题目分析：** 根据题目意思每遇到重复字符，就应该记下来他们的个数（假设为sum），直至遇到不同的字符，然后用此个数替换原来字符重复序列中后sum - 1个字符，当然第一个重复序列替换后，后一个重复序列也应该将空出的字符位补上，同时记录生成一个全新序列的大小。 **新手有可能遇到的解题思路陷阱：** 一般有这几种：忘记统计重复序列的开始字符；重复子序列与重复子序列之间的界限（也就是没有考虑下一次重复子序列的开端），原数组的最后重复的子序列没有结束处理； **解题思路分析以及代码实现：** 第一种思路：我们先不管进阶的要求，我们只要重新创建一个数组记录下我们的重复字符和重复的个数就可以了，接着返回这个新数组的大小。 为什么使用charAt()方法而不使用toCharArray()方法？经过我对两个方法的简单的时间效率比较，总的来说发现第一个方法更加快一些：因为第二个方法是把字符串转换为字符数组，它会产生创建和填充新char[]的成本，填充字符数组时会有一个for循环将byte类型的数组值转化为char类型数组值，会使用更多的内存；虽然第一种方法也有byte类型数组值转char类型值，并每次进行边界检查。（这是我看Java 8源码以及一些博客分析的，但也有一些博客说第二个方法更加快捷，难道是Java 8对第一个方法做了优化或者我的分析是错误的，望看到的大佬评论或者私信解惑）。可以参考一下这两个博客： [ 遍历String的最有效方法](http://www.coderlord.com/java/5/3/7/17017B13302537.html) [Java中toCharArray()方法](https://blog.csdn.net/liu16659/article/details/52127970) 第一种思路代码： ``` public int compress(char[] chars) { if (chars.length < 2) return chars.length; int length = 0; for (int i = 0; i < chars.length;) { int sum = 1; chars[length++] = chars[i++]; while (i < chars.length && chars[i - 1] == chars[i]) { sum++; i++; } if (sum > 1) { /*char[] nums = String.valueOf(sum).toCharArray(); for (char num : nums) chars[length++] = num;*/ String nums = String.valueOf(sum); for (int j = 0; j < nums.length(); j++) { chars[length++] = nums.charAt(j); } } } return length; } ``` **复杂度分析** 时间复杂度：O(n^2)。 空间复杂度：O(1)。 第二种思路：原数组进行替换，考虑进阶的要求：仅使用O(1) 空间解决问题；做题步骤同上，只不过在原数组上操作。 第二种思路代码： ``` public int compress(char[] chars) { if (chars.length <= 1) { return chars.length; } int i = 0, j = 0, length = 0; for (i = 0; i < chars.length; i++) { int num = 1; for (j = i + 1; j < chars.length; j++) { if (chars[i] == chars[j]) { num++; } else { i = --j; break; } if (j == chars.length - 1) { i = j; break; } } /*String nums = chars[i] + (num == 1 ? "" : String.valueOf(num)); for (int k = 0; k < nums.length(); k++) { chars[length] = nums.charAt(k); length++; }*/ if (num == 1) { chars[length++] = chars[i]; } else { String nums = chars[i] + String.valueOf(num); for (int k = 0; k < nums.length(); k++) { chars[length] = nums.charAt(k); length++; } } } return length; } ``` **复杂度分析** 时间复杂度：O(n^2)。 空间复杂度：O(1)。 第三种思路：此思路使得时间复杂度进一步降低，步骤与上两个思路并无太大区别，但却把重复子序列的长度转化为num - low（也就是用重复子序列的当前总长度 - 当前子序列的开始位置（两个子序列的转折位置））。 第三种思路代码： ``` public int compress(char[] chars) { if (chars.length == 1) return 1; int num = 1; int length = 0; for (int low = 0; low < chars.length;) { if (num < chars.length && chars[low] == chars[num]) { num++; } else { int len = num - low; chars[length] = chars[low]; if (len == 1) { length++; low++; num++; } else { String str = String.valueOf(len); for (int j = 0; j < str.length(); j++) { length++; chars[length] = str.charAt(j); } length++; low = num; num++; } } } return length; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 第四种思路（与第三种是异曲同工）：此次改变以前的重复子序列开头元素与后几个元素比较的方式，改为后几个元素与开头元素比较，这也造成了结尾如果是的单独序列：如aabbc，的无法统一处理，所以需要另外判断处理。 第四种思路代码： ``` public int compress(char[] chars) { if (chars.length <= 1) return chars.length; boolean endWithOnceLetter = chars[chars.length - 1] != chars[chars.length - 2]; int slow = 0; int fast = 1; int count = 1; int length = 0; for (fast = 1; fast < chars.length; fast++) { if (chars[fast] == chars[slow]) { count += 1; } if (chars[fast] != chars[slow] || fast == chars.length - 1) { if (count == 1) { chars[length++] = chars[slow]; } else { char[] valueString = String.valueOf(count).toCharArray(); chars[length++] = chars[slow]; for (int i = 0; i < valueString.length; i++) { chars[length++] = valueString[i]; } } slow = fast; count = 1; } } if (endWithOnceLetter) { chars[length++] = chars[chars.length - 1]; } return length; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**