英文原文
Given an array of characters chars, compress it using the following algorithm:
Begin with an empty string s. For each group of consecutive repeating characters in chars:
- If the group's length is
1, append the character tos. - Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.
After you are done modifying the input array, return the new length of the array.
You must write an algorithm that uses only constant extra space.
Example 1:
Input: chars = ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
Example 2:
Input: chars = ["a"] Output: Return 1, and the first character of the input array should be: ["a"] Explanation: The only group is "a", which remains uncompressed since it's a single character.
Example 3:
Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"]. Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".
Example 4:
Input: chars = ["a","a","a","b","b","a","a"] Output: Return 6, and the first 6 characters of the input array should be: ["a","3","b","2","a","2"]. Explanation: The groups are "aaa", "bb", and "aa". This compresses to "a3b2a2". Note that each group is independent even if two groups have the same character.
Constraints:
1 <= chars.length <= 2000chars[i]is a lowercase English letter, uppercase English letter, digit, or symbol.
中文题目
给你一个字符数组 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"] 解释： 没有任何字符串被替代。
示例 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]可以是小写英文字母、大写英文字母、数字或符号
通过代码
高赞题解
双指针
令输入数组 cs 长度为 $n$。
使用两个指针 i 和 j 分别指向「当前处理到的位置」和「答案待插入的位置」：
i指针一直往后处理，每次找到字符相同的连续一段 $[i, idx)$，令长度为 $cnt$；- 将当前字符插入到答案，并让
j指针后移：cs[j++] = cs[i]； - 检查长度 $cnt$ 是否大于 $1$，如果大于 $1$，需要将数字拆分存储。由于简单的实现中，我们只能从个位开始处理 $cnt$，因此需要使用
start和end记录下存储数字的部分，再处理完 $cnt$ 后，将 $[start, end)$ 部分进行翻转，并更新j指针； - 更新
i为idx，代表循环处理下一字符。
代码：
[]class Solution { public int compress(char[] cs) { int n = cs.length; 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; while (cnt != 0) { cs[end++] = (char)((cnt % 10) + '0'); cnt /= 10; } reverse(cs, start, end - 1); j = end; } i = idx; } return j; } void reverse(char[] cs, int start, int end) { while (start < end) { char t = cs[start]; cs[start] = cs[end]; cs[end] = t; start++; end--; } } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 58391 | 122330 | 47.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 外观数列 | 中等 |
| 字符串的编码与解码 | 中等 |
| 迭代压缩字符串 | 简单 |
