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 模拟一
维护当前有多少青蛙（设为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 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 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 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 时间复杂度：O(n)
空间复杂度：O(1)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
