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)
发表回复