力扣：1419. 数青蛙

题目：

代码：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs)
    {

        string s= "croak";
        int n=s.size();
        //首先创建一个哈希表来标明每个元素出现的次数！
        vector<int>hash(n); //不用真的创建一个hash表用一个数组模拟即可！

        //创建一个哈希表用于统计某字符的下标！因为后面需要用到某个字符前面的下标用于解题！

        unordered_map<char,int>Index;
        //将每个元素的下标映射到Index哈希表中！
        for(int i=0;i<n;i++)
        {
            Index[s[i]]=i;
        }
        //遍历给出的字符串求出最少的青蛙个数！
        for(auto ch:croakOfFrogs)
        {
            //其中c字符为一种情况!然后再把其他情况归并一起（因为他们的特性都一样！）
            //字符为c的情况！
            if(ch=='c')
            {
                if(hash[n-1]!=0)
                {
                    hash[n-1]--;
                }
                hash[0]++;
            }
            //为其他字符的情况！
            else
            {
                //求出该字符对于的下标！
                int i=Index[ch];
                if(hash[i-1]==0)
                {
                    return -1;
                }
                else
                {
                    hash[i]++;
                    hash[i-1]--;
                }
            }
        }

        //最后遍历一下哈希表！如果除了n-1的位置，其他位置有不为0的情况！直接返回-1!
        for(int i=0;i<n-1;i++)
        {
            if(hash[i]!=0)
            {
                return -1;
            }
        }
        return hash[n-1];
    }
};

算法图示：

算法思路：

通过题目的描述，需要求出最少的青蛙的个数！因为一个青蛙只有将croak全部叫完，才能重新叫！且求的是最少的青蛙的个数！所以尽可能的不让青蛙停止croak叫！叫完如果仍有新的蛙叫，首先选择让已有的青蛙继续叫，只有没有青蛙叫完的情况下，才会新增一个青蛙来进行叫！

本代码具有通用性！！！创建一个与蛙叫的字符个数相同的哈希表（其实无需真正创建哈希表，只要创建一个数组来统计某个字符出现的个数即可！）

仅仅创建一个哈希表也是可以解决问题的，只不过下面要通过多次if ，else if，来一一列举出现的情况！所以再新建一个真的哈希表用于出现蛙叫字符出现的下标即可！！因为我们要求青蛙的最少个数！所以当一个蛙叫字符出现时，首先考虑的是看看其前面是否出现了！如果没有出现的话，直接返回-1，因为此时不满足情况！当前面的元素存在时，只需将前面的元素--，当前元素++即可！

因为第一个字符没有前缀字符！所以与后面的字符所区分的情况又不一样！当元素为第一个字符时，只需要判断最后字符是否存在，如果存在--，不存在++即可！最后只需要统计出最后一个字符出现的个数即可！

需要注意的是：当最后遍历完成后，如果还有其它字符的个数不为0时，直接返回-1

例如 "crroak" 这种情况！根本不可能出现这种蛙叫，所以返回-1！

最后当遍历完字符串之后，只需要返回哈希表中最后一个元素的个数即可！

对应上图的规律编写代码即可完成求解！！