《算法闯关指南：优选算法--模拟》--43.数青蛙

🔥草莓熊Lotso：个人主页
❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受！

🎬 博主简介：

文章目录

• 前言：
• 43. 数青蛙
  • 解法（模拟+分情况讨论）：
    • 算法思路：
  • C++算法代码：
  • 算法总结&&笔记展示：
• 结尾：

前言：

聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。

43. 数青蛙

题目链接：

1419. 数青蛙 - 力扣（LeetCode）

题目描述：

题目示例：

解法（模拟+分情况讨论）：

算法思路：

模拟青蛙的叫声。

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

C++算法代码：

classSolution{public:intminNumberOfFrogs(string croakOfFrogs){ string s="croak";int n=s.size(); unordered_map<char,int> index;//记录字符映射下标关系 vector<int>hash(n);//数组模拟哈希表for(int i=0;i<n;i++) index[s[i]]=i;for(auto& ch:croakOfFrogs){if(ch=='c'){if(hash[n-1]!=0) hash[n-1]--; hash[0]++;}else{int t=index[ch];if(hash[t-1]==0)return-1; hash[t-1]--,hash[t]++;}}for(int i=0;i<n-1;i++)if(hash[i]!=0)return-1;return hash[n-1];}};

算法总结&&笔记展示：

笔记字有点丑，大家见谅：

结尾：

🍓 我是草莓熊 Lotso！若这篇技术干货帮你打通了学习中的卡点： 👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长 ❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量 ⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用 💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑 🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解 技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！ 

结语：本文探讨了LeetCode 1419题"数青蛙"的解法，通过模拟青蛙叫声过程，分析字符序列croak的匹配逻辑。算法使用哈希表记录字符位置，并动态维护各阶段字符计数：当遇到c时复用已完成k的青蛙或新增青蛙；其他字符则需前驱字符存在才能继续。最后检查未完成序列的青蛙数量。解法高效且思路清晰。

✨把这些内容吃透超牛的！放松下吧✨ʕ˘ᴥ˘ʔづきらど