1419. 数青蛙
关键词：模仿
题目起源：1419. 数青蛙 - 力扣（Leetcode）
题目形容
T模仿给你一个字符串 croakOfFrogs，它示意不同青蛙收回的蛙鸣声（字符串 "croak" ）的组合。因为同一时间能够有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
请你返回模仿字符串中所有蛙鸣所需不同青蛙的起码数目。
要想收回蛙鸣 "croak"，青蛙必须 依序 输入 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输入全副五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干无效的 "croak" 字符混合而成，请返回 -1 。
输出：croakOfFrogs = "croakcroak"输入：1 解释：一只青蛙 “呱呱” 两次输出：croakOfFrogs = "crcoakroak"输入：2 解释：起码须要两只青蛙输出：croakOfFrogs = "croakcrook"输入：-1解释：给出的字符串不是 "croak" 的无效组合。数据范畴1 <= croakOfFrogs.length <= 105字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'模仿一
保护以后有多少青蛙（设为fragNum）在呱，fragNum的最大值就是至多须要的青蛙数。
设呱到字符char的青蛙数为cnt[char]，将字符croak映射到0~4，遍历字符串croakOfFrogs，设以后字符为ch：
- ch=c：一只新的青蛙退出呱的队伍，fragNum++
- ch=r：查看是否有青蛙呱到c，也即r的前一个字符。若无，阐明以后呱到r是不非法的，return -1；若有，将呱到字符c的青蛙前进一步，让其呱到r，也即cnr[c]--，cnt[r]++
- ch=o：与ch=r相似
- ch=a：与ch=r相似
- ch=k：意味着有一只青蛙呱完了，正在呱的青蛙数应该-1，也即fragNum--
遍历完后，若还有青蛙在呱，也即fragNum＞0，阐明字符串croakOfFrogs不能由若干轮呱组成。
int minNumberOfFrogs(string croakOfFrogs) { // 长度必须是5的倍数 if (croakOfFrogs.size() % 5)return -1; // 将字母映射成数字 unordered_map<char, int> mp = {{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}}; // 正在发声的青蛙的数量 发声发到字符i的青蛙的数量 int frogNum = 0, cnt[4] = {0}; // 模仿 int t, res = 0; for (char c: croakOfFrogs) { t = mp[c]; // 新一轮发声 if (t < 1) { frogNum++, cnt[t]++; // 求最大值 if (frogNum > res)res = frogNum; } // 非新一轮发声 else { // 前一个字符数量为0，不能形成一轮发声 if (!cnt[t - 1])return -1; cnt[t - 1]--; t == 4 ? frogNum-- : cnt[t]++; } } // 最初还有发声没有实现的青蛙，阐明不能由若干轮发声组成 if (frogNum)return -1; return res;}工夫复杂度：O(n)
空间复杂度：O(1)
模仿二
保护有多少只青蛙呱完。与模仿一不同的是，在模仿二中，当遇到字符c时，若有青蛙呱完，可让其从新开始呱，不用新派一只青蛙。
设呱到字符char的青蛙数为cnt[char]，将字符croak映射到0~4，遍历字符串croakOfFrogs，设以后字符为ch：
- ch=c：若ch[k]!=0，阐明有青蛙呱完，可让一只呱完的青蛙从新呱，也即cnt[k]--，cnt[c]++；若ch[k]=0，只能派一只新的青蛙开始呱，也即cnt[c]++
- ch=r：查看是否有青蛙呱到c，也即r的前一个字符。若无，阐明以后呱到r是不非法的，return -1；若有，将呱到字符c的青蛙前进一步，让其呱到r，也即cnr[c]--，cnt[r]++
- ch=o：与ch=r相似
- ch=a：与ch=r相似
- ch=k：与ch=r相似
遍历完结，除了呱到k的青蛙外，其余呱到任何字符的青蛙数都应该为0。
int minNumberOfFrogs(string croakOfFrogs) { // 长度必须是5的倍数 if (croakOfFrogs.size() % 5)return -1; // 将字母映射成数字 unordered_map<char, int> mp = {{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}}; // 正在发字符i的青蛙数 int cnt[5] = {0}; // 模仿 int t; for (char c: croakOfFrogs) { t = mp[c], cnt[t]++, t = (t + 4) % 5; if (cnt[t])cnt[t]--; else if (t != 4)return -1; } // 除k外，发其它字母的青蛙数必须为0 for (int i = 0; i < 4; i++) if (cnt[i])return -1; return cnt[4];}工夫复杂度：O(n)
空间复杂度：O(1)