443. 压缩字符串 Medium
给你一个字符数组 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” 替代。
解题思路
输入： 字符数组 chars
输出： 压缩后的数组长度（原地修改 chars）
本题属于字符串问题。
核心思想
使用 双指针：
read指针扫描字符数组，逐段统计相同字符的出现次数write指针负责把压缩结果写回到数组前端
步骤
- 初始化
read和write为 0。 - 当
read < n时：- 定义临时指针
i = read，向右移动直到遇到不同字符，得到本段长度cnt = i - read。 - 将
chars[read]写入到chars[write]，并移动write。 - 如果
cnt > 1，将cnt转为字符串逐位写入（保证每一位都是单个字符），同时移动write。 - 更新
read = i，继续处理下一段。
- 定义临时指针
- 遍历完成后，返回
write作为压缩后数组的长度。
注意点
- 只有当
cnt > 1时才写入次数。 - 多位数需要逐字符写入，例如
12 → '1','2'。 - 函数返回的是新长度，不是数组本身。
代码实现
python
class Solution:
def compress(self, chars: List[str]) -> int:
i = 0 # 指针用于标记压缩后的字符位置
j = 0 # 指针用于遍历原数组
while j < len(chars): # 遍历整个字符数组
count = 0 # 记录当前字符出现的次数
curr = chars[j] # 当前处理的字符
# 内层循环统计当前字符的连续出现次数
while j < len(chars) and chars[j] == curr:
j += 1 # 移动到下一个字符
count += 1 # 当前字符出现次数 +1
chars[i] = curr # 将当前字符存储到压缩后的位置
i += 1 # 更新压缩后的字符位置
# 如果当前字符的出现次数大于1，则将次数存储到数组中
if count > 1:
for digit in str(count): # 将次数转换为字符串并逐个字符存入
chars[i] = digit
i += 1 # 更新压缩后的字符位置
return i # 返回压缩后的字符数组的长度javascript
/**
* @param {character[]} chars
* @return {number}
*/
var compress = function(chars) {
// 如果只有一个字符，不需要压缩，直接返回 1
if (chars.length === 1) return 1;
const n = chars.length;
let write = 0; // 写指针：负责把压缩结果写回 chars 前段
let read = 0; // 读指针：当前要处理的字符段的起点
// 遍历整个字符数组
while (read < n) {
let i = read;
// 找到从 read 开始这段相同字符的右边界（开区间）
// 即 chars[read...i-1] 都是相同字符
while (i < n && chars[read] === chars[i]) i++;
const cnt = i - read; // 这一段相同字符的长度
// 1. 写入该段的字符本身
chars[write] = chars[read];
write++;
// 2. 如果数量大于 1，则把数字逐位写入
if (cnt > 1) {
for (let ch of String(cnt)) {
chars[write] = ch; // 注意这里写的是字符（'1','2'...）
write++;
}
}
// 3. 读指针跳到下一段
read = i;
}
// 返回压缩后数组的有效长度
return write;
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)