【算法系列】leetcode1419 数青蛙 --模拟

一、题目

二、思路

模拟⻘蛙的叫声。
当遇到 'r' 'o' 'a' 'k' 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，有没有⻘蛙叫出来。如果有⻘蛙叫出来，那就让这个⻘蛙接下来喊出来这个字符；如果没有则为异常字符串，直接返回 -1 
当遇到'c'这个字符的时候，我们去看看'k'这个字符有没有⻘蛙叫出来。如果有，就让
这个⻘蛙继续去喊'c'这个字符；如果没有的话，就⻘蛙数加1。

三、代码

我的版本

#include <unordered_map>
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string str="croak";unordered_map<char,int> index;int len=str.size();vector<int> cnt(5,0);for(int i=0;i<len;++i)index[str[i]]=i;for(auto e:croakOfFrogs){   if(e=='c'){if(cnt[len-1]!=0) cnt[len-1]--;  cnt[0]++;}else{if(cnt[index[e]-1]==0)return -1;cnt[index[e]-1]--;cnt[index[e]]++;}}for(int i=0;i<len-1;++i){if(cnt[i]!=0)return -1;}return cnt[len-1];}
};

deepseek深度学习版本：

#include <unordered_map>
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {// 定义字符到阶段的映射unordered_map<char, int> charToIdx = {{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}};vector<int> counts(5, 0); // 分别代表c, r, o, a, k阶段的青蛙数目int maxFrogs = 0;for (char ch : croakOfFrogs) {// 检查字符是否有效if (charToIdx.find(ch) == charToIdx.end()) {return -1;}int idx = charToIdx[ch];if (idx == 0) {// 处理字符c，优先复用k阶段的青蛙if (counts[4] > 0) {counts[4]--;counts[0]++;} else {counts[0]++;}} else {// 处理其他字符，需要前一个阶段有青蛙int prev = idx - 1;if (counts[prev] == 0) {return -1;}counts[prev]--;counts[idx]++;}// 计算当前活跃的青蛙数目int currentSum = counts[0] + counts[1] + counts[2] + counts[3] + counts[4];maxFrogs = max(maxFrogs, currentSum);}// 检查所有非k阶段的数目是否为0for (int i = 0; i < 4; i++) {if (counts[i] != 0) {return -1;}}return maxFrogs;}
};