知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 103 - 字符串压缩(行程长度编码) ## 题目 对字符串进行**行程长度编码(Run-Length Encoding)**:连续相同字符合并为 `字符+次数`。 ### 变体一:基础编码 ``` 输入:"aabbbcccc" 输出:"a2b3c4" ``` ### 变体二:LeetCode 443 - 原地压缩 ``` 输入:['a','a','b','b','c','c','c'] 输出:返回长度 6,数组变为 ['a','2','b','2','c','3'] 规则:单个字符不加数字,count ≥ 10 要拆成多个字符位 ``` ### 变体三:自定义格式(面试高频变种) ``` 输入:"abcabcde" 编码:3#abc2#de ← 长度#原文 └3#abc 表示后面3个字符是abc └2#de 表示后面2个字符是de ``` --- ## 变体一:基础编码 ### 核心思路 ``` 双指针滑动:快指针 i 一直往前走,遇到不同字符就结算上一段 a a b b b c c c c ↑ i=0, 统计 a 的个数 → 2 → 追加 "a2" i=2, 统计 b 的个数 → 3 → 追加 "b3" i=5, 统计 c 的个数 → 4 → 追加 "c4" ``` ```java public String compress(String s) { if (s == null || s.isEmpty()) return ""; StringBuilder sb = new StringBuilder(); int i = 0; while (i < s.length()) { char c = s.charAt(i); int count = 0; while (i < s.length() && s.charAt(i) == c) { count++; i++; } sb.append(c).append(count); } return sb.toString(); } ``` ``` 时间复杂度 O(n),空间 O(n) ``` --- ## 变体二:LeetCode 443 - 原地压缩 ### 区别 ``` 基础编码: aabbbcccc → "a2b3c4" 单字符也加数字,返回新字符串 LeetCode 443: → 原地修改 char[],返回压缩后的长度 → 单字符不写数字("a" 就是 "a",不是 "a1") → count ≥ 10 要拆成 '1','2' 等多个字符 ``` ### 核心:读写双指针 ``` [ a a b b b c c c c ] ↑写 ↑读 写指针 write:下一个字符写入位置 读指针 read: 当前正在扫描的位置 流程: read 统计连续字符个数 → 把字符写入 arr[write] → 如果 count > 1,把数字逐位写入 → 更新写指针位置 ``` ```java class Solution { public int compress(char[] chars) { int write = 0; // 写指针 int read = 0; // 读指针 while (read < chars.length) { char cur = chars[read]; int count = 0; // 统计当前字符连续出现次数 while (read < chars.length && chars[read] == cur) { read++; count++; } // 写入字符 chars[write++] = cur; // 如果次数 > 1,写入数字(逐位) if (count > 1) { for (char c : String.valueOf(count).toCharArray()) { chars[write++] = c; } } } return write; // 返回压缩后的长度 } } ``` ### 执行模拟 ``` 输入:['a','a','b','b','b','c','c','c','c'] read=0, write=0 第一组 a:read 走到 2, count=2 write=0 放 'a', write=1 放 '2' → arr = ['a','2', ...], write=2 第二组 b:read 走到 5, count=3 write=2 放 'b', write=3 放 '3' → arr = ['a','2','b','3', ...], write=4 第三组 c:read 走到 9, count=4 write=4 放 'c', write=5 放 '4' → arr = ['a','2','b','3','c','4', ...], write=6 返回 6 ``` ### 无额外 String 版本(纯数字逐位写) ```java public int compress(char[] chars) { int write = 0, read = 0; while (read < chars.length) { char cur = chars[read]; int count = 0; while (read < chars.length && chars[read] == cur) { read++; count++; } chars[write++] = cur; if (count > 1) { int start = write; while (count > 0) { chars[write++] = (char) (count % 10 + '0'); count /= 10; } // 反转数字位(因为上面是从低位到高位写入的) reverse(chars, start, write - 1); } } return write; } private void reverse(char[] arr, int l, int r) { while (l < r) { char tmp = arr[l]; arr[l++] = arr[r]; arr[r--] = tmp; } } ``` --- ## 变体三:自定义格式 `长度#原文`(面试高频) ### 场景 ``` 把任意字符串编码为:长度#原文 的格式 可以处理包含任意字符的字符串,无需转义 "abcabcde" → "3#abc2#de" 拆解: 3#abc = 接下来 3 个字符是 "abc" 2#de = 接下来 2 个字符是 "de" ``` ### 为什么有用 ``` 对比:如果字符串里本身有数字怎么办? "a2b" → 基础编码 "a12b1" → 解码时怎么知道 12 是次数还是原字符? 自定义格式:长度#原文 "a2b" → "3#a2b" ← 明确告诉你有 3 个字符,内容就是 a2b 解码时读到 3#,直接取后面 3 个字符,完美! ``` ### 编码 ```java public String encode(String s) { if (s == null || s.isEmpty()) return ""; return s.length() + "#" + s; } // 批量编码 public String encodeList(List<String> list) { StringBuilder sb = new StringBuilder(); for (String word : list) { sb.append(word.length()).append('#').append(word); } return sb.toString(); } ``` ### 解码 ```java public List<String> decode(String s) { List<String> result = new ArrayList<>(); int i = 0; while (i < s.length()) { // 1. 先读到 '#',获取长度数字 int j = i; while (s.charAt(j) != '#') j++; int len = Integer.parseInt(s.substring(i, j)); // 2. '#' 后 len 个字符就是原文 String word = s.substring(j + 1, j + 1 + len); result.add(word); // 3. 跳过这段,继续 i = j + 1 + len; } return result; } ``` ### ASCII 图解 ``` 输入:["abc", "de", "fghi"] 编码过程: "abc" → "3#abc" "de" → "2#de" "fghi" → "4#fghi" 最终:"3#abc2#de4#fghi" 解码过程: 3#abc2#de4#fghi ↑ ↑ i=0 i=5 i=0: 读到 '#' (j=1) → len=3 → word="abc" → i=1+1+3=5 i=5: 读到 '#' (j=6) → len=2 → word="de" → i=6+1+2=9 i=9: 读到 '#' (j=10)→ len=4 → word="fghi"→ i=10+1+4=15 结束 ``` --- ## 复杂度 | 变体 | 时间 | 空间 | |------|:---:|:---:| | 基础编码 | O(n) | O(n) | | 原地压缩(LC 443) | O(n) | O(1) | | 长度#原文编码 | O(n) | O(n) | --- ## 边界与细节 ``` LC 443 注意点: count ≥ 10:需要拆成 '1','0' → 如 count=12 → 写 '1','2' count = 1:不写入数字 返回值:压缩后长度,不是数组 自定义格式注意点: 长度数字可能不止一位:如 123#... → j 要一直找到 '#' 原文中可能含 '#' 字符:不影响,编码时把整个原文字符串放在 # 后 ``` --- ## 与 LC 394 字符串解码的区别 | | 压缩(本题) | 解码(LC 394 Hot 100) | |------|:---:|:---:| | 方向 | 原文 → 压缩 | 压缩 → 原文 | | 输入 | `aabbbcccc` | `3[a]2[bc]` | | 输出 | `a2b3c4` | `aaabcbc` | | 特点 | 单层、线性 | 嵌套括号、递归 | --- ## 同类题目 | 题目 | 描述 | |------|------| | LeetCode 443 | 原地压缩字符串(读/写双指针) | | LeetCode 271 | 字符串编码解码(长度#原文,变体三) | | LeetCode 394 | 字符串解码(Hot 100,方向相反) | --- 上一篇:[102 - 单词接龙](file:///f:/KiroPro/Text/java/102-word-ladder.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入