压缩字符串 图解题解
这道题到底在问什么
- 输入
- chars=["a","a","b","b","c","c","c"]
- 输出
- 6,前缀 "a2b2c3"
- 输入
- chars=["a"]
- 输出
- 1,前缀 "a"
最优解：一步一步想明白
- 3记住「读指针扫组数长、写指针写结果;每组输出不超原长 → 写指针不越过已读边界 j 所以能原地」,下面每帧都在套它。
- 4开局:读指针 i 和写指针 write 都在第 0 位。i 去前面数每一组连续相同字符,write 把压缩结果写回数组头。
- 5读指针 i 来到下标 0,一个新组开始,组内字符是 a。下一步往右数它连续出现几次。
- 6往右数:这一组连续的 a 一直到下标 1,共 2 个。数清楚了,交给写指针落笔。
- 7写指针先落字符本身:把 a 写到第 0 位(原地覆盖已读过的位置),write 前进到 1。
- 8组长 2 大于 1,把个数 2 写到第 1 位,write 到 2。
- 9这一组收工,读指针 i 直接跳到下一组的起点 2。注意写指针 2 始终没超过这条已扫描完的边界 2(下一组起点),所以一路覆盖的都是读过的位置,原地安全。
- 10读指针 i 来到下标 2,一个新组开始,组内字符是 b。下一步往右数它连续出现几次。
- 11往右数:这一组连续的 b 一直到下标 4,共 3 个。数清楚了,交给写指针落笔。
- 12写指针先落字符本身:把 b 写到第 2 位(原地覆盖已读过的位置),write 前进到 3。
- 13组长 3 大于 1,把个数 3 写到第 3 位,write 到 4。
- 14这一组收工,读指针 i 直接跳到下一组的起点 5。注意写指针 4 始终没超过这条已扫描完的边界 5(下一组起点),所以一路覆盖的都是读过的位置,原地安全。
- 15读指针 i 来到下标 5,一个新组开始,组内字符是 c。下一步往右数它连续出现几次。
- 16往右数:这一组连续的 c 一直到下标 5,共 1 个。数清楚了,交给写指针落笔。
- 17写指针先落字符本身:把 c 写到第 4 位(原地覆盖已读过的位置),write 前进到 5。
- 18这一组只有 1 个 c,按规则组长为 1 不写数字,只留字符本身。这是最容易写错的地方。
- 19这一组收工,读指针 i 直接跳到下一组的起点 6。注意写指针 5 始终没超过这条已扫描完的边界 6(下一组起点),所以一路覆盖的都是读过的位置,原地安全。
- 20读指针 i 来到下标 6,一个新组开始,组内字符是 d。下一步往右数它连续出现几次。
- 21往右数:这一组连续的 d 一直到下标 9,共 4 个。数清楚了,交给写指针落笔。
- 22写指针先落字符本身:把 d 写到第 5 位(原地覆盖已读过的位置),write 前进到 6。
- 23组长 4 大于 1,把个数 4 写到第 6 位,write 到 7。
- 24读指针走到了数组末尾,所有组都压缩完了。
- 25全部压缩完:数组前 7 位被原地改写成 "a2b3cd4",返回长度 7。7 位之后(灰色)是没用的残留,调用方只看前 7 位。全程没开新数组,空间 O(1)。
⚠️ 容易写错的地方
✗ 错：组长为 1 也写上数字 1
✓ 对：组长为 1 只写字符、不写数字
题目规定单个字符不带计数,写了 1 就错(a 不能压成 a1)
✗ 错：组长 ≥ 10 直接写一个字符
✓ 对：把多位数逐位拆开依次写
组长可能两位甚至三位(如 12),要写 "1""2" 两个字符位
✗ 错：返回压缩后的字符串
✓ 对：返回长度 write(就地覆盖、不开新数组)
题目要新长度;write 不超读指针,原地写安全,超出长度的残留不算数
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def compress(self, chars: List[str]) -> int:
write = 0
i = 0
while i < len(chars):
ch = chars[i]
j = i
while j < len(chars) and chars[j] == ch:
j += 1
chars[write] = ch
write += 1
if j - i > 1:
for d in str(j - i):
chars[write] = d
write += 1
i = j
return writeC++
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int compress(vector<char>& chars) {
int write = 0, i = 0;
while (i < (int)chars.size()) {
char ch = chars[i];
int j = i;
while (j < (int)chars.size() && chars[j] == ch) j++;
chars[write++] = ch;
if (j - i > 1) for (char d : to_string(j - i)) chars[write++] = d;
i = j;
}
return write;
}
};Java
import java.util.*;
class Solution {
public int compress(char[] chars) {
int write = 0, i = 0;
while (i < chars.length) {
char ch = chars[i];
int j = i;
while (j < chars.length && chars[j] == ch) j++;
chars[write++] = ch;
if (j - i > 1) for (char d : String.valueOf(j - i).toCharArray()) chars[write++] = d;
i = j;
}
return write;
}
}复杂度
时间
O(n)
读指针 i 与写指针 write 各自单向走一遍,每个字符只被读一次、写一次
空间
O(1)
只用 i、write、组长几个变量,就地改写不开新数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 压缩字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么这道题能保证原地、不会覆盖掉还没读的字符?+
因为每一组压缩后的输出长度绝不会超过这组的原长度,分两种情形:组长为 1 时只写 1 个字符、不写数字,输出长度就是 1,正好等于组长;组长大于 1 时输出是 1 个字符加上组长的位数,而「1 + 位数」始终不超过组长本身(比如组长 99 是 2 位,1 + 2 = 3 远小于 99)。内层会先把 j 扫到组尾再写,逐组累加下来写指针 write 始终不超过已经扫描完的边界 j(下一组起点),覆盖的都是已读区域,绝不会动到 j 之后还没读的字符。
如果改成不要求原地、可以用额外空间,会更简单吗?+
会,直接用一个结果列表 append 字符和数字、最后拼接即可,逻辑一样但不用纠结写指针。本题强调原地是为了考 O(1) 空间下的指针控制,面试常以此区分熟练度。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 压缩字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。