题目:
代码:
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!
最后当遍历完字符串之后,只需要返回哈希表中最后一个元素的个数即可!
对应上图的规律编写代码即可完成求解!!