算法实战：外观数列与数青蛙的模拟解法

流程解析

42. 数青蛙

题目链接

1419. 数青蛙 - 力扣（LeetCode）

题目描述

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声混合在一起。你需要计算至少需要多少只青蛙才能发出这个声音。

如果字符串不是由合法的 "croak" 组合而成，则返回 -1。

题目示例

解法思路

这道题本质上是模拟青蛙叫声的状态流转。青蛙必须按照 'c' -> 'r' -> 'o' -> 'a' -> 'k' 的顺序叫。

我们可以维护一个计数器数组或哈希表，记录当前处于各个阶段的青蛙数量：

1. 遇到 'c'：这是新青蛙开始叫，或者一只完成叫的青蛙复用。优先复用已完成（'k' 阶段）的青蛙，如果没有则新增一只。
2. 遇到 'r', 'o', 'a', 'k'：检查前驱字符是否有青蛙在等待。如果有，该青蛙进入下一阶段；如果没有，说明序列非法，直接返回 -1。
3. 结束检查：遍历完成后，所有青蛙必须都完成了 'k' 阶段，否则说明有青蛙没叫完，返回 -1。

为了快速查找字符对应的下标，我们用一个哈希表映射 'c','r','o','a','k' 到数组索引 0~4。

C++ 代码实现

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string s = "croak";
        int n = s.size();
        vector<int> hash(n, 0); // 用数组模拟哈希表存放各阶段字符计数
        unordered_map<char, int> index; // 字符到下标的映射

        for (int i = 0; i < n; i++) {
            index[s[i]] = i;
        }

        for (char c : croakOfFrogs) {
            int x = index[c];
            if (x != 0) { // 当前字符为 r、o、a、k
                // 需要前驱字符存在
                if (hash[x - 1]-- == 0) {
                    return -1;
                }
                hash[x]++;
            } else { // 当前字符为 c
                // 优先复用已完成的青蛙
                if (hash[n - 1]) {
                    hash[n - 1]--;
                }
                hash[x]++;
            }
        }

        // 检查是否所有青蛙都完成了叫声
        for (int i = 0; i < n - 1; i++) {
            if (hash[i] != 0) {
                return -1;
            }
        }
        return hash[n - 1];
    }
};

流程解析