模拟算法【3】——1419.数青蛙

在这里插入图片描述

文章目录

🍥1. 题目
🥮2. 算法原理
🍡3. 代码实现

🍥1. 题目

题目链接：1419. 数青蛙 - 力扣（LeetCode）

给你一个字符串 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'

🥮2. 算法原理

这题是一个比较复杂的模拟，当我们遍历到当前的字符的时候，我们需要看前面是否有“青蛙”叫的字符，就是统计每个字符出现的情况，例如示例二：crcoakroak，当叫到第一个字符c的时候，我们用1标记一下，表示青蛙叫了一下，接下来遍历到r的时候，发现r前面有一个c字符，将前面的青蛙“挪过来”，让它叫r这个字符，即hash[c]--，hash[r]++

总结：

r o a k的逻辑都是一样的，都需要找一下前驱字符是否在哈希表中存在
1. 存在前驱-1
2. 不存在直接返回-1
c，找最后一个字符是否在哈希表当中
1. 存在最后一个字符--，当前字符++
2. 不存在说明没有青蛙叫，当前字符++

🍡3. 代码实现

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs)
    {
        string cry = "croak";
        int n = cry.size();
        vector<int> hash(n);    //模拟哈希表
        
        unordered_map<char,int> index;  //存下标[ch,ch下标]
        for(int i=0; i<n; i++)
            index[cry[i]] = i;

        for(auto ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                if(hash[n-1] != 0)  hash[n-1]--;
                hash[0]++;
            }
            else
            {
                int i = index[ch];
                if(hash[i-1] == 0)  return -1;
                hash[i-1]--;
                hash[i]++;
            }
        }
        for(int i=0; i<n-1; i++)
            if(hash[i]!=0)
                return -1;
            
        return hash[n-1];
        
    }
};