算法题精讲：外观数列与数青蛙的模拟解法

42. 数青蛙

题目描述

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声的组合。为了发出完整的蛙鸣声 "croak"，一只青蛙必须按顺序依次发出 'c', 'r', 'o', 'a', 'k'。如果字符串中包含非法组合，返回 -1；否则返回所需的最少青蛙数量。

核心思路

这是一个典型的模拟问题。我们可以维护一个哈希表（或数组），记录当前处于 'c', 'r', 'o', 'a', 'k' 各个阶段的青蛙数量。

1. 遇到 'c'：优先复用刚刚完成 'k' 的青蛙（减少总数），如果没有可用的，则新增一只青蛙。
2. 遇到 'r', 'o', 'a', 'k'：检查前驱阶段是否有青蛙可用。如果有，该青蛙进入下一阶段；如果没有，说明序列不合法，直接返回 -1。
3. 结束检查：遍历完成后，所有青蛙必须都完成了 'k'，否则说明有未完成的叫声，返回 -1。

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) { // 非 'c' 字符
                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];
    }
};

流程解析

这里用数组 hash 模拟了状态机。index 映射简化了字符判断逻辑，避免了冗长的 if-else。关键点在于 'c' 的处理逻辑：只有当有青蛙刚叫完 'k' 时才复用，这保证了青蛙数量的最小化。同时，任何中间状态的缺失都会导致返回 -1，确保了输入的有效性校验。