题目描述
思路解析动画文字版
记住「读指针扫组数长、写指针写结果;每组输出不超原长 → 写指针不越过已读边界 j 所以能原地」,下面每帧都在套它。
开局:读指针 i 和写指针 write 都在第 0 位。i 去前面数每一组连续相同字符,write 把压缩结果写回数组头。
读指针 i 来到下标 0,一个新组开始,组内字符是 a。下一步往右数它连续出现几次。
往右数:这一组连续的 a 一直到下标 1,共 2 个。数清楚了,交给写指针落笔。
写指针先落字符本身:把 a 写到第 0 位(原地覆盖已读过的位置),write 前进到 1。
组长 2 大于 1,把个数 2 写到第 1 位,write 到 2。
这一组收工,读指针 i 直接跳到下一组的起点 2。注意写指针 2 始终没超过这条已扫描完的边界 2(下一组起点),所以一路覆盖的都是读过的位置,原地安全。
读指针 i 来到下标 2,一个新组开始,组内字符是 b。下一步往右数它连续出现几次。
往右数:这一组连续的 b 一直到下标 4,共 3 个。数清楚了,交给写指针落笔。
写指针先落字符本身:把 b 写到第 2 位(原地覆盖已读过的位置),write 前进到 3。
组长 3 大于 1,把个数 3 写到第 3 位,write 到 4。
这一组收工,读指针 i 直接跳到下一组的起点 5。注意写指针 4 始终没超过这条已扫描完的边界 5(下一组起点),所以一路覆盖的都是读过的位置,原地安全。
读指针 i 来到下标 5,一个新组开始,组内字符是 c。下一步往右数它连续出现几次。
往右数:这一组连续的 c 一直到下标 5,共 1 个。数清楚了,交给写指针落笔。
写指针先落字符本身:把 c 写到第 4 位(原地覆盖已读过的位置),write 前进到 5。
这一组只有 1 个 c,按规则组长为 1 不写数字,只留字符本身。这是最容易写错的地方。
这一组收工,读指针 i 直接跳到下一组的起点 6。注意写指针 5 始终没超过这条已扫描完的边界 6(下一组起点),所以一路覆盖的都是读过的位置,原地安全。
读指针 i 来到下标 6,一个新组开始,组内字符是 d。下一步往右数它连续出现几次。
往右数:这一组连续的 d 一直到下标 9,共 4 个。数清楚了,交给写指针落笔。
写指针先落字符本身:把 d 写到第 5 位(原地覆盖已读过的位置),write 前进到 6。
组长 4 大于 1,把个数 4 写到第 6 位,write 到 7。
读指针走到了数组末尾,所有组都压缩完了。
全部压缩完:数组前 7 位被原地改写成 "a2b3cd4",返回长度 7。7 位之后(灰色)是没用的残留,调用方只看前 7 位。全程没开新数组,空间 O(1)。
边界重点:单字符不写数字、组长上两位要逐位写。
两个高频追问,核心还是「每组输出不超原长 → 写指针不超已读边界 j → 原地安全」。
参考代码
from typing import Listclass 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 write复杂度
- 时间：O(n)，读指针 i 与写指针 write 各自单向走一遍,每个字符只被读一次、写一次
- 空间：O(1)，只用 i、write、组长几个变量,就地改写不开新数组
易错点
面试追问把动画讲成自己的话
追问为什么这道题能保证原地、不会覆盖掉还没读的字符?
追问如果改成不要求原地、可以用额外空间,会更简单吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组中的 k-diff 数对
LeetCode 532 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题