数青蛙【LC1419】
给你一个字符串
croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串"croak"）的组合。由于同一时间可以有多只青蛙呱呱作响，所以croakOfFrogs中会混合多个“croak”。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
要想发出蛙鸣 “croak”，青蛙必须 依序 输出
‘c’, ’r’, ’o’, ’a’, ’k’这 5 个字母。
如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。
思路
记录每个字符出现的个数、剩余c的个数
- 如果字符串由若干有效的
croak组成，那么字符c个数应大于等于字符r，字符r个数应大于等于字符o，字符o个数应大于等于字符a，字符a个数应大于等于字符k，如果不满足以上任意情况返回-1
- 如果当前字符为k，那么表示有一个完整的
croak，此时剩余c的个数减1，如果遍历结束仍有字符c剩余，返回-1 - 那么青蛙的最少数目即为最大的剩余c的个数
- 实现
class Solution { public int minNumberOfFrogs(String croakOfFrogs) { int n = croakOfFrogs.length(); Map<Character, Integer> counts = new HashMap<>(); int cur = 0; int res = 0; for (int i = 0; i < n; i++){ char c = croakOfFrogs.charAt(i); counts.put(c, counts.getOrDefault(c, 0) + 1); if (c == 'c'){ cur++; res = Math.max(res, cur); }else if (c == 'k'){ cur--; } if(counts.getOrDefault('r', 0) > counts.getOrDefault('c', 0) || counts.getOrDefault('o', 0) > counts.getOrDefault('r', 0) ||counts.getOrDefault('a', 0) > counts.getOrDefault('o', 0) || counts.getOrDefault('k', 0) > counts.getOrDefault('a', 0)){ return -1; } } if (cur != 0) return -1; return res; } }
