【C++算法】42.模拟_数青蛙

文章目录

• • 题目链接：
  • 题目描述：
  • 解法
  • C++ 算法代码：

题目链接：

1419. 数青蛙

题目描述：

解法

模拟：

利用一个指针，从前往后遍历，遍历到r就看前面有没有c，遍历到o就看前面有没有r。

建立一个哈希表记录每一个字符出现的情况。

比如：

1. 先出现c，哈希表里c的值是1
2. 出现r后，c的值-1，r的值+1
3. 当完成了c r c o a k r o a k后，再次出现c r o a k就不一样了，因为题目要的是最小青蛙数。
4. 这个时候，我们让k的值-1，c的值+1，代表里面有个青蛙重新开始叫了。
5. 当结束后，应该只有k里面有值，如果这个时候除了k还有其他元素有值，那么返回-1

C++ 算法代码：

class Solution 
{
    public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string t = "croak"; // 定义一个字符串 t，表示 "croak" 的顺序
        int n = t.size();
        vector<int> hash(n); // 用数组来模拟哈希表 // hash[0] = 'c', hash[1] = 'r', ..., hash[4] = 'k'
        unordered_map<char, int> index; //[x, x这个字符对应的下标]
        for(int i = 0; i < n; i++)
            index[t[i]] = i; // 例如，'c' -> 0, 'r' -> 1, ..., 'k' -> 4

        for(auto ch : croakOfFrogs) // 遍历输入字符串 croakOfFrogs 中的每个字符
        {
            if(ch == 'c') // 如果当前字符是 'c'，表示一只青蛙开始叫
            {
                if(hash[n - 1] != 0) hash[n - 1]--; // 检查是否有空闲的青蛙（'k' 计数大于 0），如果有，则重用一只青蛙
                hash[0]++; // 增加 'c' 的计数，表示一只新的青蛙开始叫
            }
            else // 如果当前字符不是 'c'，则表示一只青蛙正在发出声音
            {
                int i = index[ch]; // 获取当前字符在 "croak" 中的索引
                if(hash[i - 1] == 0) return -1; // 如果前一个字符的计数为 0，则说明当前字符不符合 "croak" 的顺序，返回 -1
                hash[i - 1]--; hash[i]++; // 前一个字符计数减 1，当前字符计数加 1
            }
        }
        for(int i = 0; i < n - 1; i++)
            if(hash[i] != 0) // 检查 "croak" 中每个字符的计数是否都为 0，除了最后一个字符 'k'
                return -1; // 如果有任何一个字符的计数不为 0，则返回 -1
        return hash[n - 1]; // 返回 'k' 的计数，即同时发出 "croak" 声音的最小青蛙数量
    }
};