企业官网建设流程全解析

如果面试官突然甩给你一道“压缩字符串”的算法题，你的第一反应是什么？是开心地觉得简单，还是心里打鼓？说实话，这道题在 LeetCode 上被标记为中等难度，却经常出现在一线大厂的算法面试里。它表面上是要求把连续重复的字符按“字符+次数”的格式压缩，比如aabbb变成a2b3，但实际考察点远不止编码，而是你对数组原地操作、双指针、边界条件这些基本功的掌握程度。这篇文章就围绕压缩字符串这道题，拆解两种常见版本，给出可直接运行的代码，并用踩坑经验帮你避开那些面试官最爱埋的雷。适合正在刷题准备算法面试的开发者，也适合想搞懂 RLE 编码原理再应用到业务场景的同学。

1. 算法题到底在考什么：先拆穿压缩字符串的“潜台词”

1.1 两个常见题目版本，别在第一眼就搞混

市面上流传的“压缩字符串”其实有两个主流版本，很多人上来就写，结果连题目要求都没看清，代码自然不可能过。

第一个版本是 LeetCode 443 题String Compression。输入是一个字符数组chars，要求原地压缩，也就是直接修改这个数组，把压缩后的结果写到数组前部，最终返回新的数组长度。它考察的核心是：你能不能在不申请额外数组的情况下，用 O(1) 空间完成操作。

第二个版本在很多面试书里出现，比如《程序员面试金典》里的字符串压缩题。输入是一个普通字符串s，你需要把连续相同的字符压缩成“字符+出现次数”的形式，如果压缩后的字符串更短，返回压缩串，否则返回原串。这个版本允许你创建一个新字符串，考察点是字符串拼接和逻辑判断。

两者最直观的区别在于：LeetCode 443 对出现次数为 1 的字符不写数字，比如["a","b"]压缩后就是["a","b"]，不会变成["a","1","b","1"]；而字符串版题目一般强制写 1，比如"aab"会变为"a2b1"。

我见过不少候选人，面到一半才发现自己把数组当字符串做，或者在原地版本里疯狂res.append。这种基础错误一旦出现，面试官对你的印象分就会直线下降。所以拿到题第一件事不是写代码，而是把所有约束条件读清楚，尤其是“原地”和“返回值”这两个词。

1.2 核心算法：行程长度编码（RLE）的原理

压缩字符串这道题背后的算法，是典型的“行程长度编码”（Run-Length Encoding，简称 RLE）。它的原理非常朴素：把输入序列分成若干个连续相同元素的“行程”，记录每个行程的元素和长度。举个例子，aaabbc包含三个行程：aaa、bb、c，按“元素+长度”编码就是a3b2c1。

用一个生活类比你就懂了。想象一个班级的点名簿，如果 50 个同学都叫“王磊”，老师逐人点名要念 50 次。然后聪明老师改成了“王磊×50”，一下子只念两个符号。这个“名字+数量”的结构，就是最原始的 RLE 思路。它牺牲了一点读取时的解码成本，但换来了存储空间和传输带宽上的大幅节省。

RLE 之所以适合当算法面试题，是因为它的编码规则三分钟就能讲完，但真正实现起来，数组下标、字符计数、数字位数这些问题一个接一个。面试官想看到的，不是你能背出答案，而是你能不能在一个看似普通的题里，把边界条件、原地修改、时间空间复杂度这些基本功理清楚。这也是为什么它明明不复杂，却常年出现在“必刷算法题”清单里的原因。

2. 解题思路与方案选型：从暴力解法到双指针

2.1 暴力解法：先统计再重建，为什么面试官不满意

多数人拿到这道题的第一版代码，是新建一个结果数组，把原数组扫描一遍，遇到连续相同字符就统计数量，然后往结果数组里塞字符和数字。这种思路在逻辑上完全正确，代码也非常好读。

def compress_naive(chars): res = [] i = 0 n = len(chars) while i < n: ch = chars[i] cnt = 0 while i < n and chars[i] == ch: i += 1 cnt += 1 res.append(ch) if cnt > 1: for c in str(cnt): res.append(c) return len(res)

这段代码能通过一些测试用例，但它直接违背了 LeetCode 443 的硬性要求：不使用额外空间。res是一个新数组，空间复杂度是 O(n)。面试官如果让你优化，你只能回答已经优化到头了，那这道题基本就凉了。

暴力法的价值在于帮我们理清思路：每一组连续相同字符由“一个字符 + 一个计数”组成，统计完就把这一组的结果写出去。这其实已经摸到了核心逻辑，只是存储方式不符合要求。接下来的双指针解法，就是把“写到一个新数组”改成“写到原数组的前部”，空间立刻降到 O(1)。

2.2 双指针原地压缩：标准解法是怎么一步步想到的

要原地压缩，就得在同一个数组里同时做两件事：一边往后读，一边往前写。于是自然引出双指针：read负责扫描原数组的每一组字符，write负责把压缩后的内容写到数组前部。

完整流程是：

1. 当read没有越界时，记录当前字符ch = chars[read]。
2. 用一个内层循环统计从read开始有多少个连续相同的字符，记为count，同时让read移动到下一组的开头。
3. 把chars[write]写成ch，write加 1。
4. 如果count > 1，把count转成字符串，逐位写入chars[write]，每写一位write加 1。
5. 循环结束后返回write，这个值就是压缩后数组的新长度。

拿["a","a","b","b","c","c","c"]手动推演一遍。初始read=0，write=0。第一组字符是a，统计出count=2，read停到下标 2。此时chars[0]='a'，write=1；再把'2'写到chars[1]，write=2。第二组是b，chars[2]='b'，write=3，chars[3]='2'，write=4。第三组是c，chars[4]='c'，write=5，chars[5]='3'，write=6。最后返回 6，数组前 6 位就是['a','2','b','2','c','3']。

很多初学者担心一个问题：write在向后写的时候，会不会把read还没来得及读的字符覆盖掉？这里的关键在于，write永远不可能越过read。原因很简单：read每次扫描一组要前进count步，而write每组最多写1 + log10(count)位。当count=1时只写 1 位，write和read拉平；当count=2时写 2 位，两者拉平；当count>2时写得比扫描的少，read更是跑在前面。既然write始终位于read的左侧或同一位置，就永远不会破坏尚未读到的数据。

2.3 数字写入的细节：为什么不能只写一位数

这是整个题里最容易被忽略、也最容易丢分的地方。数组里的每个元素都是一个字符，当连续字符出现次数超过 9 时，比如 10 个a，计数“10”是由字符'1'和'0'组成的，必须拆成两个字符写入。

如果代码里写chars[write] = str(count)，在 Python 或 C++ 中会直接报错，因为str(count)是一个字符串，不是一个字符。正确做法是遍历str(count)的每一个字符，逐位写入。举个例子，100 个连续a压缩后前四位应该是'a','1','0','0'，返回长度为 4。

面试时建议优先用语言自带的字符串转换函数，比如 Python 的str(count)或 C++ 的to_string(count)，简明清晰。如果面试官追问“不允许用库函数怎么办”，你可以说用除 10 取余从低位到高位得到每一位，逆序写入；也可以先把每位放进一个临时数组，再反向写回原数组。原理不难，但现场容易写乱，所以先把标准解写对，再考虑这个进阶版本。

3. 核心代码实现与关键细节拆解

3.1 Python 标准实现：可以直接跑通 LeetCode 443

下面给出完整的 Python 实现，注释标出了每一段的关键作用。

def compress(chars): write = 0 read = 0 n = len(chars) if n == 0: return 0 while read < n: ch = chars[read] count = 0 # 统计当前这一组有多少个连续相同字符 while read < n and chars[read] == ch: read += 1 count += 1 # 先写入字符本身 chars[write] = ch write += 1 # 只有数量大于 1 时才写数字 if count > 1: for digit in str(count): chars[write] = digit write += 1 return write

逐行拆开看，这段代码的核心逻辑就是“找到一组，写入一组”。ch保存的是当前组的字符；内层循环统计完count后，read正好指向下一组的第一个字符。外层的while继续用新位置开启下一轮，不需要额外维护i。

本地测试也是现成的：

chars = ["a", "a", "b", "b", "c", "c", "c"] n = compress(chars) print(n) # 6 print(chars[:n]) # ['a', '2', 'b', '2', 'c', '3']

这里有几个很值得注意的细节。第一，内层循环一定要从read当前的位置开始，不能用while count这种不知道指针在哪的方式。第二，count至少为 1，因为外层循环进入时read一定指向一个有效字符。第三，先写字符再写数字，顺序反了会导致输出变成2a3b之类的错误结果。

3.2 C++ 实现对比：原地修改的典型写法

如果你平时用 C++，实现思路完全一样，只是要操作vector<char>的引用。

#include <vector> #include <string> using namespace std; int compress(vector<char>& chars) { int write = 0; int read = 0; int n = chars.size(); if (n == 0) return 0; while (read < n) { char ch = chars[read]; int count = 0; while (read < n && chars[read] == ch) { ++read; ++count; } chars[write++] = ch; if (count > 1) { string num = to_string(count); for (char c : num) { chars[write++] = c; } } } return write; }

C++ 版本的注意点是函数参数必须写成vector<char>&，如果只写vector<char>，函数内部修改的是拷贝，不会影响外部数组。另外chars[write++] = ch这种写法代码简洁，但如果对write的边界不自信，也可以拆成两行，减少出错机会。

3.3 字符串版本：到底什么时候返回原串

字符串版本的核心思路同样是扫描连续相同字符，但需要额外判断压缩结果是否更短。下面是一段可以直接用的 Python 解法：

def compress_string(s): if not s: return s res = [] i = 0 n = len(s) while i < n: ch = s[i] count = 0 while i < n and s[i] == ch: i += 1 count += 1 res.append(ch) res.append(str(count)) compressed = ''.join(res) return compressed if len(compressed) < n else s

这个版本和 LeetCode 443 最大的不同是：即使某个字符只出现一次，也会写入数字 1。因此"aab"的压缩结果是"a2b1"，长度和原串一样，最终返回原串"aab"。而"aabcccccaaa"的压缩结果是"a2b1c5a3"，长度比原串短，返回压缩串。

很多人在面试时把两个版本搞混，题目明明要求返回原串或压缩串中较短的那个，却不管三七二十一直接返回压缩结果；或者反过来，LeetCode 443 要求原地，却新建了字符串。建议在解题前先把规则写在白板一角，时刻提醒自己。

4. 常见问题与排查技巧实录

4.1 边界条件与测试用例清单

这道题想一次通过，光靠题目自带的例子远远不够。至少要准备下面这些测试用例，尤其是 10 个连续字符的情况。

前三个用例很多人不会出错，但第四个非常容易丢。10 个a必须被压缩成['a','1','0']，这里需要用到多位数写入的逻辑，如果你只写了单个数字字符，或者用chars[write] = str(count)，都会出问题。第五个用例用来验证count=1不写数字的规则，第六个则混合了“单字符不写数字”和“多位数写入”两种情况。

4.2 面试现场最容易翻车的 5 个细节

我见过太多候选人死在这五个细节上，每一个都值得单独说。

第一，忘记原地修改。题目要求直接改原数组，却新建了一个result列表，空间复杂度不达标。正确的做法是始终让write在原数组上覆盖。

第二，统计完一组没有正确移动read。如果内层循环写成while count < n而不是以read越界为条件，read可能停在一个错误位置，外层循环死循环或漏字符。

第三，把数字写到字符前面。chars[write] = ch必须先执行，再写count。先写数字后写字符，结果完全错乱。

第四，count > 1的条件被忽略。有些版本要求 1 不写数字，如果你无条件写数字，["a","b"]会被写成["a","1","b","1"]，长度反而增加。

第五，read的取值边界没想清楚。内层循环条件必须是read < n and chars[read] == ch，两个条件的顺序不能反，否则chars[read]可能越界访问。

4.3 时间复杂度和空间复杂度怎么说

这道题的最优复杂度是时间 O(n)、额外空间 O(1)。每个字符都会被read扫描一次，也会被write写入一次，所以总操作次数是线性的。str(count)产生的临时字符串长度是log10(count)，在大多数测试数据下可以视为常数，面试时可以说“严格来说需要 O(log n) 级别的临时空间，但题目一般把它当作 O(1)”。如果面试官比较严格，你补充一句“可以用除 10 取余的方式手动把整数转成字符数组，做到严格 O(1)”就够了。

这类复杂度分析其实不是难点，难的是语气。不要背课文一样说“时间复杂度O(n)，空间复杂度O(1)”，而是结合你的代码解释每一步为什么是线性、为什么没有额外数组。这样面试官会认为你真正理解了实现而不是背了模板。

5. 从算法题延伸到真实场景：压缩字符串的工程实践

5.1 RLE 的真实应用场景在哪里

RLE 并不是只存在于面试题里，它在很多工程场景都有实际应用。最经典的是位图和图片格式，比如 BMP 和 TIFF 支持 RLE 压缩；传真协议也使用一维 RLE 对黑白像素编码。PNG 虽然用的是 Deflate 压缩，但在压缩前会有滤波步骤，本质上也在制造更容易被压缩的重复模式。游戏里常见的 Tilemap 地图数据，如果同一行有大量相同的地图块 ID，用 RLE 也能明显缩减体积。

RLE 的最大优势是算法简单、压缩和解压速度极快。它只需要顺序扫描一次，不需要像 Huffman 那样统计全量频率，也不像 LZ 系列需要维护字典。但它的弱点同样明显：如果数据本身没有连续重复，比如一段完全随机的字符，压缩后大小反而会膨胀。这也解释了算法题里为什么要求“只在字符出现次数大于1时写数字”或“压缩后必须更短才返回压缩串”。

5.2 如果想做更复杂压缩：Huffman 与 LZ 系列

面试官如果觉得你 RLE 答得不错，可能会追问“你还知道哪些压缩算法”。这时候你可以从两个方向回应：熵编码和字典编码。

Huffman 编码的核心是根据字符出现的频率分配变长二进制码，出现频率越高的字符用越短的码。它适合处理字符分布差异明显的数据，是 ZIP、JPEG、MP3 等格式中重要的组成部分。

LZ77/LZ78 系列则使用滑动窗口或字典记录已经出现过的重复片段，用引用替换重复内容。我们常用的 Gzip、PNG 和 ZIP 都离不开 LZ 系列算法，往往是先把重复片段找出来，再用 Huffman 对结果编码。

回答时不需要现场手写完整实现，能把三层递进关系讲清楚，面试官就知道你对压缩谱系是有概念的。

5.3 刷完这道题之后，可以往哪些方向深入

压缩字符串只是双指针基本功的一个切片。做完它，我建议你趁热打铁刷几道相关题目：LeetCode 26 删除有序数组中的重复项、27 移除元素、283 移动零。它们的核心套路都是“一个指针负责挑出有效元素，一个指针负责覆盖写入位置”，和压缩字符串的双指针完全同源。

如果你想进一步理解字符串相关算法，可以看看 KMP 匹配、Trie 树、字符串哈希等方向，但这些属于进阶内容，不必一头扎进去。还有一点想提醒：网上热词里会刷出很多“深度学习算法”“语义分割算法”“粒子群算法”，它们和这道压缩字符串题没有直接关系。这个题考的是最基础的数组操作和边界控制，别被“算法”这个大帽子吓到，先把地基打牢，后续学什么都会轻松许多。

6. 我的实操心得与建议

做这类原地修改的题目，我最大的心得是：一定不要干想，动笔在纸上画格子。把数组画成一个小方格，手动标出read和write每一步的位置，跑上两个例子之后，那些关于“会不会覆盖未读数据”“数字到底写在哪里”的疑问会瞬间消失。我第一次写 10 个连续a的用例就发现，自己原本想用一个字符存数字的想法根本行不通，纸上推演直接救了命。

还有两个小技巧值得分享。第一，把“定位组首、统计长度、写回编码”分成三个清晰的动作，哪怕不拆函数，也要在注释里标清楚，很多隐蔽 bug 都发生在三个动作互相嵌套的边界条件里。第二，测试用例一定要自带，尤其是空数组、单个字符、全部相同字符、单字符与多字符混合这四类。面试现场只跑题目样例是远远不够的，你多跑一个边界用例，面试官眼里你的代码质量就上一个台阶。

最后说一个编码习惯。写这类双指针题时，变量命名尽量用read、write、count，而不是i、j、k。你可能会觉得名字长短无所谓，但实际调试时，带含义的名字能让你在read和write交错的行为里更快定位问题。面试官看代码也更容易跟着你的思路走。这个习惯一开始可能不觉得重要，等你被i、j的边界搞疯一次，就知道它有多值钱了。