题目大意：
数青蛙
给你一个字符串 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'
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1419
解题思路分析：
这道题有些类似之前做过的一道安排会议室的题目。本题中，当一只青蛙发出c-r-o-a-k叫声的过程中，出现了另外的叫声，那么这肯定不是当前青蛙发出的声音。我们统计一下最多同时出声的青蛙数量，即是本题的解。
解题时，我们定义4个变量，分别代表，当前发出c，r，o，a的声音数量，另外在维护一个count，保存当前同时发出叫声的青蛙数量，最后再使用一个maxCount来统计最多的同时发声的数量。接下来循环遍历字符串，如果当前字符是c，代表一个新的蛙叫声开始，count加一，同时c加一，另外要使用当前count去更新全局maxCount。如果当前字符是r，首先查看c的数量（没有c哪来的r），如果c的数量是0，代表这是一个不合理的叫声，直接返回-1。反之，c的数量减一，当前r的数量加一。如果当前字符是r，o，a或者k，处理方式与r相似。唯一不同的是，当前字符为k时，代表一个完整的蛙叫声已经结束，count应该减一。
实现代码：
public int minNumberOfFrogs(String croakOfFrogs) {
// 如果字符串长度不能被5整除，那么肯定无法得到正确的解
if(croakOfFrogs.length() % 5 !=0) return -1;
// 当前发出c，r，o，a叫声的数量
int c=0,r=0,o=0,a=0;
// 当前同时发声的青蛙数量
int currentCount=0;
// 最大同时发出声音的青蛙数量（返回结果）
int maxCount=0;
for(int i=0;i<croakOfFrogs.length();i++){
// 当前字符
char ch = croakOfFrogs.charAt(i);
switch(ch){
case 'c': // 当前字符是c
c++; // 当前c的叫声加一
currentCount++; // 发声的青蛙数量加一
// 更新全局最大数量
maxCount=Math.max(maxCount,currentCount);
break;
case 'r': // 当前字符是r
if(c==0) return -1;
c--;
r++;
break;
case 'o':
if(r==0) return -1;
r--;
o++;
break;
case 'a':
if(o==0) return -1;
o--;
a++;
break;
case 'k':
if(a==0) return -1;
a--;
currentCount--;
break;
}
}
return maxCount;
}本题解法执行时间为7ms。
Runtime: 7 ms, faster than 92.97% of Java online submissions for Minimum Number of Frogs Croaking.
Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Minimum Number of Frogs Croaking.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1419-minimum-number-of-frogs-croaking-解题思路分析/