算法之力扣数青蛙
题目连接
文章目录
- 题目解析
- 算法原理
- 第一步
- 第二步
- 第三步
- 第三步
- 第四步指向o
- 代码讲解
- 代码实现
题目解析
先给大家来讲解一下这个题目的意思吧，这个题目是说呢给你一个蛙叫的字符串让你去设计一个算法求出发出这种蛙叫最少需要几只青蛙。比如说第一个样例发出这种叫声很明显一只青蛙叫两声就够了。
算法原理
我们以第二个样例为示范样列给大家讲解一下该怎么解决这个问题
第一步
我们以上面这个图为例，首先弄出一个表格这个表格第一行表示的是croak这五个字符每个字符的个数，然后用一个指针指向开头第一个字符在指针向后移动的过程中去改变表中的数字即可首先先看第一个字符是c因此先将c这个表格弄为1
第二步
第三步
当下面的指针向后移动到r的时候先查看表格中r前面的那个字符是不是大于0，之后如果大于那就是num[‘r’]++然后num[‘c’]–;
第三步
之后当指针再次向后移动的时候下一个字符为c我们可以看到c这个字符经过第二步变成了0并且k也是0因此我们让c再++
第四步指向o
第四步指向了o我们就让o前面的字符–并且让o++
然后就一直向后执行即可由此我们可以得到一个规律那就是
代码讲解
根据上面的讲解我们知道首先我们需要一个记录个数的数组，以及一个记录下标的哈希表
string a="croak";unordered_map<char,int>hash;hash['c']=0;hash['r']=1;hash['o']=2;hash['a']=3;hash['k']=4;int num[300];memset(num,0,sizeof(num));
我们可以看到hash是为了记录每个字符在字符串中的下标，num为了记录每个字符此时个数
代码实现
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string a="croak";unordered_map<char,int>hash;hash['c']=0;hash['r']=1;hash['o']=2;hash['a']=3;hash['k']=4;int num[300];memset(num,0,sizeof(num));for(int i=0;i<croakOfFrogs.size();i++){if(croakOfFrogs[i]=='c'){if(num['k']==0){num['c']++;}else if(num['k']>0){num['k']--;num['c']++;}}else{if(num[a[hash[croakOfFrogs[i]]-1]]>0){num[a[hash[croakOfFrogs[i]]-1]]--;num[a[hash[croakOfFrogs[i]]]]++;}else{return -1;}}}for(int i=0;i<4;i++){if(num[a[i]]!=0){return -1;}}return num['k'];}
};
想一直在一起不想分开遇到不好的可以共同克服，我有让人厌烦甚至超过底线的缺点我也会去改正。