模拟算法实战：从外观数列到数青蛙的状态机思维

1. 模拟算法：外表简单，拆开全是细节

1.1 与其背模板，不如先理解“状态”

先说个容易被忽略的事：模拟题通常不需要复杂的数学推导，也不依赖高级数据结构，真正拉开差距的地方，是你能不能“照着规则一步步推进”而不遗漏边界。外观数列和数青蛙就是两块很好的试金石。

我在模拟题上吃过不少亏。早期总觉得模拟题就是“翻译题目”，后来才发现，翻译只是第一步，难的是在翻译过程中保持状态的正确性。外观数列看似只是“数数”，但它每一轮都会生成一个新字符串，新字符串又成为下一轮的输入，这中间如果你只是“大致知道逻辑”，极容易在细节上翻车。数青蛙更是典型，多个叫声交叉出现，你要判断的不仅是顺序，还有并发数量，甚至还要识别哪些输入是根本非法的。

简单说，模拟算法是一种“忠实执行规则”的算法策略。它不追求巧妙，追求的是把题目的状态机完整地建出来，然后在每一步用合适的变量记录当前状态，按输入推进状态并收集结果。你把规则想清楚，代码往往就能写对；你漏掉规则，代码就只能在测试用例里反复挣扎。

1.2 为什么这两道题值得放在一起讲

外观数列和数青蛙表面上完全不沾边：一个是纯字符串生成，一个要处理多对象并发。但它们的内核是一致的——你都需要明确“当前处于哪个阶段”，都需要在状态迁移时做合法性检查。外观数列的“阶段”是同一个字符串里一段连续相同字符的计数；数青蛙的“阶段”是一只青蛙从发出 c 到发出 k 的完整叫声链条。

放在一起的好处是，你可以用同一个思维框架去套两题，然后看到模拟题的两种典型变体：

• 第一种变体：生成类模拟。问题自己会生长，你每轮基于上一轮的状态算新状态。外观数列就是这种。
• 第二种变体：输入类模拟。给你一串动作序列，你要不停分配资源、维护状态，并判断资源的最值。数青蛙就是这种。

两类题在工程里都很常见。你写日志解析脚本，处理“上报-确认-完成”的消息时，本质就是在做输入类模拟；你写编译器词法扫描器，把字符流聚合成 token 时，本质上就是外观数列里“对连续相同字符分组计数”的升级版。所以这两道题不是纯粹刷题用的，它们背后是真实场景里非常基础的建模能力。

2. 外观数列：每一轮都在重新扫描、重新计数

2.1 先把规则拆干净：什么是“外观”

题目描述是这样的：从数字 1 开始，每一项都依据前一项生成，规则是“对前一项中每种连续的数字进行计数，并描述出来”。

比如第一项是1。它只有一个数字 1，所以描述为“一个 1”，写成11，这是第二项。第二项11是两个连续的 1，描述为“两个 1”，写成21，这是第三项。第三项21是一个 2、一个 1，分别描述后合起来就是1211，这是第四项。第四项1211从左到右看，先是 1 个 1，然后 1 个 2，然后 2 个 1，于是得到111221，这是第五项。

关键点在“连续”两个字。你不能把一个字符串里所有相同的字符加总，必须按“连续出现”的片段去描述。1211这个串里两个 1 并不连续，所以你必须分开数成“1 个 1”和“2 个 1”，而不是“3 个 1”。我第一次手推时就在这里犯了错，还以为自己推错了，后来才发现必须严格分段。

所以这题的数学模型可以这么看：给定一个字符串 S，把它切分成若干不可再分的连续相等字符段，比如111221切成111、22、1三段，然后每一段输出“长度 + 字符”，最后拼起来。这个过程重复 n 次，就是从第 1 项长到第 n 项的过程。

2.2 逐轮模拟的写法和细节

实现上最直接的方式就是迭代。初始状态下，prev = "1"。然后从第 2 项开始，每一轮都扫描prev，构造curr，最后把curr赋给prev。

我用伪代码说明一下主循环：

prev = "1" for i = 2 to n: curr = "" index = 0 while index < length(prev): count = 1 while index + 1 < length(prev) and prev[index] == prev[index + 1]: count += 1 index += 1 curr += count.toString() + prev[index] index += 1 prev = curr return prev

这个循环里最容易写错的地方是内部那个计数 while。注意两个条件缺一不可：一是不能越界，二是下一个字符必须和当前字符相同。合在一起写index + 1 < len && prev[index] == prev[index + 1]就能安全地数完一整段。

再提醒一个细节：count.toString()这一步不可省。输出1211中的12是“字符 1 接着字符 2”，不是数字十二。如果你用数值相加，比如count + prev[index]，在某些语言里会先把整数和字符自动转成数值相加，再转回字符串时就可能得到错误的字符。我实际编码时吃过这个亏，Python 里str(count) + prev[index]没问题，但在其他强类型语言里就要格外注意类型转换。

还有一个边界：当 n = 1 时，循环一次都不执行，直接返回prev，也就是"1"。这个逻辑涵盖在 for 循环里，不需要单独特判，但如果你用 while 循环递减 n 来写，就得小心 n 为 1 时别把prev重置掉。

2.3 复杂度到底高不高

很多人第一次看到这题会担心：字符串会不会长得飞快，导致最后根本无法运算？实测一下就知道数字长得很凶。第 1 项长度 1，第 5 项长度是 6，第 10 项长度变为 10 左右，第 20 项长度已经超过 100，第 30 项长度在 700 上下。它的长度增长大致是每一项增长约 1.3 倍，所以第 n 项的字符串长度近似是1.3^n量级。

于是时间复杂度就是O(sum_{i=1}^{n} L_i)，其中L_i是第 i 项的长度。这个复杂度是超线性但又不是指数爆炸的，n 在 30 以下完全无压力，n 到 50 也还在绝大多数在线评测系统的限制内。

空间上，你只需要保留上一项和当前项两个字符串，是O(L_n)，几乎没有额外负担。这里不建议用递归从第 n 项一步步回溯生成，因为状态会重复计算；从第 1 项往上推是更自然也更高效的方式。

3. 数青蛙：用计数器维护并发叫声的阶段

3.1 把“最少青蛙”翻译成可计算的东西

数青蛙这题给一个字符串，里面只包含c、r、o、a、k五种小写字母，表示若干只青蛙的叫声录音。一只青蛙完整叫一次，必须严格按照c -> r -> o -> a -> k的顺序发出这五个字符。你可以把它的叫声看成一条流水线，c 是流水线的起点，k 是流水线的终点。字符串是这些青蛙的叫声叠加在一起的结果，也可能是非法数据。

题目问的是：完成整段录音最少需要几只青蛙。如果字符串本身不合法，返回 -1。

难点在于多只青蛙可以同时叫，它们的叫声穿插在一起。比如crcoakroak这只串，你按顺序扫描时，第一次 c 开始了一只青蛙，然后 r 把它推进到第二阶段，紧接着又一个 c 开始第二只青蛙，之后 o 让第一只进入第三阶段……我们该怎么判断哪只青蛙对应哪个字符？

一个很自然的想法是：不要纠结具体哪只青蛙，只需要统计“当前处在哪个阶段”的青蛙数量。比如当前有一只青蛙等待 r，那当扫描到 r 时，就消耗一个等待 r 的青蛙，把它推进到等待 o 的状态。这个“统计各阶段等待数量”的思路，正是模拟题里非常经典的“状态计数器”法。

3.2 核心算法：状态迁移里的进与出

具体实现可以维护一个长度为 5 的数组或者 5 个变量，对应c、r、o、a、k五种状态，含义是“已经发出了这个字符、正在等待下一个字符的青蛙数量”。然后逐个扫描输入字符：

• 遇到c：新的青蛙开始叫，cnt_c += 1。此时它进入了“等待 r”的状态。
• 遇到r：必须有一只青蛙当前在“等待 r”状态。如果有，cnt_c -= 1，cnt_r += 1；如果没有，说明这个 r 没有对应的 c，字符串非法，直接返回 -1。
• 遇到o：同理，需要cnt_r > 0，然后cnt_r -= 1，cnt_o += 1。
• 遇到a：需要cnt_o > 0，然后cnt_o -= 1，cnt_a += 1。
• 遇到k：需要cnt_a > 0，然后cnt_a -= 1。这一步意味着有一只青蛙完整叫完了，它离开系统。

扫描过程中，任意时刻正在同时叫的青蛙数量是cnt_c + cnt_r + cnt_o + cnt_a，也就是还没叫完、仍在等待后续字符的青蛙数量。这个数量的最大值就是同时发声的青蛙峰值，也就是最少需要的青蛙数。

我举一个具体例子，字符串croakcroak：

• 第 1 个字符 c，cnt_c = 1。
• 第 2 个字符 r，cnt_c = 0，cnt_r = 1。
• 第 3 个字符 o，cnt_r = 0，cnt_o = 1。
• 第 4 个字符 a，cnt_o = 0，cnt_a = 1。
• 第 5 个字符 k，cnt_a = 0，第一只青蛙结束。
• 第 6 到第 10 个字符重复同样过程。

整个过程中 cnt 总和最多只有 1，答案就是 1。

再看crcoakroak：

• 第 1 个 c，cnt_c = 1。
• 第 2 个 r，cnt_c = 0，cnt_r = 1。
• 第 3 个 c，cnt_c = 1。
• 第 4 个 o，cnt_r = 0，cnt_o = 1。
• 第 5 个 a，cnt_o = 0，cnt_a = 1。
• 第 6 个 k，cnt_a = 0，第二只青蛙结束。
• 第 7 个 r，此时 cnt_c = 1，所以 cnt_c = 0，cnt_r = 1。
• 第 8 个 o，cnt_r = 0，cnt_o = 1。
• 第 9 个 a，cnt_o = 0，cnt_a = 1。
• 第 10 个 k，cnt_a = 0。

这里第三只青蛙其实是第 3 个字符 c 开的，它比第二只青蛙（第 1 个 c 开的）更晚结束，于是同一时刻最多有两只在叫，答案就是 2。

用代码写出来大概是这样：

def minNumberOfFrogs(croakOfFrog: str) -> int: cnt = [0] * 5 mapping = {'c': 0, 'r': 1, 'o': 2, 'a': 3, 'k': 4} ans = 0 active = 0 for ch in croakOfFrog: idx = mapping[ch] if idx == 0: cnt[0] += 1 active += 1 ans = max(ans, active) else: if cnt[idx - 1] == 0: return -1 cnt[idx - 1] -= 1 cnt[idx] += 1 if idx == 4: active -= 1 if active > 0: return -1 return ans

这个版本维护了一个active变量，表示正在叫、还没叫完的青蛙数量。你也可以不用active，直接在所有位置计算sum(cnt)再求最大值，原理一样，但active更省事。注意结束时要检查active > 0，否则会出现“有青蛙叫了一半”的情况，比如输入croakc——第一只青蛙完整叫完，第二只刚发出 c 却没继续，这是非法数据。

3.3 非法序列的全部判断点

非法输入在这题里经常被低估。我归纳了几种典型情况：

1. 字符顺序错误。比如croak中穿插了crok这样的局部字符串，扫描到k时前一个状态a的计数为 0，直接返回 -1。
2. 各字符总数不等。合法的完整叫声里 c、r、o、a、k 五个字符数量必然相等。扫描结束时如果cnt数组里还有非零值，说明存在未完成的叫声，返回 -1。
3. 字符串长度不是 5 的倍数。因为完整叫声恰好 5 个字符，如果长度不能整除 5，可以直接判定非法。这个预判能省不少时间。
4. 字符串为空。长度为 0 时没有青蛙叫，理论上答案应该是 0。你可以提前返回 0，也可以让主流程自然得出 ans = 0。

这些判断在代码里其实都很轻量，但漏掉哪一个都会被阴险的测试案例抓到。我记得就有一次没检查“扫描结束后 active 必须为 0”，结果在一个结尾处残留未完成叫声的用例上卡了很久。

4. 模拟题最常见的三种翻车现场

4.1 边界没卡住：长短与越界

外观数列里最典型的边界问题是“只有一位数字时怎么数”。prev长度为 1 时，内部 while 循环要从 index + 1 < len 这个条件开始判断，如果写成while (prev[index] == prev[index + 1])，第一轮就越界了。

数青蛙的边界则是“字符不在映射表里怎么办”。严格来说题目输入只包含那五个字母，实际工程中我会顺手加一个 else 分支直接返回 -1，不怕一万就怕万一。这种防御性写法成本为零，但能避免很多线上解析问题的排查成本。

另外，数青蛙里有个隐藏边界：字符串长度是 5 的倍数会提前预判非法，但长度整除 5 也不能说明一定合法，比如crroa长度是 5，却不合法。预判只是过滤器，真正合法性判断还是要走一遍状态机。

4.2 状态残留：上一轮没清干净

模拟题只要你有一个状态没复位，后面整个结果都会错。外观数列里，每一轮生成curr前必须用空字符串初始化；数青蛙里，每一轮cnt数组的增减必须准确，该减的没减、该加的没加，都会让后续判断失效。

这点听起来像废话，但真写的时候容易在分支合并里蒙圈。比如数青蛙里，不同字符会走不同分支，如果某个分支没写cnt[idx] += 1，下一个字符来判断前一个状态数量时就可能为 0，导致一个本来合法的串被误判成非法。我调试这类问题时最常用的办法是打印cnt数组的中间状态，瞄一眼就能发现是谁少加了一步。

4.3 复杂度误判：以为自己写的是 O(n)，实际翻倍

外观数列的复杂度前面聊过，本质不是严格的 O(n)，而是 O(字符串长度总和)。如果 n 不大，问题不大。可如果题目变形成让你输出第 n 项的完整字符串，而不是只返回长度，那内存和输出本身就会成为瓶颈。做题时要分清题目问的是“长度”还是“内容”，同样是外观数列，不同问法对应完全不同的实现要求。

数青蛙是严格的 O(n) 时间、O(1) 空间，只扫一遍字符串。但很多人会把“求最大值”和“求最终数量”搞混，导致多写一遍循环。其实一次扫描过程中就能维护好最大值，没必要把字符先收集起来再统计。

5. 从这两道题提取的模拟题通法

5.1 一套可以复用的思考流程

做模拟题，我习惯按这个顺序思考：

1. 找出题目里的“状态变量”。问自己：每一步推进，什么东西在变？青蛙叫的阶段、当前生成的字符串、剩余操作数，这些就是状态。
2. 画出状态迁移表。填入“当前状态、遇到什么事件、转移到什么状态、需要满足什么前置条件”。数青蛙的迁移表一行就是一个字符规则。
3. 写代码时严格按迁移表实现，任何一条迁移都要有前置校验和后续更新。
4. 扫描结束后统一检查状态是否归位。外观数列看是否生成完毕，数青蛙看cnt是否全清零。
5. 补边界条件。长度奇偶、首尾字符、空输入、单个输入。

这五步做完，绝大多数模拟题都不会跑偏。

5.2 两类变体的延伸方向

外观数列代表的那类“迭代生成”问题，延伸出去就是各种“外观序列”“运行长度编码”的变体。你在学 Run-Length Encoding 时，代码核心和外观数列完全一致：从左到右扫描，连续相同项合并为“数量 + 值”。如果你能把外观数列的扫描逻辑写顺，RLE 压缩算法的实现就基本会了。

数青蛙代表的那类“并发调度”问题，延伸出去更广。任务调度器里给你一堆任务和冷却时间，问最少需要多少单位时间才能跑完；操作系统里模拟多个进程在不同 CPU 上的调度；甚至网络流控里按 token 桶模型来限流，都是类似的“状态计数 + 流水线推进”模式。它们的共同点是：你需要维护一组等待队列，每次事件到达时，从对应队列里取出一个任务推进到下一步。

最后说说我在实际项目里怎么用这些模型的。写日志解析器时，日志会按固定流程推进：收到请求、校验参数、处理业务、返回结果。我会用一个状态机，每个日志行对应一个迁移事件，遇到不合法的跳转就把日志标成异常，这跟数青蛙扫描非法字符的处理方式一模一样。所以这两道题的价值不只是面试，它训练的是你从混乱的输入中维护清晰状态的能力，而这种能力，几乎所有工程场景都用得上。