| comments | difficulty | edit_url | rating | source | tags | ||
|---|---|---|---|---|---|---|---|
true |
中等 |
1689 |
第 185 场周赛 Q3 |
|
给你一个字符串 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'
我们注意到，如果字符串 croakOfFrogs 是由若干有效的 "croak" 字符混合而成，那么它的长度一定是
接下来，我们将 'c', 'r', 'o', 'a', 'k' 这 croakOfFrogs 中每个字母出现的次数，其中
我们遍历字符串 croakOfFrogs 中的每个字母
- 如果
$i=0$ ，那么当前有一个新的青蛙开始蛙鸣，因此令$x$ 的值加$1$ ，然后我们更新$ans = \max(ans, x)$ ； - 否则，如果
$cnt[i-1]=0$ ，那么表示当前没有青蛙可以发出字母$c$ ，无法完成蛙鸣，返回$-1$ ，否则我们令$cnt[i-1]$ 减$1$ 。如果$i=4$ ，那么表示青蛙已经完成了一个蛙鸣，因此令$x$ 的值减$1$ 。
遍历结束后，如果
时间复杂度 croakOfFrogs 的长度；而
class Solution:
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
if len(croakOfFrogs) % 5 != 0:
return -1
idx = {c: i for i, c in enumerate('croak')}
cnt = [0] * 5
ans = x = 0
for i in map(idx.get, croakOfFrogs):
cnt[i] += 1
if i == 0:
x += 1
ans = max(ans, x)
else:
if cnt[i - 1] == 0:
return -1
cnt[i - 1] -= 1
if i == 4:
x -= 1
return -1 if x else ansclass Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
int n = croakOfFrogs.length();
if (n % 5 != 0) {
return -1;
}
int[] idx = new int[26];
String s = "croak";
for (int i = 0; i < 5; ++i) {
idx[s.charAt(i) - 'a'] = i;
}
int[] cnt = new int[5];
int ans = 0, x = 0;
for (int k = 0; k < n; ++k) {
int i = idx[croakOfFrogs.charAt(k) - 'a'];
++cnt[i];
if (i == 0) {
ans = Math.max(ans, ++x);
} else {
if (--cnt[i - 1] < 0) {
return -1;
}
if (i == 4) {
--x;
}
}
}
return x > 0 ? -1 : ans;
}
}class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
int n = croakOfFrogs.size();
if (n % 5 != 0) {
return -1;
}
int idx[26]{};
string s = "croak";
for (int i = 0; i < 5; ++i) {
idx[s[i] - 'a'] = i;
}
int cnt[5]{};
int ans = 0, x = 0;
for (char& c : croakOfFrogs) {
int i = idx[c - 'a'];
++cnt[i];
if (i == 0) {
ans = max(ans, ++x);
} else {
if (--cnt[i - 1] < 0) {
return -1;
}
if (i == 4) {
--x;
}
}
}
return x > 0 ? -1 : ans;
}
};func minNumberOfFrogs(croakOfFrogs string) int {
n := len(croakOfFrogs)
if n%5 != 0 {
return -1
}
idx := [26]int{}
for i, c := range "croak" {
idx[c-'a'] = i
}
cnt := [5]int{}
ans, x := 0, 0
for _, c := range croakOfFrogs {
i := idx[c-'a']
cnt[i]++
if i == 0 {
x++
ans = max(ans, x)
} else {
cnt[i-1]--
if cnt[i-1] < 0 {
return -1
}
if i == 4 {
x--
}
}
}
if x > 0 {
return -1
}
return ans
}function minNumberOfFrogs(croakOfFrogs: string): number {
const n = croakOfFrogs.length;
if (n % 5 !== 0) {
return -1;
}
const idx = (c: string): number => 'croak'.indexOf(c);
const cnt: number[] = [0, 0, 0, 0, 0];
let ans = 0;
let x = 0;
for (const c of croakOfFrogs) {
const i = idx(c);
++cnt[i];
if (i === 0) {
ans = Math.max(ans, ++x);
} else {
if (--cnt[i - 1] < 0) {
return -1;
}
if (i === 4) {
--x;
}
}
}
return x > 0 ? -1 : ans;
}