题目重点:按题目从左到右分组连续字符,处理空串、多位数次数、非连续重复和编码歧义。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 按 Python 字符逐个处理的训练版;若题目规定字节、Unicode grapheme cluster 或大小写归一化,需重新确认。
- 题目只要求压缩,未要求结果一定比原串短,也未要求可无歧义解码;数字字符会让无分隔符格式有解码歧义。
解题路线
- 维护当前 run 起点,向右扫描直到字符变化或字符串结束;run 长度为 end−start。
- 长度 1 追加原字符,长度大于 1 追加字符与十进制长度;然后从新字符开始下一 run。
- 循环不变量是 start 之前的字符已被完整编码,start 到 end−1 都等于当前字符;每个字符只作为 run 成员扫描一次。
手动走一遍
aaaaabbbccca 的 runs 为 a×5、b×3、c×3、a×1,输出 a5b3c3a。末尾 a 与开头 a 不相邻,不能合并。
Python 参考实现
下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。
代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。
"""Compress consecutive character runs; a run of one stays unchanged."""
def compress_runs(value: str) -> str:
if not value:
return ""
parts = []
start = 0
for end in range(1, len(value) + 1):
if end == len(value) or value[end] != value[start]:
count = end - start
parts.append(value[start] if count == 1 else value[start] + str(count))
start = end
return "".join(parts)
复杂度
N 个字符 O(N) 扫描,输出构造占 O(M) 空间,M 为编码结果长度;用片段列表最后 join 避免重复字符串拼接可能造成平方时间。
易错点与追问
容易失分的边界
- 把全局字符频次当连续 run 计数。
- 忘记处理最后一段或空串。
- 声称这种编码一定可逆:若原文含数字,无分隔符和转义规则可能产生歧义。
继续深挖
- 如果要保证可解码,如何加转义、长度前缀或限制原始字符集?
- 若要求只有压缩后更短才返回压缩串,如何避免重复遍历?
