数青蛙 --- 模拟

目录

一：题目

二：算法原理

三：代码实现

---

一：题目

题目链接：1419. 数青蛙 - 力扣（LeetCode） 

二：算法原理

三：代码实现

if else版本：

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs){int len = croakOfFrogs.size();unordered_map<char, int> hash;for (int i = 0; i < len; i++){if (croakOfFrogs[i] == 'c'){if (hash.count('k') && hash['k'] != 0){hash['k']--;hash['c']++;}elsehash['c']++;}else if (croakOfFrogs[i] == 'r'){if (hash.count('c') && hash['c'] != 0){hash['c']--;hash['r']++;}elsereturn -1;}else if (croakOfFrogs[i] == 'o'){if (hash.count('r') &&hash['r'] != 0){hash['r']--;hash['o']++;}elsereturn -1;}else if (croakOfFrogs[i] == 'a'){if (hash.count('o') && hash['o'] != 0){hash['o']--;hash['a']++;}elsereturn -1;}else if (croakOfFrogs[i] == 'k'){if (hash.count('a') && hash['a'] != 0){hash['a']--;hash['k']++;}elsereturn -1;}}if(hash['c'] == 0 && hash['r'] == 0 && hash['o'] == 0&&hash['a'] ==0)return hash['k'];else return -1;}
};

哈希表存<字符，下标>版：

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string s = "croak";//将它存在字符串中，代码适用于题目不知道字符串内容int len = s.size();vector<int> hash(len);//用数组模拟哈希表，每一个字符对应一个下标unordered_map<char,int> index;//存[x,x对应的下标]，x的前驱就是对应下标-1for(int i = 0;i < len; i++){index[s[i]] = i;}for(auto ch :croakOfFrogs){if(ch == s[0]){if(hash[len-1] != 0)hash[len-1]--;hash[0]++;}else{int i = index[ch];//当前字符的下标if(hash[i-1] == 0)return -1;else{hash[i-1]--;hash[i]++;}}   }//如果最后除了k以外其他字符不为0，说明有的青蛙没有叫完，也不行for(int i = 0; i < len-1;i++){if(hash[i] != 0)return -1;}return hash[len-1];}
};