欢迎阅读 欢迎来到「数青蛙」题解之旅本文将带你从安排一群青蛙接力叫出 croak这一趣味场景出发深入理解状态机 贪心复用的巧妙运用并掌握如何用计数数组追踪每只青蛙的进度来求出所需青蛙的最少数量。在开始之前建议你先了解题目背景这是 LeetCode 1419 题给定由c/r/o/a/k组成的字符串判断能否由若干只青蛙交替叫出完整的croak每只青蛙必须按顺序叫完五个字母能则返回最少青蛙数不能返回-1。本质上问题转化为为每个字符分配一只处于正确阶段的青蛙。明确学习目标掌握状态计数hash[i] 表示叫到第 i 个字母的青蛙数的建模方式理解优先复用已叫完的青蛙的贪心策略并熟练处理字母顺序违规与叫声未完成两类失败情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如croakOfFrogs croakcroak输出1croakOfFrogs 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~4index[c]0, ..., index[k]4。hash[5]初始化全 0hash[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,0A 叫 rc无已完成的新派1,1,0,0,0青蛙 B 开始o由 r 接1,0,1,0,0A 叫 oa由 o 接1,0,0,1,0A 叫 ak由 a 接1,0,0,0,1A 叫完hash[4]1r由 c 接0,1,0,0,1B 叫 ro由 r 接0,0,1,0,1B 叫 oa由 o 接0,0,0,1,1B 叫 ak由 a 接0,0,0,0,2B 叫完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~3k对应的 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~3croakOfFrogs 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_mapchar, 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~3k 允许非 0 for (int i 0; i 4; i) { if (hash[i] ! 0) { return -1; } } return hash[4]; // 4. 返回叫完 k 的青蛙数 最少青蛙数 } };四、易错点分析难点1hash[i]的状态语义必须厘清int hash[5] { 0 }; // hash[i]叫到第 i 个字母的青蛙数hash[0]是已叫完c、正等r的青蛙数而不是总共派出的青蛙数。理解这一点才能看懂转移逻辑遇r时是hash[0]--; hash[1]前驱出、当前入而不是简单地给r加一。把hash误当成各字母出现次数统计会导致完全错误的实现那样无法判断顺序合法性。难点2c必须优先复用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字符找不到前驱必须立即返回 -1if (hash[index[ch] - 1] ! 0) { ... } else { return -1; }以r为例它必须由刚叫完c的青蛙接续。若hash[0] 0说明此前没有任何青蛙叫到cr无从上承整串必然无法拆分成合法croak——立即返回 -1而非等到收尾。同理o需要hash[1]、a需要hash[2]、k需要hash[3]。前驱为空即非法是本题正确性的第一道闸门。难点4收尾检查只能查0~3不能查4for (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可及时终止并保证正确性。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨