1419.数青蛙

【LetMeFly】1419.数青蛙

力扣题目链接：https://leetcode.cn/problems/minimum-number-of-frogs-croaking/

给你一个字符串 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'

方法一：计数 + 模拟

题目大意是每只青蛙依次叫完“c、r、o、a、k”算作一次发声，一只青蛙完整叫完这一次后可以叫下一次，但是不能只叫一半。问最少有多少只青蛙在叫。

我们只需要一个计数器“cnt”，分别统计当前叫到“c、r、o、a、k”的青蛙数量。

接着还需要一个变量“nowFrog”来统计当前正在叫且还没有叫完的青蛙的数量。答案用变量“ans”来表示。

遍历发生字符串：

• 如果当前字符是“c”，那么就说明这个声音来自某一只青蛙的开始，$nowFrog++$，并更新答案（同时发声的最大青蛙数量）和cnt

• 否则，这个声音来自某只叫了一半的青蛙，假如这一声是“o”，那么就需要由一只“r”青蛙改叫“o”

  • 如果“r”青蛙数量为0，直接返回-1
  • 否则cnt[r]–，cnt[o]++
    注意查看这一声是否为最后一声“k”，如果为k，则说明某只青蛙叫完了，nowFrog–，cnt[o]–（其实cnt[0]可以恒为0）

• 时间复杂度$O(len(croakOfFrogs))$

• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        unordered_map<char, int> ma = {{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}};
        int cnt[5] = {0};
        int nowFrog = 0;
        int ans = 0;
        for (char c : croakOfFrogs) {
            int th = ma[c];
            if (th == 0) {  // 新青蛙
                nowFrog++;
                ans = max(ans, nowFrog);
                cnt[0]++;
            }
            else {  // 老青蛙
                if (!cnt[th - 1]) {
                    return -1;
                }
                cnt[th - 1]--;
                if (th == 4) {  // 这个青蛙叫完了
                    nowFrog--;
                }
                else {
                    cnt[th]++;
                }
            }
        }
        return nowFrog ? -1 : ans;
    }
};

Python

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        ma = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}
        cnt = [0] * 5
        nowFrog = 0
        ans = 0
        for c in croakOfFrogs:
            th = ma[c]
            if not th:  # 新青蛙
                nowFrog += 1
                ans = max(ans, nowFrog)
                cnt[0] += 1
            else:  # 老青蛙
                if not cnt[th - 1]:
                    return -1
                cnt[th - 1] -= 1
                if th == 4:  # 这个青蛙叫完了
                    nowFrog -= 1
                else:
                    cnt[th] += 1
        return ans if not nowFrog else -1

Java

🔥 感谢 @水大佬 提供Java版本的代码~

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        if(croakOfFrogs.length()%5!=0){
            return -1;
        }
        HashMap<Character,Integer> map=new HashMap<>();
        map.put('c',0);
        map.put('r',1);
        map.put('o',2);
        map.put('a',3);
        map.put('k',4);
        int frog=0;
        int maxfrog=0;
        int[] count=new int[5];
        for(char now:croakOfFrogs.toCharArray()){
            int croak=map.get(now);
            if(now=='c'){
                frog++;
                count[0]++;
                maxfrog=Math.max(frog,maxfrog);
            }else{
                if(count[croak-1]==0){
                return -1;
                }
                count[croak-1]--;
                if(now=='k'){
                    frog--;
                }else{
                    count[croak]++;
                }
            }
        }
        if(frog>0){
            return -1;
        }
        return maxfrog;
    }
}

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/130520908