LEETCODE 1419. 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" 的有效组合。

示例 4:

输入:croakOfFrogs = "croakcroa"
输出:-1

提示:

  • 1 <= croakOfFrogs.length <= 10^5
  • 字符串中的字符只有 'c''r''o''a' 或者 'k'

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1419

解题思路分析:

这道题有些类似之前做过的一道安排会议室的题目。本题中,当一只青蛙发出c-r-o-a-k叫声的过程中,出现了另外的叫声,那么这肯定不是当前青蛙发出的声音。我们统计一下最多同时出声的青蛙数量,即是本题的解。

解题时,我们定义4个变量,分别代表,当前发出c,r,o,a的声音数量,另外在维护一个count,保存当前同时发出叫声的青蛙数量,最后再使用一个maxCount来统计最多的同时发声的数量。接下来循环遍历字符串,如果当前字符是c,代表一个新的蛙叫声开始,count加一,同时c加一,另外要使用当前count去更新全局maxCount。如果当前字符是r,首先查看c的数量(没有c哪来的r),如果c的数量是0,代表这是一个不合理的叫声,直接返回-1。反之,c的数量减一,当前r的数量加一。如果当前字符是r,o,a或者k,处理方式与r相似。唯一不同的是,当前字符为k时,代表一个完整的蛙叫声已经结束,count应该减一。

实现代码:

public int minNumberOfFrogs(String croakOfFrogs) {
    // 如果字符串长度不能被5整除,那么肯定无法得到正确的解
    if(croakOfFrogs.length() % 5 !=0) return -1;
    // 当前发出c,r,o,a叫声的数量
    int c=0,r=0,o=0,a=0;
    // 当前同时发声的青蛙数量
    int currentCount=0;
    // 最大同时发出声音的青蛙数量(返回结果)
    int maxCount=0;
    for(int i=0;i<croakOfFrogs.length();i++){
        // 当前字符
        char ch = croakOfFrogs.charAt(i);
        switch(ch){
            case 'c': // 当前字符是c
                c++; // 当前c的叫声加一
                currentCount++; // 发声的青蛙数量加一
                // 更新全局最大数量
                maxCount=Math.max(maxCount,currentCount);
                break;
            case 'r': // 当前字符是r
                if(c==0) return -1;
                c--;
                r++;
                break;
            case 'o':
                if(r==0) return -1;
                r--;
                o++;
                break;
            case 'a':
                if(o==0) return -1;
                o--;
                a++;
                break;
            case 'k':
                if(a==0) return -1;
                a--;
                currentCount--;
                break;
        }
    }
    return maxCount;
}

本题解法执行时间为7ms。

Runtime: 7 ms, faster than 92.97% of Java online submissions for Minimum Number of Frogs Croaking.

Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Minimum Number of Frogs Croaking.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1419-minimum-number-of-frogs-croaking-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。