[算法】模拟：（leetcode）1419.数青蛙(medium)
本篇使用c++
目录
1、题目链接
2、题目介绍
3、思路分析
问题分析
解题思路
4、代码
💗感谢阅读！💗
1、题目链接
1419. 数青蛙 - 力扣（LeetCode）
2、题目介绍
给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 “croak” ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
注意：要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。
如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。
示例 1：
输入：croakOfFrogs = "croakcroak"
输出：1
解释：一只青蛙 “呱呱” 两次
示例 2：
输入：croakOfFrogs = "crcoakroak"
输出：2
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"
示例 3：
输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。
示例 4：输入：croakOfFrogs = "croakcroa"
输出：-1
提示：
1 <= croakOfFrogs.length <= 10^5
字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'
3、思路分析
问题分析
如果字符串中的字符
- 不是这些字符的有效组合，
- 或者字符的顺序不正确，
那么该字符串就不是有效的蛙鸣声组合。
解题思路
检查字符串长度：首先，检查输入字符串
croakOfFrogs的长度是否是 5 的倍数。因为每个 "croak" 包含 5 个字符，所以如果不是 5 的倍数，则无法构成有效的蛙鸣声组合，直接返回 -1。初始化变量：
- 使用一个长度为 5 的数组
hash来记录每个字符（'c', 'r', 'o', 'a', 'k'）在字符串中出现的次数。- 使用变量
res来记录模拟字符串中所有蛙鸣所需的不同青蛙的最少数目，初始化为 0。- 使用变量
now来表示当前正在发出蛙鸣声但尚未完成的青蛙数量，初始化为 0。遍历字符串：
- 遍历字符串
croakOfFrogs中的每个字符。- 如果遇到字符 'c'，表示有一只新的青蛙开始发出蛙鸣声，将
hash[0]和now分别增加 1，并更新res为max(res, now)，因为可能出现了新的同时发声的青蛙。- 如果遇到字符 'r', 'o', 'a'，则只将对应位置的
hash值增加 1，不改变now或res的值。同时，检查这些字符的数量是否满足顺序要求（即后面的字符数量不应超过前面的字符数量），如果不满足，则返回 -1。- 如果遇到字符 'k'，表示一只青蛙完成了它的蛙鸣声，将
hash[4]增加 1，并将now减少 1。这表示有一只青蛙完成了叫声，不再占用发声位置。检查结束条件：
- 遍历结束后，检查
now是否为 0。如果不为 0，说明有青蛙开始了叫声但没有完成，这表示字符串不是有效的蛙鸣声组合，返回 -1。- 如果
now为 0，且没有在其他地方返回 -1，则说明字符串是有效的蛙鸣声组合，返回res作为结果。
4、代码
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
//限制条件：字符串长度不满足5倍数，
if (croakOfFrogs.size() % 5 != 0)
return -1;
int hash[5] = { 0 };//哈希记录croak字符出现次数
int res = 0; //记录模拟字符串中所有蛙鸣所需的不同青蛙的最少数目
int now = 0;//表示当前正在发出蛙鸣声，但尚未完成的青蛙数量（动态变化）
for (int i = 0; i < croakOfFrogs.size(); i++)
{
//crcoakroak
//hash 0 1 2 3 4
// 2 2 2 2 2
//res 2
//now 1
if (croakOfFrogs[i] == 'c')
{
hash[0]++;
now++;
res = max(res, now);
}
else if (croakOfFrogs[i] == 'r')
{
hash[1]++;
}
else if (croakOfFrogs[i] == 'o')
{
hash[2]++;
}
else if (croakOfFrogs[i] == 'a')
{
hash[3]++;
}
else
{
hash[4]++;
now--;
}
if (!(hash[0] >= hash[1] && hash[1] >= hash[2] && hash[2] >= hash[3] && hash[3] >= hash[4]))
{
return -1;
}
}
//全部遍历完毕，但是还有青蛙没有完全发出croak，因此不符合条件
if (now != 0) return -1;
return res;
}
};