其他系列文章导航
文章目录
前言
这是力扣的443题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。
一、题目描述
题目有点小坑，在下面提到了。
给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
- 如果这一组长度为
1，则将字符追加到s中。 - 否则，需要向
s追加字符，后跟这一组的长度。
压缩后得到的字符串 s不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。（说白了就是要在原字符数组上改）
示例 1：
输入：chars = ["a","a","b","b","c","c","c"]
输出：返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
解释："aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
示例 2：
输入：chars = ["a"]
输出：返回 1 ，输入数组的前 1 个字符应该是：["a"]
解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。
示例 3：
输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：返回 4 ，输入数组的前 4 个字符应该是：["a","b","1","2"]。
解释：由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
提示：
1 <= chars.length <= 2000chars[i]可以是小写英文字母、大写英文字母、数字或符号
注：这个题是要求修改原数组，即在原空间，然后，返回新的长度，在测试机中的是根据我们计算出来的新长度来输出而不是使用chars.length或者char ch:chars之类的控制输出。
二、题解
2.1 方法一：双指针
思路与算法：
首先我们要令输入数组 chars 长度为 n。
编辑
使用两个指针 i 和 j 分别指向「当前处理到的位置」和「答案待插入的位置」：
- 当字符一样的时候，i 指针一直往后处理，每次找到字符相同的连续一段 [i,idx)，令长度为 cnt；
- 将当前字符插入到答案，并让 j 指针后移：chars [j++] = chars [i]；
- 检查 cnt 的长度是否大于 1，如果大于 1，需要将数字拆分存储。由于简单的实现中，我们只能从个位开始处理 cnt，因此需要使用 start 和 end 记录下存储数字的部分，再处理完 cnt 后，将 [start,end) 部分进行翻转，并更新 j 指针；
编辑 - 最后我们更新 i 为 idx，代表循环处理下一字符。
三、代码
3.1 方法一：双指针
Java版本（带注释）：
class Solution { public int compress(char[] chars) { int len = chars.length; int i = 0; //当前处理下标 int j = 0; //当前被替换下标 while(i < len) { int idx = i; //找连续相同字符 while(idx < len && chars[idx] == chars[i]) idx++; int cnt = idx - i; //连续相同字符长度 chars[j++] = chars[i];//要替换的下标对准 连续字符串 的第一个下标 if(cnt > 1) { int start = j, end = start; //替换cnt while(cnt != 0) { chars[end++] = (char)(cnt % 10 + '0'); cnt /= 10; } //由于从个位开始替换, 需要将数字翻转 reverse(chars, start, end-1); //替换完成后, 更新j j = end; } i = idx;//处理完一串, 移动下标 } return j; } //翻转chars 下标start .. 下标end 之间的字符 void reverse(char[] chars, int start, int end) { while(start < end) { char tmp = chars[start]; chars[start] = chars[end]; chars[end] = tmp; start++; end--; } } }
C++版本：
#include <vector> #include <string> using namespace std; class Solution { public: int compress(vector<char>& cs) { int n = cs.size(); int i = 0, j = 0; while (i < n) { int idx = i; while (idx < n && cs[idx] == cs[i]) idx++; int cnt = idx - i; cs[j++] = cs[i]; if (cnt > 1) { int start = j, end = start; string cnt_str = to_string(cnt); for (char c : cnt_str) { cs[end++] = c; } reverse(cs, start, end - 1); j = end; } i = idx; } return j; } void reverse(vector<char>& cs, int start, int end) { while (start < end) { char t = cs[start]; cs[start] = cs[end]; cs[end] = t; start++; end--; } } };
C++简洁版：
class Solution { public: int compress(vector<char>& chars) { int i=0,j=0,n=chars.size(); while(i<n){ int idx=i; while(idx<n && chars[idx]==chars[i]) idx++; int cnt=idx-i; chars[j++]=chars[i]; if(cnt>1){ string s=to_string(cnt); for(auto c:s) chars[j++]=c; } i=idx; } return j; } };
Python版本：
def compress(cs): n = len(cs) i, j = 0, 0 while i < n: idx = i while idx < n and cs[idx] == cs[i]: idx += 1 cnt = idx - i cs[j] = cs[i] j += 1 if cnt > 1: start = j end = start cnt_str = str(cnt) for c in cnt_str: cs[end] = c end += 1 cs[start:end] = cs[start:end][::-1] j = end i = idx return j
四、复杂度分析
没有用到除常量以外额外的空间，满足题目的要求！
- 时间复杂度：O(n)
- 空间复杂度：O(1)
