1. 题目解析
题目链接：1419. 数青蛙
这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。
2.算法原理
一、模拟青蛙叫声的基本逻辑
在模拟青蛙叫声的过程中，我们需要遵循一定的规则来判断何时青蛙会发出声音。具体规则如下：
当遇到字符序列 'r'、'o'、'a'、'k' 时，我们需要检查每个字符之前是否已经有青蛙发出叫声。这是因为青蛙的叫声需要按照一定的顺序来触发，如果前面的字符没有被青蛙喊出，那么当前字符也无法被喊出。
对于字符 'r'、'o'、'a'、'k' 的检查，我们需要回溯到每个字符的前一个字符，查看是否有青蛙已经发出了叫声。如果有，则当前字符可以被青蛙喊出；否则，我们需要直接返回 -1，表示无法模拟出青蛙的叫声。
当遇到字符 'c' 时，情况稍有不同。我们需要特别检查字符 'k' 是否已经被青蛙喊出。这是因为 'c' 的叫声通常是在 'k' 的叫声之后发出的，作为一种特殊的叫声组合。如果 'k' 已经被喊出，那么青蛙可以继续喊出 'c'；否则，我们需要重新开始模拟，即重新引入一个青蛙来尝试喊出这些字符。
二、算法执行的详细步骤
根据以上逻辑，我们可以将算法的执行过程细化为以下步骤：
- 初始化一个标志位，用于记录是否有青蛙发出叫声。
- 遍历输入的字符序列，对每个字符进行判断。
- 对于字符 'r'、'o'、'a'、'k'，检查其前一个字符是否已经被青蛙喊出。如果是，则更新标志位，表示当前字符可以被喊出；否则，返回 -1。
- 对于字符 'c'，检查字符 'k' 是否已经被喊出。如果是，则允许青蛙喊出 'c'；否则，重新开始模拟过程。
- 如果遍历完整个字符序列后，青蛙成功地喊出了所有字符，则算法执行成功；否则，返回 -1 表示无法模拟出青蛙的叫声。
3.代码编写
class Solution
{
public:
int minNumberOfFrogs(string croakOfFrogs)
{
string s = "croak";
int n = s.size();
vector<int> hash(n);
unordered_map<char, int> idx;
for(int i = 0; i < n; i++) idx[s[i]] = i;
for(const auto &ch : croakOfFrogs)
{
if(ch == 'c')
{
if(hash[n - 1]) hash[n - 1]--;
hash[0]++;
}
else
{
if(hash[idx[ch] - 1] == 0) return -1;
hash[idx[ch] - 1]--;
hash[idx[ch]]++;
}
}
for(int i = 0; i < n - 1; i++)
{
if(hash[i]) return -1;
}
return hash[n - 1];
}
};The Last
嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。
觉得有点收获的话，不妨给我点个赞吧！
如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~
