算法实战：LeetCode 1419 数青蛙（模拟法）

题目描述

给定一个字符串 croakOfFrogs，它表示若干只青蛙发出的叫声序列。每只青蛙必须按顺序发出 "c", "r", "o", "a", "k" 五个字符才能完成一次完整的叫声。

我们需要计算发出该字符串所需的最少青蛙数量。如果字符串不是由合法的青蛙叫声组成，则返回 -1。

输入示例：

• 输入："croakcroak"

• 输出：1

• 解释：一只青蛙叫了两次完整的声音。

• 输入："crcoakroak"

• 输出：2

• 解释：两只青蛙交替发声。

解题思路

这道题的核心在于模拟青蛙叫声的状态流转。我们可以把每只青蛙看作一个状态机，它从 "c" 开始，经过 "r", "o", "a"，最后到达 "k" 结束。

为了统计最少需要多少只青蛙，我们只需要跟踪当前处于各个阶段的青蛙数量。具体来说，维护一个长度为 5 的数组，分别对应 'c', 'r', 'o', 'a', 'k' 这五个字符。

遍历字符串中的每个字符时：

1. 遇到 'c'：这是新叫声的开始。优先检查是否有刚完成叫声（即处于 'k' 阶段）的青蛙可以复用。如果有，让它回到 'c' 阶段；如果没有，说明需要新增一只青蛙。
2. 遇到其他字符：检查前一个字符对应的阶段是否有青蛙在等待。例如遇到 'r'，必须有青蛙处于 'c' 阶段。如果没有，说明序列非法，直接返回 -1。如果有，将该青蛙的状态推进到当前字符。
3. 循环结束后：检查是否所有青蛙都完成了叫声（即除了 'k' 阶段外，其他阶段计数都应为 0）。如果有青蛙卡在中间状态，说明输入不合法，返回 -1。

最终，处于 'k' 阶段的青蛙数量即为同时发声的最大并发量，也就是所需的最少青蛙数。

C++ 代码实现

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string s = "croak";
        int n = s.size();
        
        // 记录字符映射下标关系，方便查找前驱
        unordered_map<char, int> index;
        for (int i = 0; i < n; i++) {
            index[s[i]] = i;
        }
        
        
        ;
        
         (& ch : croakOfFrogs) {
             (ch == ) {
                
                 (hash[n - ] != ) {
                    hash[n - ]--;
                }
                
                hash[]++;
            }  {
                 t = index[ch];
                
                 (hash[t - ] == ) {
                     ; 
                }
                
                hash[t - ]--;
                hash[t]++;
            }
        }
        
        
         ( i = ; i < n - ; i++) {
             (hash[i] != ) {
                 ; 
            }
        }
        
        
         hash[n - ];
    }
};