数青蛙Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个字符串 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" 的有效组合。
提示：
- 1 <= croakOfFrogs.length <= 105
- 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'
# 思路
换一种思路：我们记录当前能叫出某一个字符的青蛙的数量。
# 解法
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
int[] cnt=new int[128];//当前可以叫出第i个字符的青蛙有几只？
int all=0;//当前总共有all只青蛙
int[] nexts=new int[128];//字符到下一个字符下标的映射
nexts['c']='r';
nexts['r']='o';
nexts['o']='a';
nexts['a']='k';
nexts['k']='c';
for(char c:croakOfFrogs.toCharArray()){
if(cnt[c]==0){
if(c!='c') return -1;//如果没有青蛙能叫出这声，那么此时只能是'c'要叫
all++;//增加一只青蛙
cnt['c']++;//能叫出'c'的青蛙增加一只
}
cnt[c]--;
cnt[nexts[c]]++;
}
return all==cnt['c']?all:-1;//all==cnt['c']说明青蛙都叫完了
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 总结
- 分析出几种情况，然后分别对各个情况实现
