“模拟(数青蛙)(5)”这个标题第一次看到的人多半会以为是把儿歌唱一遍一只青蛙一张嘴两只眼睛四条腿扑通一声跳下水。但你真把这个需求翻译成一个程序题会发现它远没有歌词那么温柔。很多入门模拟题都有这种特性规则谁都能看懂可一旦要输出、要对边界、要对大量输入做状态判断问题就全冒出来了。我最早接触这道题是在某在线练习系统的入门题库里它的题面就叫“模拟数青蛙”编号刚好是5。后来在不同训练营里我又看到过它的变体有的是让你按数量生成儿歌文本有的是给你一串青蛙叫声的字符序列让你算最少同时存在几只青蛙。两种都挂着“数青蛙”的名字考核的核心却很不一样。这篇文章一次把两种常见玩法都拆开讲代码也直接能跑适合刚学完循环和数组、想练“模拟题”的人也适合正在刷字符串处理题目的朋友对照参考。1. 先拆需求这一题到底要模拟什么1.1 儿歌版N只青蛙的所有器官数量都能用乘法算儿歌版的规则很简单一只青蛙对应一张嘴、两只眼睛、四条腿、一次“扑通”声。两只青蛙就是两张嘴、四只眼睛、八条腿、两次扑通。这里不存在什么隐藏逻辑核心规律就是所有指标都跟着青蛙数量线性增长。青蛙数嘴眼睛腿扑通声11241224825510205nn2n4nn问题里的(5)如果是当作参数理解那就是要求模拟5只青蛙的完整输出如果是当作题号理解它就是入门模拟题里的第5题。无论哪种你都需要把“n只青蛙”翻译成一句连贯的中文5只青蛙、5张嘴、10只眼睛、20条腿、5声扑通。实话说这个版本的代码非常短但它考察你的是两件容易被忽略的事一是能不能把自然语言规则转换成乘法公式二是能不能把“扑通五声”这种约定俗成的说法用代码正确呈现。很多人卡就卡在第二点上后面我会专门讲输出格式的坑。1.2 另一种题面给一串字符数最少有几只青蛙同时在叫进阶版本的“数青蛙”不再让你生成歌词而是给你一个字符串比如croakcroak。这里的croak就是一声完整的蛙鸣由c → r → o → a → k五个字母按顺序组成。题目要求你判断这串叫声是否合法如果合法返回同时发出叫声的最少青蛙数量如果不合法返回-1。我第一次看这个题面时觉得挺抽象。后来我把它当合唱团来理解每一只青蛙就是一名歌手一个歌手必须按顺序唱出c-r-o-a-k五个音。字符串就是某个时间段内所有人发出的音的堆叠记录。你只能看到这些字母按时间顺序排在一起却不知道哪个音属于哪只青蛙。现在要你判断最少需要多少只青蛙才能形成这样的声音序列。举个例子croakcroak可以是一号青蛙完整叫完一次紧接着二号青蛙也叫完一次所以答案只需要1只青蛙。但crcoakroak就不一样它像一号青蛙唱到c-r的时候二号青蛙已经迫不及待地开始了c两只青蛙的进度在同一段时间里重叠了因此最少需要2只青蛙。这个过程就是典型的“模拟”不套公式、不做推测一个字符一个字符地处理实时维护当前有几只青蛙在叫。1.3 为什么这类题叫“模拟”而不是“计算”很多人会把模拟题和数学题搞混。数学题的思路通常是找到规律后直接带公式比如计算第n项斐波那契数列时可以优化成矩阵快速幂模拟题则要求你老老实实按照事件发生的顺序把每一步状态变化走一遍。青蛙歌版本还比较简单用乘法就能cover但叫声字符串版本就必须用状态推进的方式不断更新当前进展。模拟题的训练价值就在这里它逼着你把现实规则拆成程序状态你会考虑什么时候开始计数、什么时候结束计数、什么时候应该废弃这条记录。这个过程和写业务逻辑很像比如处理聊天消息队列、统计直播间同时在线人数、解析日志中的嵌套事件本质上都是跟着事件流走维护一个动态状态。2. 核心细节解析与实操要点2.1 用五个计数器表示叫声进度处理叫声字符串时最直接的想法可能是扫描每个字符看看它是不是某个“未完成青蛙”的下一个音。但这样会引出许多复杂判断比如这只青蛙之前唱到哪了、如何标记它的进度。更简洁的做法是维护5个计数器分别对应c、r、o、a、k这五个阶段。它们记录的不再是“某只具体的青蛙”而是“当前有多少只青蛙已经唱到了对应节点”。当遇到一个c说明有青蛙开始发声启动计数器遇到r说明有青蛙从c阶段进入r阶段那么c计数器减一、r计数器加一遇到k就表示有青蛙完整结束a计数器减一同时当前活跃青蛙数减一。这其实就是把每只青蛙的状态压缩到一组数字里。你并不需要关心具体是哪只青蛙因为所有青蛙遵循同样的状态流转规则。用一个数组cnt[5]记录五个阶段的在途数量再用一个整型active表示当前正在发声的青蛙数整个过程就能在一遍扫描里完成。2.2 并发最高值才是要输出的答案既然我们需要“最少需要的青蛙数量”那就要重点盯住active的最大值。每当扫描到一个新的cactive就加1说明又多了一只正在发声的青蛙每当扫描到kactive就减1说明有一只青蛙完成了完整叫声。整个过程中active曾经达到的最大值就是某个时刻同时发声的青蛙数量下限。这里有个容易被绕进去的点croakcroak明明有两个croak为什么答案是1而不是2因为这两组叫声完全可以发生在同一只青蛙身上第一声叫完它休息一下再叫第二声并不需要第二只青蛙同时存在。也就是说字符串里croak出现的次数不是答案它们是否重叠、重叠了多少才是决定最少青蛙数量的关键。2.3 非法的叫声序列为什么必须返回-1如果给你一个croakcrook第四只字符应该是a却出现了o那么这说明序列混乱了可能是有青蛙跳过了中间环节也可能是输入根本就是错的。处理这类情况需要在扫描过程中检查前置计数器当遇到r时如果当前c阶段的计数器已经为0说明没有任何青蛙处在可以发出r的状态那么整个序列非法立即返回-1。另外字符串长度必须是5的倍数。每只青蛙完整叫一次贡献5个字符长度不能被5整除则说明一定存在残缺叫声。扫描结束后还要检查5个计数器是否全部归零。如果某个计数器还残留着数字意味着有青蛙只叫了一半就断了同样非法。2.4 输出格式才是儿歌版的隐藏考点别小看“扑通五声”这个输出不同题库、不同题面要求的格式很可能不一样。常见的有两种重复型把“扑通”这个词重复n次再接“声跳下水”。例如5只青蛙输出“扑通扑通扑通扑通扑通声跳下水”。数字型直接用数字表示例如“扑通5声跳下水”。很多在线判题系统对中文输出非常严格多一个空格、少一个逗号、半角逗号和全角逗号混用都会判WA。我见过一个特别典型的错误同学写代码时用了英文逗号“,”而题面样例是全角逗号“”提交了三次才发现问题。所以在写输出时我习惯先确认题面的原始字符串把引号、逗号、句号都复制出来而不是自己凭记忆敲。3. 实操过程与核心环节实现3.1 版本一一个Python函数生成任意数量青蛙的儿歌最简单的方式是直接把四项倍数关系写成格式化字符串。我提供一个可复用的函数参数包括青蛙数量和输出风格。def frog_verse(n: int, style: str repeat) - str: if n 1: return 青蛙数量至少为1 head f{n}只青蛙{n}张嘴{2 * n}只眼睛{4 * n}条腿 if style repeat: return head 扑通 * n 声跳下水。 return head f扑通{n}声跳下水。 print(frog_verse(5))运行结果5只青蛙5张嘴10只眼睛20条腿扑通扑通扑通扑通扑通声跳下水。这段代码的核心只有两个2*n代表眼睛数4*n代表腿数。扑通 * n在Python里表示把字符串重复n次5只青蛙就连续出现5个“扑通”后面紧跟“声跳下水”。如果你需要用这种文本做批量展示直接循环调用for i in range(1, 6): print(frog_verse(i))输出会是一到五只青蛙的完整儿歌每一行之间互不影响。3.2 版本二从叫声字符串推断最少青蛙数量这个版本是真正的核心完整代码并不长但每一步都需要想清楚。def min_frogs(s: str) - int: if len(s) % 5 ! 0: return -1 order {c: 0, r: 1, o: 2, a: 3, k: 4} cnt [0] * 5 active 0 best 0 for ch in s: idx order.get(ch) if idx is None: return -1 cnt[idx] 1 if idx 0: # c 是新声音开始 active 1 best max(best, active) else: # 必须有上一阶段的声音在等待 if cnt[idx - 1] 0: return -1 cnt[idx - 1] - 1 # k 表示完整结束释放当前活跃青蛙 if idx 4: cnt[4] - 1 active - 1 # 所有阶段必须清零 if all(x 0 for x in cnt): return best return -1逐行拆一下逻辑。len(s) % 5是快速过滤无效输入但不充分只能算前置检查。cnt[0]到cnt[4]分别记录处于c、r、o、a、k阶段的声音数量。这里的重点是每个非c字符都会消耗一个上一层计数而k额外消耗一个cnt[4]因为它自己刚被加进来需要先结算再去减活跃数。用几组数据验证一下print(min_frogs(croak)) print(min_frogs(croakcroak)) print(min_frogs(crcoakroak)) print(min_frogs(ccccc rrrrroooooaaaaakkkkk)) print(min_frogs(croakcrook))第二行里不要有空格这里是为了阅读方便。实际用例分别是ccccc rrrrroooooaaaaakkkkk.replace( , )直接写应该写成cccc crrrrroooooaaaaakkkkk看下面更清楚print(min_frogs(croak)) # 1 print(min_frogs(croakcroak)) # 1 print(min_frogs(crcoakroak)) # 2 print(min_frogs(cccccrrrrroooooaaaaakkkkk)) # 5 print(min_frogs(croakcrook)) # -1第五个用例cccccrrrrroooooaaaaakkkkk看起来有点夸张它其实对应5只青蛙在同一时间段里同步发声5个c意味着5只青蛙同时开始之后连续5个r、5个o、5个a、5个k。它们之间没有交叉延迟所以并发峰值就是5返回值恰好是5和标题里的(5)形成一个很漂亮的对应。croakcrook则是在第二个croak后面接的不是a而是o程序处理到第三个字符o时会检查cnt[1]是否为0。因为这个o没有对应的前置r阶段所以直接返回-1。3.3 版本三C快速实现如果你刷题用的是C实现思路完全相同只是把数组换成int cnt[5]字符到下标的映射用switch或者一个简单的函数处理即可。#include string #include algorithm using namespace std; int minNumberOfFrogs(string s) { if (s.size() % 5 ! 0) return -1; int cnt[5] {0}; int active 0, best 0; for (char ch : s) { int idx; if (ch c) idx 0; else if (ch r) idx 1; else if (ch o) idx 2; else if (ch a) idx 3; else if (ch k) idx 4; else return -1; cnt[idx]; if (idx 0) { active; best max(best, active); } else { if (cnt[idx - 1] 0) return -1; cnt[idx - 1]--; if (idx 4) { cnt[4]--; active--; } } } for (int i 0; i 5; i) { if (cnt[i] ! 0) return -1; } return best; }这段代码的空间占用是常数级5个int时间消耗是单次O(n)扫描。字符串长度哪怕到十万、百万也只是线性增长完全不用担心性能。3.4 自测用例与结果对照为了方便自己排查我习惯把测试用例集中放在一个表格里运行之后逐条对比。输入期望输出说明croak1一只青蛙完整叫完croakcroak1同一只青蛙叫两次crcoakroak2两只青蛙交叠croakcrcoakroak2前面一只结束后又出现两只交叠cccccrrrrroooooaaaaakkkkk55只青蛙同时发声croakcrook-1o之前没有对应的rcroakcroa-1最后一组不完整残留关系未清零crocak-1o后直接出现c无法匹配最后一条crocak输入扫描到第四个字符时是a但此时cnt[2]为0因为前面只有一个o已经被c消耗掉了所以会返回-1。这种用例专门用来测你是否正确做了前置检查。4. 常见问题与排查技巧实录4.1 格式错误输出了英文逗号和半角符号我辅导过的一个同学写儿歌版本时用了ASCII逗号,输出结果从视觉上和样例没区别但判题系统就是不给过。后来把head改成全角逗号和全角句号一次通过。中文题面就是有这种坑建议先把样例输出复制到一个文本编辑器里逐个字符对比。4.2 把croakcroak误判成2只青蛙这个错误几乎每个初学者都会遇到。原因很简单看到两个完整的croak就想当然认为两个“croak”必然对应两只青蛙。但题目问的是“最少需要几只”并没有规定一只青蛙只能叫一次。只要第一个croak结束之后第二只才开始那同一只青蛙完全可以复用。要区分“出现次数”和“同时存在数量”这两个概念并发峰值看的不是总数而是重叠数。4.3 最后忘了检查计数器是否清零有一种隐蔽错误是返回了看似合理的结果但实际少了最后一步校验。例如输入croakcroa扫描结束时active已经回到0best也确实为1看起来一切正常。但cnt[0]和cnt[3]并不为0说明最后一只青蛙的叫声是不完整的。如果不做最终的归零判断就会错误地返回1而不是-1。我在初版代码里也踩过这个坑所以现在总会画蛇添足地写一遍all(x 0 for x in cnt)。4.4 用正则匹配来拆分叫声结果越拆越乱曾经有人问我能不能用正则或字符串替换来做先数croak出现次数再把嵌套的交叠串拆出来。理论上不是完全不行但字符串一旦长起来嵌套和重叠会让正则表达式变得极其脆弱。而且这种方法的时间复杂度和可读性都很差。状态计数器方案只用一个循环就解决了问题不需要回溯、不需要栈这是它最大的优势。4.5 空字符串和长度为1的输入空字符串长度是0可以被5整除直接进入循环最终best是0返回0。但有些题目会规定字符串长度至少为1有些题则要求空字符串返回0。我建议写代码时先判断长度如果题意没有特殊说明空字符串返回0是符合直觉的。长度为1的输入比如c扫描后cnt[0]为1最终归零判断失败返回-1也符合逻辑。5. 从这题延伸出去一次循环就是一个状态机5.1 把“croak”想成五个状态如果你对“状态机”这个概念还不熟这个题就是一个很好的入门例子。每只青蛙在c、r、o、a、k之间单向流转当前计数就是各状态的在途数量。遇到合法字符就推动状态前进遇到非法字符就报错所有状态归零表示一轮处理结束。这和做字符串解析、协议解析的思路一模一样。做音视频流媒体时经常遇到分片数据包的处理逻辑数据包必须按顺序经过多个阶段每个阶段都有对应的缓存计数器不完整的序列要丢弃。你看这和数青蛙本质上没有区别。状态机看似抽象但在实际工程里无处不在。5.2 可以自己扩展的玩法如果觉得这个题过于简单可以加几个限制条件来扩展增加多个叫声种类比如“呱呱”用guagua表示统计不同种类的并发青蛙数量。增加随机叫声模拟器随机生成合法序列再返回最少并发数用来测试你的算法。做一个可视化程序用进度条直观展示每只青蛙当前处于哪个阶段。我做完基础版后顺手写过一个字符动画版在终端里用五个小横条代表五个阶段每次扫描到对应字符时横条前进一格。看到动画那一瞬间状态机的理解就彻底落地了。5.3 青蛙数量5的另一个视角把这两个版本放在一起看儿歌版直接告诉你5只青蛙有多少器官字符串版本则要你自己从一串叫声里把一个“5”挖出来。前者是输出模拟后者是过程模拟。它们共同的地方在于都不需要什么高级数据结构和复杂算法只要你能耐住性子把规则的每一步走完答案自己就会浮现出来。这种耐心其实就是编程里最需要的底层能力。最后说一句我自己的体会很少有人第一遍就能把这种模拟题写对通常都会在某个边界条件上翻车。翻车不是坏事关键是你能不能在调试信息里看到计数器的状态变化。我在min_frogs里临时加过一行print(cnt, active, best)每次遇到预期之外的结果这一行能直接告诉我当前状态卡在哪一步。遇到此类问题不要只盯最终答案先把中间状态打出来问题会清楚很多。如果你也在做类似的模拟题可以把“状态打印”作为第一调试手段。等到代码稳定了再删掉。这个习惯救过我很多次也希望对你有帮助。 
长河君 · 2026/10/15 9:55:45 · 阅读 1.2k 数青蛙模拟题全解析：从儿歌生成到状态机计数
“模拟(数青蛙)(5)”这个标题第一次看到的人多半会以为是把儿歌唱一遍一只青蛙一张嘴两只眼睛四条腿扑通一声跳下水。但你真把这个需求翻译成一个程序题会发现它远没有歌词那么温柔。很多入门模拟题都有这种特性规则谁都能看懂可一旦要输出、要对边界、要对大量输入做状态判断问题就全冒出来了。我最早接触这道题是在某在线练习系统的入门题库里它的题面就叫“模拟数青蛙”编号刚好是5。后来在不同训练营里我又看到过它的变体有的是让你按数量生成儿歌文本有的是给你一串青蛙叫声的字符序列让你算最少同时存在几只青蛙。两种都挂着“数青蛙”的名字考核的核心却很不一样。这篇文章一次把两种常见玩法都拆开讲代码也直接能跑适合刚学完循环和数组、想练“模拟题”的人也适合正在刷字符串处理题目的朋友对照参考。1. 先拆需求这一题到底要模拟什么1.1 儿歌版N只青蛙的所有器官数量都能用乘法算儿歌版的规则很简单一只青蛙对应一张嘴、两只眼睛、四条腿、一次“扑通”声。两只青蛙就是两张嘴、四只眼睛、八条腿、两次扑通。这里不存在什么隐藏逻辑核心规律就是所有指标都跟着青蛙数量线性增长。青蛙数嘴眼睛腿扑通声11241224825510205nn2n4nn问题里的(5)如果是当作参数理解那就是要求模拟5只青蛙的完整输出如果是当作题号理解它就是入门模拟题里的第5题。无论哪种你都需要把“n只青蛙”翻译成一句连贯的中文5只青蛙、5张嘴、10只眼睛、20条腿、5声扑通。实话说这个版本的代码非常短但它考察你的是两件容易被忽略的事一是能不能把自然语言规则转换成乘法公式二是能不能把“扑通五声”这种约定俗成的说法用代码正确呈现。很多人卡就卡在第二点上后面我会专门讲输出格式的坑。1.2 另一种题面给一串字符数最少有几只青蛙同时在叫进阶版本的“数青蛙”不再让你生成歌词而是给你一个字符串比如croakcroak。这里的croak就是一声完整的蛙鸣由c → r → o → a → k五个字母按顺序组成。题目要求你判断这串叫声是否合法如果合法返回同时发出叫声的最少青蛙数量如果不合法返回-1。我第一次看这个题面时觉得挺抽象。后来我把它当合唱团来理解每一只青蛙就是一名歌手一个歌手必须按顺序唱出c-r-o-a-k五个音。字符串就是某个时间段内所有人发出的音的堆叠记录。你只能看到这些字母按时间顺序排在一起却不知道哪个音属于哪只青蛙。现在要你判断最少需要多少只青蛙才能形成这样的声音序列。举个例子croakcroak可以是一号青蛙完整叫完一次紧接着二号青蛙也叫完一次所以答案只需要1只青蛙。但crcoakroak就不一样它像一号青蛙唱到c-r的时候二号青蛙已经迫不及待地开始了c两只青蛙的进度在同一段时间里重叠了因此最少需要2只青蛙。这个过程就是典型的“模拟”不套公式、不做推测一个字符一个字符地处理实时维护当前有几只青蛙在叫。1.3 为什么这类题叫“模拟”而不是“计算”很多人会把模拟题和数学题搞混。数学题的思路通常是找到规律后直接带公式比如计算第n项斐波那契数列时可以优化成矩阵快速幂模拟题则要求你老老实实按照事件发生的顺序把每一步状态变化走一遍。青蛙歌版本还比较简单用乘法就能cover但叫声字符串版本就必须用状态推进的方式不断更新当前进展。模拟题的训练价值就在这里它逼着你把现实规则拆成程序状态你会考虑什么时候开始计数、什么时候结束计数、什么时候应该废弃这条记录。这个过程和写业务逻辑很像比如处理聊天消息队列、统计直播间同时在线人数、解析日志中的嵌套事件本质上都是跟着事件流走维护一个动态状态。2. 核心细节解析与实操要点2.1 用五个计数器表示叫声进度处理叫声字符串时最直接的想法可能是扫描每个字符看看它是不是某个“未完成青蛙”的下一个音。但这样会引出许多复杂判断比如这只青蛙之前唱到哪了、如何标记它的进度。更简洁的做法是维护5个计数器分别对应c、r、o、a、k这五个阶段。它们记录的不再是“某只具体的青蛙”而是“当前有多少只青蛙已经唱到了对应节点”。当遇到一个c说明有青蛙开始发声启动计数器遇到r说明有青蛙从c阶段进入r阶段那么c计数器减一、r计数器加一遇到k就表示有青蛙完整结束a计数器减一同时当前活跃青蛙数减一。这其实就是把每只青蛙的状态压缩到一组数字里。你并不需要关心具体是哪只青蛙因为所有青蛙遵循同样的状态流转规则。用一个数组cnt[5]记录五个阶段的在途数量再用一个整型active表示当前正在发声的青蛙数整个过程就能在一遍扫描里完成。2.2 并发最高值才是要输出的答案既然我们需要“最少需要的青蛙数量”那就要重点盯住active的最大值。每当扫描到一个新的cactive就加1说明又多了一只正在发声的青蛙每当扫描到kactive就减1说明有一只青蛙完成了完整叫声。整个过程中active曾经达到的最大值就是某个时刻同时发声的青蛙数量下限。这里有个容易被绕进去的点croakcroak明明有两个croak为什么答案是1而不是2因为这两组叫声完全可以发生在同一只青蛙身上第一声叫完它休息一下再叫第二声并不需要第二只青蛙同时存在。也就是说字符串里croak出现的次数不是答案它们是否重叠、重叠了多少才是决定最少青蛙数量的关键。2.3 非法的叫声序列为什么必须返回-1如果给你一个croakcrook第四只字符应该是a却出现了o那么这说明序列混乱了可能是有青蛙跳过了中间环节也可能是输入根本就是错的。处理这类情况需要在扫描过程中检查前置计数器当遇到r时如果当前c阶段的计数器已经为0说明没有任何青蛙处在可以发出r的状态那么整个序列非法立即返回-1。另外字符串长度必须是5的倍数。每只青蛙完整叫一次贡献5个字符长度不能被5整除则说明一定存在残缺叫声。扫描结束后还要检查5个计数器是否全部归零。如果某个计数器还残留着数字意味着有青蛙只叫了一半就断了同样非法。2.4 输出格式才是儿歌版的隐藏考点别小看“扑通五声”这个输出不同题库、不同题面要求的格式很可能不一样。常见的有两种重复型把“扑通”这个词重复n次再接“声跳下水”。例如5只青蛙输出“扑通扑通扑通扑通扑通声跳下水”。数字型直接用数字表示例如“扑通5声跳下水”。很多在线判题系统对中文输出非常严格多一个空格、少一个逗号、半角逗号和全角逗号混用都会判WA。我见过一个特别典型的错误同学写代码时用了英文逗号“,”而题面样例是全角逗号“”提交了三次才发现问题。所以在写输出时我习惯先确认题面的原始字符串把引号、逗号、句号都复制出来而不是自己凭记忆敲。3. 实操过程与核心环节实现3.1 版本一一个Python函数生成任意数量青蛙的儿歌最简单的方式是直接把四项倍数关系写成格式化字符串。我提供一个可复用的函数参数包括青蛙数量和输出风格。def frog_verse(n: int, style: str repeat) - str: if n 1: return 青蛙数量至少为1 head f{n}只青蛙{n}张嘴{2 * n}只眼睛{4 * n}条腿 if style repeat: return head 扑通 * n 声跳下水。 return head f扑通{n}声跳下水。 print(frog_verse(5))运行结果5只青蛙5张嘴10只眼睛20条腿扑通扑通扑通扑通扑通声跳下水。这段代码的核心只有两个2*n代表眼睛数4*n代表腿数。扑通 * n在Python里表示把字符串重复n次5只青蛙就连续出现5个“扑通”后面紧跟“声跳下水”。如果你需要用这种文本做批量展示直接循环调用for i in range(1, 6): print(frog_verse(i))输出会是一到五只青蛙的完整儿歌每一行之间互不影响。3.2 版本二从叫声字符串推断最少青蛙数量这个版本是真正的核心完整代码并不长但每一步都需要想清楚。def min_frogs(s: str) - int: if len(s) % 5 ! 0: return -1 order {c: 0, r: 1, o: 2, a: 3, k: 4} cnt [0] * 5 active 0 best 0 for ch in s: idx order.get(ch) if idx is None: return -1 cnt[idx] 1 if idx 0: # c 是新声音开始 active 1 best max(best, active) else: # 必须有上一阶段的声音在等待 if cnt[idx - 1] 0: return -1 cnt[idx - 1] - 1 # k 表示完整结束释放当前活跃青蛙 if idx 4: cnt[4] - 1 active - 1 # 所有阶段必须清零 if all(x 0 for x in cnt): return best return -1逐行拆一下逻辑。len(s) % 5是快速过滤无效输入但不充分只能算前置检查。cnt[0]到cnt[4]分别记录处于c、r、o、a、k阶段的声音数量。这里的重点是每个非c字符都会消耗一个上一层计数而k额外消耗一个cnt[4]因为它自己刚被加进来需要先结算再去减活跃数。用几组数据验证一下print(min_frogs(croak)) print(min_frogs(croakcroak)) print(min_frogs(crcoakroak)) print(min_frogs(ccccc rrrrroooooaaaaakkkkk)) print(min_frogs(croakcrook))第二行里不要有空格这里是为了阅读方便。实际用例分别是ccccc rrrrroooooaaaaakkkkk.replace( , )直接写应该写成cccc crrrrroooooaaaaakkkkk看下面更清楚print(min_frogs(croak)) # 1 print(min_frogs(croakcroak)) # 1 print(min_frogs(crcoakroak)) # 2 print(min_frogs(cccccrrrrroooooaaaaakkkkk)) # 5 print(min_frogs(croakcrook)) # -1第五个用例cccccrrrrroooooaaaaakkkkk看起来有点夸张它其实对应5只青蛙在同一时间段里同步发声5个c意味着5只青蛙同时开始之后连续5个r、5个o、5个a、5个k。它们之间没有交叉延迟所以并发峰值就是5返回值恰好是5和标题里的(5)形成一个很漂亮的对应。croakcrook则是在第二个croak后面接的不是a而是o程序处理到第三个字符o时会检查cnt[1]是否为0。因为这个o没有对应的前置r阶段所以直接返回-1。3.3 版本三C快速实现如果你刷题用的是C实现思路完全相同只是把数组换成int cnt[5]字符到下标的映射用switch或者一个简单的函数处理即可。#include string #include algorithm using namespace std; int minNumberOfFrogs(string s) { if (s.size() % 5 ! 0) return -1; int cnt[5] {0}; int active 0, best 0; for (char ch : s) { int idx; if (ch c) idx 0; else if (ch r) idx 1; else if (ch o) idx 2; else if (ch a) idx 3; else if (ch k) idx 4; else return -1; cnt[idx]; if (idx 0) { active; best max(best, active); } else { if (cnt[idx - 1] 0) return -1; cnt[idx - 1]--; if (idx 4) { cnt[4]--; active--; } } } for (int i 0; i 5; i) { if (cnt[i] ! 0) return -1; } return best; }这段代码的空间占用是常数级5个int时间消耗是单次O(n)扫描。字符串长度哪怕到十万、百万也只是线性增长完全不用担心性能。3.4 自测用例与结果对照为了方便自己排查我习惯把测试用例集中放在一个表格里运行之后逐条对比。输入期望输出说明croak1一只青蛙完整叫完croakcroak1同一只青蛙叫两次crcoakroak2两只青蛙交叠croakcrcoakroak2前面一只结束后又出现两只交叠cccccrrrrroooooaaaaakkkkk55只青蛙同时发声croakcrook-1o之前没有对应的rcroakcroa-1最后一组不完整残留关系未清零crocak-1o后直接出现c无法匹配最后一条crocak输入扫描到第四个字符时是a但此时cnt[2]为0因为前面只有一个o已经被c消耗掉了所以会返回-1。这种用例专门用来测你是否正确做了前置检查。4. 常见问题与排查技巧实录4.1 格式错误输出了英文逗号和半角符号我辅导过的一个同学写儿歌版本时用了ASCII逗号,输出结果从视觉上和样例没区别但判题系统就是不给过。后来把head改成全角逗号和全角句号一次通过。中文题面就是有这种坑建议先把样例输出复制到一个文本编辑器里逐个字符对比。4.2 把croakcroak误判成2只青蛙这个错误几乎每个初学者都会遇到。原因很简单看到两个完整的croak就想当然认为两个“croak”必然对应两只青蛙。但题目问的是“最少需要几只”并没有规定一只青蛙只能叫一次。只要第一个croak结束之后第二只才开始那同一只青蛙完全可以复用。要区分“出现次数”和“同时存在数量”这两个概念并发峰值看的不是总数而是重叠数。4.3 最后忘了检查计数器是否清零有一种隐蔽错误是返回了看似合理的结果但实际少了最后一步校验。例如输入croakcroa扫描结束时active已经回到0best也确实为1看起来一切正常。但cnt[0]和cnt[3]并不为0说明最后一只青蛙的叫声是不完整的。如果不做最终的归零判断就会错误地返回1而不是-1。我在初版代码里也踩过这个坑所以现在总会画蛇添足地写一遍all(x 0 for x in cnt)。4.4 用正则匹配来拆分叫声结果越拆越乱曾经有人问我能不能用正则或字符串替换来做先数croak出现次数再把嵌套的交叠串拆出来。理论上不是完全不行但字符串一旦长起来嵌套和重叠会让正则表达式变得极其脆弱。而且这种方法的时间复杂度和可读性都很差。状态计数器方案只用一个循环就解决了问题不需要回溯、不需要栈这是它最大的优势。4.5 空字符串和长度为1的输入空字符串长度是0可以被5整除直接进入循环最终best是0返回0。但有些题目会规定字符串长度至少为1有些题则要求空字符串返回0。我建议写代码时先判断长度如果题意没有特殊说明空字符串返回0是符合直觉的。长度为1的输入比如c扫描后cnt[0]为1最终归零判断失败返回-1也符合逻辑。5. 从这题延伸出去一次循环就是一个状态机5.1 把“croak”想成五个状态如果你对“状态机”这个概念还不熟这个题就是一个很好的入门例子。每只青蛙在c、r、o、a、k之间单向流转当前计数就是各状态的在途数量。遇到合法字符就推动状态前进遇到非法字符就报错所有状态归零表示一轮处理结束。这和做字符串解析、协议解析的思路一模一样。做音视频流媒体时经常遇到分片数据包的处理逻辑数据包必须按顺序经过多个阶段每个阶段都有对应的缓存计数器不完整的序列要丢弃。你看这和数青蛙本质上没有区别。状态机看似抽象但在实际工程里无处不在。5.2 可以自己扩展的玩法如果觉得这个题过于简单可以加几个限制条件来扩展增加多个叫声种类比如“呱呱”用guagua表示统计不同种类的并发青蛙数量。增加随机叫声模拟器随机生成合法序列再返回最少并发数用来测试你的算法。做一个可视化程序用进度条直观展示每只青蛙当前处于哪个阶段。我做完基础版后顺手写过一个字符动画版在终端里用五个小横条代表五个阶段每次扫描到对应字符时横条前进一格。看到动画那一瞬间状态机的理解就彻底落地了。5.3 青蛙数量5的另一个视角把这两个版本放在一起看儿歌版直接告诉你5只青蛙有多少器官字符串版本则要你自己从一串叫声里把一个“5”挖出来。前者是输出模拟后者是过程模拟。它们共同的地方在于都不需要什么高级数据结构和复杂算法只要你能耐住性子把规则的每一步走完答案自己就会浮现出来。这种耐心其实就是编程里最需要的底层能力。最后说一句我自己的体会很少有人第一遍就能把这种模拟题写对通常都会在某个边界条件上翻车。翻车不是坏事关键是你能不能在调试信息里看到计数器的状态变化。我在min_frogs里临时加过一行print(cnt, active, best)每次遇到预期之外的结果这一行能直接告诉我当前状态卡在哪一步。遇到此类问题不要只盯最终答案先把中间状态打出来问题会清楚很多。如果你也在做类似的模拟题可以把“状态打印”作为第一调试手段。等到代码稳定了再删掉。这个习惯救过我很多次也希望对你有帮助。