【模拟】你会数青蛙吗？
【模拟】你会数青蛙吗？
1419. 数青蛙
给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。
示例 1：
输入：croakOfFrogs = "croakcroak"
输出：1
解释：一只青蛙 “呱呱” 两次示例 2：
输入：croakOfFrogs = "crcoakroak"
输出：2
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"示例 3：
输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。提示：
1 <= croakOfFrogs.length <= 105- 字符串中的字符只有
'c','r','o','a'或者'k'
思路一：模拟 + 哈希表记录出现字符个数
其实这道题也是一个模拟，只不过这个模拟不太容易想到，我们可能一开始上来会想着如何去统计一个 croak 中还穿插着多少个 croak，但是这样子是比较复杂的，所以我们要换个思路！
首先我们遍历整个字符串 croakOfFrogs，我们将遍历到的字符都加入到哈希表中，记录每个字符出现的次数，但是还要做一些处理。
如果遇到字符 c 的话，则说明这是一个新的 croak，则直接 让 hash[c]++，同时我们还要判断一下 hash[k] 也就是 croak 的最后一个字符 k 是否有计数，有的话说明之前至少有一个 croak 是已经存在的了，即已经至少存在一只青蛙了。此时出现了字符 c 的话，而题目要求的是最少的青蛙数量，所以我们就可以拿已经存在的一只青蛙来进行哇叫，而不需要再累加一只青蛙，所以我们要 让 hash[k]--（这里需要结合下面 hash[k] 的含义才能理解，其实 hash[k] 表示的是青蛙的数量）。而如果不存在字符 k 的话，则不需要做什么处理！
接着就是遇到字符 r 的话，此时我们需要去判断一下是否前面已经出现过字符 c 了，如果说不存在的话，说明这个叫声是错误的，直接 return -1 即可。而如果存在字符 c 的话，我们就要 让 hash[c]--，表示当前字符 r 已经匹配掉前面的一个字符 c 了，最后再 让 hash[r]++ 表示出现了字符 r，剩下的任务交给后面的字符去处理！
接下来的字符 o、a 其实和 r 的处理是一样的，不同的是字符 o 要判断前面是否出现了 r 可以匹配，而字符 a 要判断前面是否出现了 o 可以匹配，不存在的话直接 return -1，可以的话直接让对应的前面的字符在哈希表中减去一个计数，然后让当前的字符在哈希表中增加一个计数即可，原因和上面是一样的！
最后就是字符 k，它首先也是要判断一下前面是否出现过字符 a，如果不存在的话也是直接 return -1，而如果存在的话，则 让 hash[a]-- 表示匹配掉一个 a，并且 让 hash[k]++，表示又出现了一次 k。与上面不同的是，因为叫声的字符串是 croak，而 k 是最后一个字符，所以此时 hash[k] 的数量，就表示 croak 出现的次数！
这也就是为什么上面在遇到字符 c 的时候，我们需要判断一下是否字符 k，原因就是如果存在的话，说明已经证明起码有一只青蛙了，那为了题目要求的最少数量，就可以直接让 hash[k]-- 表示拿走一只青蛙用来产生新的叫声，而不会产生新的青蛙！只有当不存在字符 k 的时候，才需要说产生新的青蛙！
最后处理完字符串之后，需要 判断一下哈希表中除了字符 k 以外的字符，是不是计数有大于零的，有的话就错误了，直接 return -1；并且 判断哈希表中 k 的计数是否也为零，是的话说明字符串中不存在叫声，也是直接 return -1。
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
unordered_map<char, int> hash;
for(int i = 0; i < croakOfFrogs.size(); ++i)
{
if(croakOfFrogs[i] == 'c')
{
if(hash.count('k') && hash['k'] > 0)
hash['k']--;
}
else if(croakOfFrogs[i] == 'r')
{
if(!hash.count('c') || hash['c'] < 1)
return -1;
hash['c']--;
}
else if(croakOfFrogs[i] == 'o')
{
if(!hash.count('r') || hash['r'] < 1)
return -1;
hash['r']--;
}
else if(croakOfFrogs[i] == 'a')
{
if(!hash.count('o') || hash['o'] < 1)
return -1;
hash['o']--;
}
else if(croakOfFrogs[i] == 'k')
{
if(!hash.count('a') || hash['a'] < 1)
return -1;
hash['a']--;
}
hash[croakOfFrogs[i]]++; // 别忘了让当前字符++
}
// 最后需要判断结果集是否正确
for(const auto& e : hash)
{
if(!(e.first == 'k') && e.second > 0) // 除了k以外的字符，计数不能大于零
return -1;
if(e.first == 'k' && e.second < 1) // k字符的计数不能为零
return -1;
}
return hash['k']; // 最后返回的hash[k]就代表青蛙的个数！
}
};思路二：模拟 + 哈希表记录字符下标 + 数组记录字符出现个数
上面这种方法虽然能解决问题，但是写了很多 if 语句，看起来不够优雅，我们可以使用【哈希表记录字符下标 + 数组记录字符出现个数】来解决这个问题！
首先我们要思考，之前为什么需要写这么多的 if 语句，但是内部代码基本上是类似的，本质就是我们没建立起 c、r、o、a、k 几个字母能快速找到对应前驱字符的关系，所以和上面解法不同的是，这里数组对应 c 的下标就是 0、r 的下标就是 1……以此类推，然后将这些下标再映射存放到哈希表中，这样子我们就能快速的在找 r 的时候，只需要用哈希表检索字母就能找到 r 在数组中的下标，接着只需要在数组中对当前位置下标减一，就能快速找到 c，然后利用数组进行计数！
同理后面的字符也是如此，这样子一来我们就能将 r、o、a、k 几个字母单独用一个 if 语句就能搞定，而不需要写冗余的代码了！
然后其它的思路和上面的题解是一样的！
总结：当哈希表中存放数值无法做到减少代码冗余的时候，可以考虑存放其索引位置，再利用其它容器比如数组来计数达到同样的目的，减少代码冗余！
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
// 这样子写可以根据题目的不同，只需要修改一下str就能适用于其它同样类型的题！
string str = "croak";
int n = str.size();
vector<int> arr(n, 0);
// 创建哈希表，将字符对应下标进行映射
unordered_map<char, int> hash;
for(int i = 0; i < n; ++i)
hash[str[i]] = i;
// 遍历处理青蛙叫声字符串
for(int i = 0; i < croakOfFrogs.size(); ++i)
{
if(croakOfFrogs[i] == 'c') // 单独为字符c处理
{
if(arr[hash['k']] > 0)
arr[hash['k']]--;
}
else
{
if(arr[hash[croakOfFrogs[i]] - 1] < 1) // 通过数组中下标减一得到前驱字符
return -1;
arr[hash[croakOfFrogs[i]] - 1]--;
}
arr[hash[croakOfFrogs[i]]]++; // 别忘了当前字符++
}
// 最后需要判断结果集是否正确
for(int i = 0; i < n; ++i)
{
if(i != n - 1 && arr[i] > 0) // 除了k以外的字符，计数不能大于零
return -1;
if(i == n - 1 && arr[i] == 0) // k字符的计数不能为零
return -1;
}
return arr[n - 1];
}
};腾讯云开发者
