LEETCODE算法:5390. Minimum Number of Frogs Croaking

发表于 更新于 分类于 Waline： 阅读次数：

题目

Given the string croakOfFrogs, which represents a combination of the string "croak" from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid "croak" means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid "croak" return -1.

Example 1:

Input: croakOfFrogs = "croakcroak" Output: 1 Explanation: One frog yelling "croak" twice. Example 2:

Input: croakOfFrogs = "crcoakroak" Output: 2 Explanation: The minimum number of frogs is two. The first frog could yell "crcoakroak". The second frog could yell later "crcoakroak". Example 3:

Input: croakOfFrogs = "croakcrook" Output: -1 Explanation: The given string is an invalid combination of "croak" from different frogs. Example 4:

Input: croakOfFrogs = "croakcroa" Output: -1

Constraints:

1 <= croakOfFrogs.length <= 10^5 All characters in the string are: 'c', 'r', 'o', 'a' or 'k'.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//逐一统计字符串中croak各个字母数量，因为一个青蛙叫只能按顺序的叫出croak，所有如果出现后一个字母出现的次数大于前面的字母，肯定不对返回-1
//当遇到k的时候，说明有一只青蛙叫完了，可以重新开始叫，所以croak每个字母都减1
//答案为当前ans和c-k的最大值，c相当于有几只青蛙正在叫，k相当于几只已经叫过了，差值就是当前需要的最少的青蛙数
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int c=0,r=0,o=0,a=0,k=0;
        int ans=0,tmp=0;
        for(auto t:croakOfFrogs)
        {
            if(t=='c') c++;
            else if(t=='r') r++;
            else if(t=='o') o++;
            else if(t=='a') a++;
            else if(t=='k') k++;
            else return -1;
            if(r>c||o>r||a>o||k>a) return -1;
            ans=max(ans,c-k);
            if(t=='k')
            {
                c--;r--;o--;a--;k--;
            }
        }
        if(c) return -1;
        return ans;
    }
};