0443. String Compression
========================
题目信息
--------
:题号: 0443
:难度: Medium
:主题: 字符数组、连续分组、原地写回、有效长度
:原题: `LeetCode 0443 `_
:重点: 只压缩连续相同字符、单次字符不写数字、计数按十进制逐位写入、返回修改后的有效前缀长度
题目重述
--------
给定字符数组 ``chars``,把每一段连续相同字符原地压缩。每组先写入该字符;若该组长度大于 1,再把长度的十进制各位字符依次写在后面。组长度为 1 时不能附加数字 ``1``。
返回压缩结果占用的字符数量。函数必须把结果写入 ``chars`` 的前缀,返回长度之后的原数组内容不作要求。``chars.length`` 位于 ``[1, 2000]``,元素可以是英文字母、数字或符号。只能使用常数额外空间。
自建示例
--------
多个连续分组:
.. code-block:: text
输入:chars = ["a","a","a","b","b","c"]
返回:5
修改后的有效前缀:["a","3","b","2","c"]
解释:三个 a 写成 a3,两个 b 写成 b2,单个 c 只写字符本身。
计数包含多位数字:
.. code-block:: text
输入:chars = 十二个连续的 "x"
返回:3
修改后的有效前缀:["x","1","2"]
解释:组长度 12 必须拆成字符 1 和 2 写入,而不是作为一个整数槽位。
读指针扫描分组,写指针覆盖前缀
------------------------------
读指针 ``read`` 每次定位一段连续相同字符,先向右扫描得到该组的结束位置和长度,再由写指针 ``write`` 把字符写回结果前缀。长度为 1 时只写字符;长度大于 1 时把十进制字符串的每一位依次写入,因而自然支持两位及更多位的计数。
压缩结果不会比已经读过的内容更长,所以写指针不会越过读指针破坏尚未统计的分组。扫描结束后,``write`` 就是有效前缀长度。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int compress(std::vector& chars) {
int read = 0;
int write = 0;
while (read < static_cast(chars.size())) {
char current = chars[read];
int begin = read;
while (read < static_cast(chars.size()) &&
chars[read] == current) {
++read;
}
chars[write++] = current;
int count = read - begin;
if (count > 1) {
std::string digits = std::to_string(count);
for (char digit : digits) {
chars[write++] = digit;
}
}
}
return write;
}
};
代码分析
--------
读指针只负责确认完整分组,写指针只写压缩后的有效结果;即使写入覆盖了数组前缀,也不会影响当前分组之后尚未读取的字符。每个字符最多被读写常数次,时间复杂度为 ``O(n)``;``to_string`` 产生的数字长度最多为 ``O(log n)``,除结果数组外的辅助空间为 ``O(log n)``。