class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
}
};
1419. 数青蛙
给你一个字符串 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'原站题解
java 解法, 执行用时: 16 ms, 内存消耗: 42.9 MB, 提交时间: 2023-05-06 10:28:54
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
if (croakOfFrogs.length() % 5 != 0) {
return -1;
}
int res = 0, frogNum = 0;
int[] cnt = new int[4];
Map<Character, Integer> map = new HashMap<Character, Integer>() {{
put('c', 0);
put('r', 1);
put('o', 2);
put('a', 3);
put('k', 4);
}};
for (int i = 0; i < croakOfFrogs.length(); i++) {
char c = croakOfFrogs.charAt(i);
int t = map.get(c);
if (t == 0) {
cnt[t]++;
frogNum++;
if (frogNum > res) {
res = frogNum;
}
} else {
if (cnt[t - 1] == 0) {
return -1;
}
cnt[t - 1]--;
if (t == 4) {
frogNum--;
} else {
cnt[t]++;
}
}
}
if (frogNum > 0) {
return -1;
}
return res;
}
}
python3 解法, 执行用时: 144 ms, 内存消耗: 16.3 MB, 提交时间: 2023-05-06 10:28:35
class Solution:
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
if len(croakOfFrogs) % 5:
return -1
res, frog_num = 0, 0
cnt = [0] * 4
mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}
for c in croakOfFrogs:
t = mp[c]
if t == 0:
cnt[t] += 1
frog_num += 1
if frog_num > res:
res = frog_num
else:
if cnt[t - 1] == 0:
return -1
cnt[t - 1] -= 1
if t == 4:
frog_num -= 1
else:
cnt[t] += 1
if frog_num > 0:
return -1
return res
golang 解法, 执行用时: 4 ms, 内存消耗: 4.1 MB, 提交时间: 2023-05-06 10:28:08
// 每个字母在 "croak" 中的上一个字母
var previous = [...]int{'c': 'k', 'r': 'c', 'o': 'r', 'a': 'o', 'k': 'a'}
func minNumberOfFrogs(croakOfFrogs string) int {
cnt := [len(previous)]int{}
for _, ch := range croakOfFrogs {
pre := previous[ch] // pre 为 ch 在 "croak" 中的上一个字母
if cnt[pre] > 0 { // 如果有青蛙发出了 pre 的声音
cnt[pre]-- // 复用一只
} else if ch != 'c' { // 否则青蛙必须从 'c' 开始蛙鸣
return -1 // 不符合要求
}
cnt[ch]++ // 发出了 ch 的声音
}
if cnt['c'] > 0 || cnt['r'] > 0 || cnt['o'] > 0 || cnt['a'] > 0 {
return -1 // 有发出其它声音的青蛙，不符合要求
}
return cnt['k'] // 最后青蛙们都发出了 'k' 的声音
}
java 解法, 执行用时: 4 ms, 内存消耗: 42.7 MB, 提交时间: 2023-05-06 10:27:53
class Solution {
// 数组比哈希表快。's' 保证 "croak" 中的任意字符都不会越界
private static final char[] PREVIOUS = new char['s'];
static { // 预处理每个字母在 "croak" 中的上一个字母
var s = "croakc".toCharArray();
for (int i = 1; i < s.length; i++)
PREVIOUS[s[i]] = s[i - 1];
}
public int minNumberOfFrogs(String croakOfFrogs) {
var cnt = new int['s'];
for (var ch : croakOfFrogs.toCharArray()) {
var pre = PREVIOUS[ch]; // pre 为 ch 在 "croak" 中的上一个字母
if (cnt[pre] > 0) // 如果有青蛙发出了 pre 的声音
cnt[pre]--; // 复用一只
else if (ch != 'c') // 否则青蛙必须从 'c' 开始蛙鸣
return -1; // 不符合要求
cnt[ch]++; // 发出了 ch 的声音
}
if (cnt['c'] > 0 || cnt['r'] > 0 || cnt['o'] > 0 || cnt['a'] > 0)
return -1; // 有发出其它声音的青蛙，不符合要求
return cnt['k']; // 最后青蛙们都发出了 'k' 的声音
}
}
python3 解法, 执行用时: 200 ms, 内存消耗: 16.5 MB, 提交时间: 2023-05-06 10:27:40
# 预处理每个字母在 "croak" 中的上一个字母
PREVIOUS = dict(pairwise("croakc"[::-1]))
class Solution:
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
cnt = Counter()
for ch in croakOfFrogs:
pre = PREVIOUS[ch] # pre 为 ch 在 "croak" 中的上一个字母
if cnt[pre]: # 如果有青蛙发出了 pre 的声音
cnt[pre] -= 1 # 复用一只
elif ch != 'c': # 否则青蛙必须从 'c' 开始蛙鸣
return -1 # 不符合要求
cnt[ch] += 1 # 发出了 ch 的声音
if any(cnt[ch] for ch in "croa"):
return -1 # 有发出其它声音的青蛙，不符合要求
return cnt['k'] # 最后青蛙们都发出了 'k' 的声音