LeetCode 补充题 169. 保留单次计数的游程编码
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 443. 压缩字符串
LeetCode 原题原地压缩字符数组，连续段长度为 1 时省略计数；本文按 Unicode 码点处理，始终保留计数 1，并返回新字符串。
:::
给定字符串
s，将每一段连续相同字符写为“字符 + 出现次数”。即使该段只出现一次，也要输出数字1。返回编码后的字符串，不要求原地修改。
示例 1：
输入：
s = "aabbccdaa"
输出："a2b2c2d1a2"
解释： 两个不相邻的a段分别编码，d只出现一次也要写成 d1。
示例 2：
输入：
s = "abc"
输出："a1b1c1"
解释： 所有单次出现的连续段都保留计数 1。
提示：
- 按 Unicode 码点判断字符是否相同。
- 空串返回空串。
- 本题仅定义编码结果，不要求实现解码。
题意分析
编码针对连续相同字符段，而不是整串中某字符的总频次。即使字符相同，只要中间被其他字符隔开，就应当产生独立的两段输出；长度为 1 的段也要显式写出计数。
解法：扫描连续相同字符段
核心思路
[!blue]
先按码点得到字符序列。
i是当前尚未处理段的起点，j从i+1向右移动，直到越界或遇到不同码点。此时[i,j)恰好是一个完整连续段，长度为j-i。向结果追加一次该码点，再追加段长的十进制表示，然后令
i = j进入下一段。每个输入位置只属于一个段，既不会重复计数，也不会跨段合并。使用字符串构造器累积，避免反复复制整个结果。空输入不进入循环而返回空串；该格式只要求编码，输入本身含数字时也不额外承诺可以无歧义解码。
解题步骤
- 将输入按码点遍历，从 i 向右找到连续相同段的结束位置 j。
- 输出该码点及 j-i，单次也输出 1。
- 令 i=j 继续下一段，直到遍历完毕。
代码实现
class Solution {
public String encodeRuns(String s) {
int[] chars = s.codePoints().toArray();
StringBuilder out = new StringBuilder();
for (int i = 0; i < chars.length; ) {
int j = i + 1;
while (j < chars.length && chars[j] == chars[i]) {
j++;
}
out.appendCodePoint(chars[i]).append(j - i);
i = j;
}
return out.toString();
}
}
import (
"strconv"
"strings"
)
func encodeRuns(s string) string {
chars := []rune(s)
var out strings.Builder
for i := 0; i < len(chars); {
j := i + 1
for j < len(chars) && chars[j] == chars[i] {
j++
}
out.WriteRune(chars[i])
out.WriteString(strconv.Itoa(j - i))
i = j
}
return out.String()
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：码点数组和结果空间 $O(n)$。
关键点总结
[!green]
连续段独立计数，同一字符被其他字符隔开后不能合并；aabcc 得到 a2b1c2。
易错点总结
[!yellow]
- 每段必须输出计数，不能省略
1。- 相同字符的非相邻段不能合并成全局频次。
- 返回完整编码字符串，不是原地压缩后的数组长度。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 443. 压缩字符串 | 中等 | 同样扫描连续重复段，本题按 Unicode 码点处理并且次数 1 也必须输出。 |
| 38. 外观数列 | 中等 | 每一轮都对前一轮做游程描述，本题只对给定文本执行一次。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！