👋 欢迎阅读
🎯 欢迎来到「数青蛙」题解之旅！本文将带你从"安排一群青蛙接力叫出 croak"这一趣味场景出发，深入理解状态机 + 贪心复用的巧妙运用，并掌握如何用计数数组追踪每只青蛙的进度来求出所需青蛙的最少数量。
在开始之前，建议你先：
了解题目背景：这是 LeetCode 1419 题，给定由
c/r/o/a/k组成的字符串，判断能否由若干只青蛙交替叫出完整的"croak"（每只青蛙必须按顺序叫完五个字母），能则返回最少青蛙数，不能返回-1。本质上，问题转化为为每个字符分配一只处于正确阶段的青蛙。明确学习目标：掌握状态计数（hash[i] 表示叫到第 i 个字母的青蛙数）的建模方式，理解优先复用已叫完的青蛙的贪心策略，并熟练处理字母顺序违规与叫声未完成两类失败情况。
准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如
croakOfFrogs = "croakcroak"输出1，croakOfFrogs = "crcoakroak"输出2）。
本文将从问题建模、状态转移、贪心复用、失败判定到代码实现，层层递进。即使你对状态机还不熟悉，我们也会从"每只青蛙叫到哪一步就记一笔账"这一直觉出发，让你轻松抓住核心思想——状态记账，能接就接，接不上就新派。现在，让我们一起调度青蛙，算出最少只数吧！ 🐸🎯
🔥愿旖旎·个人主页
📘学习专栏：《算法专栏》《LangChain学习》《贪心算法》
🌄 钱塘江上潮信来，今日方知我是我
✨当前学习内容：《模拟》
一.题目
1419. 数青蛙 - 力扣（LeetCode）
二、算法分析
一、问题分析（前置分析）
- 题目要求：判断字符串
croakOfFrogs能否拆分成若干个完整的"croak"子序列（每只青蛙按序叫完五个字母），并求最少青蛙数；不能则返回-1。 - 关键约束：每只青蛙必须严格按
c → r → o → a → k顺序叫；同一时刻一只青蛙只能叫一个字母；字符串中只能含这五种字母。 - 核心思路：用
hash[5]记录"当前叫到第 i 个字母的青蛙有几只"，遍历字符串做状态转移：c优先复用已叫完（k）的青蛙，否则新增；其余字母必须由"刚叫完前一个字母"的青蛙接管，否则说明顺序违规，直接返回-1。
📌 例子：为什么"复用叫完的青蛙"能得到最少数量
croakOfFrogs = "croakcroak"：读完第一个"croak"后hash[4] = 1（一只青蛙叫完了）；接着又遇c，此时优先让这只已完成的青蛙重新开始，全程只需1 只青蛙 ✅。若每次遇c都新派青蛙，就会得出 2 只——"能复用就复用"正是"最少"的来源（同时刻最多只有一只青蛙能叫某个字母，而复用已空闲的青蛙不增加并行需求）。
二、算法策略（状态计数 + 贪心复用）
核心步骤：
- 建立索引映射：把
"croak"的五个字母映射为下标0~4（index['c']=0, ..., index['k']=4）。 hash[5]初始化全 0：hash[i]表示"当前叫到第 i 个字母"的青蛙数量。- 遍历每个字符
ch：- 若
ch == 'c'：有叫完的青蛙（hash[4] != 0）则复用它（hash[4]--; hash[0]++），否则新派一只（hash[0]++）； - 否则：必须存在"叫完前一个字母"的青蛙（
hash[index[ch]-1] != 0）才能接管（前者--、当前++），否则返回 -1。
- 若
- 收尾检查：遍历结束后，
hash[0..3]必须全为 0（不能有青蛙卡在半途），否则返回-1。 - 返回：
hash[4]（叫完k的青蛙数 = 同时并行所需的青蛙数 = 最少数量）。
📊 示例（croakOfFrogs = "crcoakroak"，期待2）：
| 字符 | 动作 | hash[0..4]（c,r,o,a,k） | 说明 |
|---|---|---|---|
| c | 无已完成的，新派 | 1,0,0,0,0 | 青蛙 A 开始 |
| r | 由 c 接 | 0,1,0,0,0 | A 叫 r |
| c | 无已完成的，新派 | 1,1,0,0,0 | 青蛙 B 开始 |
| o | 由 r 接 | 1,0,1,0,0 | A 叫 o |
| a | 由 o 接 | 1,0,0,1,0 | A 叫 a |
| k | 由 a 接 | 1,0,0,0,1 | A 叫完（hash[4]=1） |
| r | 由 c 接 | 0,1,0,0,1 | B 叫 r |
| o | 由 r 接 | 0,0,1,0,1 | B 叫 o |
| a | 由 o 接 | 0,0,0,1,1 | B 叫 a |
| k | 由 a 接 | 0,0,0,0,2 | B 叫完，hash[4]=2 |
收尾时hash[0..3]全为 0，返回hash[4] = 2✅，与题目示例一致。
三、正确性说明（简单版本）
- 状态语义精确：
hash[i]表示"已经叫到第 i 个字母、正在等待下一个字母"的青蛙数；每处理一个字符都做一次合法转移（前者减、当前加），总数守恒（除c新建时增一只）。 - 合法性判定完备：非
c的字符若找不到前驱状态（hash[index[ch]-1] == 0），说明此前没有青蛙叫到它前一个字母，顺序必然违规，返回-1正确；收尾时若有青蛙卡在半途（hash[0..3] != 0），说明叫声未完成，同样返回-1。 - 贪心复用最优：同一时刻至多一只青蛙能叫某个特定字母（因为每只青蛙同一时刻只能处在一个状态）。遇
c时复用已完成的青蛙，既满足约束又不增加并行需求；而hash[4]记录的是"历史上同时并行的最大值"——它由字符串本身的交错结构决定，贪心复用使这一数值达到理论下界（最少）。 - 答案即最少：
hash[4]等价于"任意时刻同时处于活跃状态的青蛙数的最大值"，即所需青蛙数的最优解，不可能更少。
📌 例子：为什么hash[index[ch]-1] == 0就必然非法
croakOfFrogs = "cro"（不完整）已在收尾检查中返回 -1；再看"croakroak"中以r开头的情形"rcroak"：第一个字符是r，此时hash[index['r']-1] = hash[0] = 0（没有青蛙叫过c），无法为r找到前驱，立即返回-1✅——"前驱状态为空"精确捕获了顺序违规。
四、实现细节（边界防护）
- 初始化：
hash[5] = {0}、index映射"croak"的下标、t = "croak"。 - 边界防护：遍历前无需特判空串（空串遍历不进入，收尾全 0，返回
hash[4] = 0，符合"0 只青蛙"的语义）；非cr/o/a合法字符（题目保证只含这五种）中途异常由hash[前驱] == 0兜住并返回 -1；收尾检查只查0~3（k对应的 4 允许非 0，表示已叫完的青蛙）。 - 复杂度：时间 O(n)（单次遍历 + O(5) 收尾检查），空间 O(1)（
hash[5]与固定映射表）。 - 关键操作：
index[t[j]] = j;（字母→下标映射）、if (hash[index['k']] != 0) { hash[index['k']]--; hash[index['c']]++; }（复用已完成的青蛙）、if (hash[index[ch] - 1] != 0) {...} else return -1;（状态转移与合法性判定）、for (i = 0; i < 4; i++) if (hash[i] != 0) return -1;（收尾完整性检查）。
📌 例子：收尾检查为什么只查 0~3
croakOfFrogs = "croak"：结束时hash = {0,0,0,0,1}，hash[4] = 1（一只青蛙叫完了，这是正常完成状态，不能算失败）；若查i <= 4并要求全 0，就会把这个唯一合法情形误判为 -1。反之croakOfFrogs = "croa"：结束时hash = {0,0,0,1,0}，hash[3] = 1 ≠ 0（有青蛙卡在a）→ 返回 -1 ✅——只查 0~3 恰好区分"完成"与"半途"。
五、返回值（目标映射）
- 返回
hash[4]：所需的最少青蛙数（同时并行的青蛙数量）；若中途顺序违规或收尾未完成，返回-1，对应题目"不能形成则返回 -1"。
三.代码
class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { int hash[5] = { 0 }; // hash[i] = 当前叫到第 i 个字母的青蛙数 unordered_map<char, int> index; // 字符 -> 它在 "croak" 中的下标 string t = "croak"; // 1. 建立映射：c->0, r->1, o->2, a->3, k->4 for (int j = 0; j < t.size(); j++) { index[t[j]] = j; } int n = croakOfFrogs.size(); // 2. 遍历每个字符，做一次状态转移 for (const auto& ch : croakOfFrogs) { if (ch == 'c') { // 遇 'c'：优先复用已经叫完的青蛙，否则新派一只 if (hash[index['k']] != 0) { hash[index['k']]--; // 已完成的青蛙重新投入工作 hash[index['c']]++; } else { hash[index['c']]++; // 没有空闲青蛙，新增一只 } } else { // 其余字母：必须有“刚叫完前一个字母”的青蛙来接 if (hash[index[ch] - 1] != 0) { hash[index[ch] - 1]--; // 前驱状态出队 hash[index[ch]]++; // 当前状态入队 } else { return -1; // 前驱状态为空：顺序违规 } } } // 3. 收尾检查：不能有青蛙卡在半途（只查 0~3，k 允许非 0） for (int i = 0; i < 4; i++) { if (hash[i] != 0) { return -1; } } return hash[4]; // 4. 返回叫完 k 的青蛙数 = 最少青蛙数 } };四、易错点分析
难点1：hash[i]的状态语义必须厘清
int hash[5] = { 0 }; // hash[i]：叫到第 i 个字母的青蛙数
hash[0]是"已叫完c、正等r"的青蛙数，而不是"总共派出的青蛙数"。理解这一点才能看懂转移逻辑：遇r时是hash[0]--; hash[1]++（前驱出、当前入），而不是简单地"给r加一"。把hash误当成"各字母出现次数统计"会导致完全错误的实现（那样无法判断顺序合法性）。
难点2：c必须优先复用hash[4]（贪心关键）
if (hash[index['k']] != 0) { hash[index['k']]--; hash[index['c']]++; } else { hash[index['c']]++; }遇
c时若已有叫完（hash[4] != 0）的青蛙，必须让它重新开始，而不是新派。这既符合"一只青蛙可以连续叫多轮"的题意，也保证hash[4]最终等于"同时并行的青蛙数最大值"（即最小值）。若每次c都新增，hash[4]会变成"总叫声轮数"，答案偏大——这里的贪心不是可选项，而是答案正确性的前提。
难点3：非c字符找不到前驱必须立即返回 -1
if (hash[index[ch] - 1] != 0) { ... } else { return -1; }以
r为例，它必须由"刚叫完c"的青蛙接续。若hash[0] == 0，说明此前没有任何青蛙叫到c，r无从上承，整串必然无法拆分成合法croak——立即返回 -1（而非等到收尾）。同理o需要hash[1]、a需要hash[2]、k需要hash[3]。"前驱为空即非法"是本题正确性的第一道闸门。
难点4：收尾检查只能查0~3，不能查4
for (int i = 0; i < 4; i++) // 注意是 i < 4，不是 i < 5遍历结束后，处于半途（
hash[0..3] != 0）说明有青蛙没叫完，非法；而hash[4]（已叫完的青蛙）允许非 0，它正是答案本身。若收尾写成i < 5并把hash[4] != 0也当失败，那么唯一合法输入"croak"会被误判为 -1——这是本题最容易写错的收尾边界。
五、流程图
🎯 闭幕
🎉 恭喜你完成了「数青蛙」问题的学习！
为了巩固知识并进一步拓展，建议你：
🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。
💡深入思考
代码中遇到
'c'时，会先检查hash[index['k']]是否非零，优先复用已经叫完'k'的青蛙。为什么这样能保证青蛙数量最少？如果每次遇到'c'都新建一只青蛙，结果会怎样？hash[i]表示当前处于第i个字母阶段的青蛙数量。为什么最后只检查hash[0] ~ hash[3]是否为 0，而不检查hash[4]？如果hash[4]非零，它代表什么？对于非
'c'字母，代码要求hash[index[ch] - 1] != 0才能转移。为什么必须保证前驱状态存在？如果前驱状态为 0，直接返回-1，这避免了什么错误？
如果你觉得本文对你有所帮助，欢迎：
👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路
📌深入思考答案
优先复用已完成
'k'的青蛙，是因为这些青蛙已经叫完一轮，可以立即投入下一轮，避免新增青蛙。若每次都新建，则最终青蛙数量会等于'c'的总数，远大于实际所需，无法得到最少数量。hash[0]~hash[3]分别表示叫到'c','r','o','a'的青蛙数。最后必须全部为 0，否则说明有青蛙卡在半途，叫声不完整，应返回-1。hash[4]表示叫完'k'的青蛙数，它们可以继续复用，因此允许非零，最终返回hash[4]即为最少青蛙数。非
'c'字母必须由前驱状态的青蛙接续。如果前驱状态为 0，说明当前字母没有合法的前序，叫声顺序违规，直接返回-1可及时终止并保证正确性。
祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨
