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–，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;
// 新一轮发声
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++；若 ch[k]=0，只能派一只新的青蛙开始呱，也即 cnt++
- ch=r：查看是否有青蛙呱到 c，也即 r 的前一个字符。若无，阐明以后呱到 r 是不非法的，return -1；若有，将呱到字符 c 的青蛙前进一步，让其呱到 r，也即 cnr–，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, 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)