leetcode-1419

LeetCode 1419. 数青蛙

1 题目描述

• 题目链接：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” 的有效组合.

2 思路

  用一个数组vec[5]来记录croak中各个字符出现的次数，当数组vec不是单调递减时说明当前的字符串不是有效组合，直接返回false; 每一次呱呱都是以c开头，因此可以将青蛙的最少数目转化为同时在呱呱的青蛙数，而同时呱呱的青蛙数可以用一个计数器来实现，当遇到c时计数器加1，表示当前有多少只在叫，而遇到k时说明第一只开口的青蛙已经完成呱呱，此时其为空闲状态，下一个c则不用再有新的青蛙来加入。这一步操作可以通过检测当前的字符是否为k，若是则将计数器减1，从而实现在下一次检测到c的“不加入”新的青蛙的操作。而结果即为同时呱呱的青蛙数的最大值。

    class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int cnt = 0, ans = 0;
        vector<int> vec(5, 0);
        for(auto ch: croakOfFrogs){
            switch(ch){
                case 'c': 
                    vec[0]++;
                    cnt++;
                    break;
                case 'r':
                    if(vec[1] >= vec[0]) return -1;
                    vec[1]++;
                    break;
                case 'o':
                    if(vec[2] >= vec[1]) return -1;
                    vec[2]++;
                    break;
                case 'a':
                    if(vec[3] >= vec[2]) return -1;
                    vec[3]++;
                    break;
                case 'k':
                    if(vec[4] >= vec[3]) return -1;
                    cnt--;
                    vec[4]++;
                    break;
                default: return -1;
            }
            ans = max(ans, cnt);
        }
        return vec[0]==vec[4] ? ans : -1;
    }
};

  以上代码可以进行优化，减少变量数.需要注意的是，在循环末尾判断字符串是否有效时不需要判断k的值是否小于0；同样的，返回结果时也不需要判断k的值是否为0，其他字符判断次数是否为0是确保前四个被消耗完，即叫过croa后再叫k，而最后一只青蛙呱呱完前四个字符的次数为0，而k的次数应该为1.

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int res = 0;
        vector<int> vec(5, 0);
        for(auto ch: croakOfFrogs){
            switch(ch){
                case 'c': 
                    if(vec[4] > 0) vec[4]--;
                    else res++;
                    vec[0]++;
                    break;
                case 'r':
                    vec[0]--, vec[1]++;
                    break;
                case 'o':
                    vec[1]--, vec[2]++;
                    break;
                case 'a':
                    vec[2]--, vec[3]++;
                    break;
                case 'k':
                    vec[3]--, vec[4]++;
                    break;
                default: ;
            }
            if(vec[0]<0||vec[1]<0||vec[2]<0||vec[3]<0) return -1;
        }
        if(vec[0]!=0||vec[1]!=0||vec[2]!=0||vec[3]!=0) return -1;
        return res;
    }
};