【优选算法必刷100题】第43题（模拟）：数青蛙

🔥个人主页：Cx330🌸

❄️个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》《C++知识分享》

《优选算法指南-必刷经典100题》《Linux操作系统》:从入门到入魔

《Git深度解析》:版本管理实战全解

🌟心向往之行必能至

🎥Cx330🌸的简介：

前言：

聚焦算法题实战，系统讲解三大核心板块：“精准定位最优解”——优选算法，“简化逻辑表达，系统性探索与剪枝优化”——递归与回溯，“以局部最优换全局高效”——贪心算法，讲解思路与代码实现，帮助大家快速提升代码能力

43. 数青蛙

题目链接：

1419. 数青蛙 - 力扣（LeetCode）

题目描述：

题目示例：

算法原理（模拟）：

思路：

• 当遇到'r' 'o' 'a' 'k'这四个字符的时候，我们要去看看每一个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那么就让这个青蛙接下来喊出这个字符；如果没有，直接返回-1；
• 当遇到 ‘c’ 这个字符的时候，我们去看看 ‘k’ 这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去 ‘c’ 这个字符；如果没有的话，就重新整一个青蛙出来

模拟解法代码（C++）：

class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { string t="croak"; int n=t.size(); vector<int> hash(n);//用数组来模拟哈希 unordered_map<char,int> index;//【x,x字符对应的下标】 for(int i=0;i<n;i++) index[t[i]]=i; for(auto ch:croakOfFrogs) { if(ch=='c') { if(hash[n-1]!=0) hash[n-1]--; hash[0]++; } else { int i=index[ch]; if(hash[i-1]==0) return -1; hash[i-1]--;hash[i]++; } } for(int i=0;i<n-1;i++) if(hash[i]!=0) return -1; return hash[n-1]; } };

博主手记（字体还请见谅哈）：

结尾：

总结：算法核心是追踪"croak"序列的完成状态：遇到'c'时检查是否有完成叫声的青蛙可复用，否则新增青蛙；遇到其他字符时检查前驱字符是否存在。使用哈希表记录字符位置，数组跟踪各阶段叫声数量。若最终中间状态不为零或无法匹配前驱字符则返回-1