力扣：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！

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

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