每日OJ题_算法_模拟⑤_力扣1419. 数青蛙

目录

力扣1419. 数青蛙

解析代码1

解析代码2

---

力扣1419. 数青蛙

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 <= 10^5
• 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

---

解析代码1

五个if：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        // int c = 0, r = 0, o = 0, a = 0, k = 0;
        vector<int> arr(6, 0); // 用下标1到5分别映射五个字母
        for(auto& e : croakOfFrogs)
        {
            if(e == 'c')
            {
                if(arr[5] > 0)
                    --arr[5];
                ++arr[1];
            }
            if(e == 'r')
            {
                if(arr[1] > 0)
                    --arr[1];
                else
                    return -1;
                ++arr[2];
            }
            if(e == 'o')
            {
                if(arr[2] > 0)
                    --arr[2];
                else return -1;
                ++arr[3];
            }
            if(e == 'a')
            {
                if(arr[3] > 0)
                    --arr[3];
                else  return -1;
                ++arr[4];
            }
            if(e == 'k')
            {
                if(arr[4] > 0)
                    --arr[4];
                else return -1;
                ++arr[5];
            }
        }
        if(arr[1] > 0 || arr[5] == 0)
            return -1;
        return arr[5];
    }
};

---

解析代码2

用哈希表：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string str = "croak";
        int n = str.size();
        vector<int> arr(n, 0); // 数组模拟哈希表
        unordered_map<char, int> index; //映射每个字符的下标
        for(int i = 0; i < n; ++i)
            index[str[i]] = i;
 
        for(auto& e : croakOfFrogs)
        {
            if(e == 'c')
            {
                if(arr[n-1] != 0)
                    --arr[n-1];
                ++arr[0];
            }
            else
            {
                if(arr[index[e] - 1] == 0)
                    return -1;
                --arr[index[e] - 1];
                ++arr[index[e]];
            }
        }
        for(int i = 0; i < n-1; ++i)
        {
            if(arr[i] != 0)
                return -1;
        }
        return arr[n-1];
    }
};