当前位置：首页 > news >正文

模拟(数青蛙)(5)

news 2026/6/1 2:33:42

https://blog.csdn.net/2601_95366422/article/details/158928787

上节课链接

一.题目

1419. 数青蛙 - 力扣（LeetCode）

二.思路讲解

2.1 审题

题目要求我们判断一个由多个"croak"交错组成的字符串是否有效，并计算出最少需要多少只青蛙才能发出所有这些蛙鸣。每个青蛙必须按顺序叫出c → r → o → a → k五个字母，且同一时间可以有多只青蛙同时叫，但每个字母必须严格按顺序。如果字符串不是有效组合，返回 -1。

2.2 思路讲解

要模拟这个过程，我们需要记录每个字母当前被叫的次数，以及正在叫的青蛙数量。由于只有五个字母，我们可以用一个长度为5的数组来存储每个字母的当前计数，数组下标与字母对应（例如 0:c, 1:r, 2:o, 3:a, 4:k）。这样，遍历字符串时，根据当前字符更新计数。

关键点在于如何处理 c 和 k：

遇到c：表示一只青蛙开始叫。为了最少青蛙数，我们应优先重用已经叫完的青蛙（即那些已经输出过k的青蛙）。所以先检查是否有k的计数（即是否有空闲青蛙），如果有，则让这只空闲青蛙重新开始（k--，c++）；否则，新开一只青蛙（c++）。
遇到r、o、a、k时，必须保证前一个字母的计数大于0，否则无效。例如遇到r，需要c > 0，然后c--，r++；遇到o需要r > 0，然后r--，o++，以此类推。特别地，遇到k时，需要a > 0，然后a--，k++，此时这只青蛙完成了叫声，k 计数增加，表示空闲青蛙数量。

为什么不能用哈希表存次数而要用数组？因为我们需要按顺序检查前后关系，主要是数组可能会出现穿插的c，那么我们就无法找到当前字母和上一个字母的关系了！

遍历结束后，需要检查数组中所有计数是否都为0（即所有青蛙都叫完了），如果有残留，则说明字符串无效，返回 -1。否则，返回过程中记录的最大青蛙数。

核心要点：

用数组模拟五个字母的计数，下标对应字母顺序。
遇到c时优先重用已完成青蛙（k--），否则新开。
遇到其他字母时，必须保证前一个字母计数大于0，然后转移计数。
最终检查所有计数是否为0，判断有效性。

三.代码演示

class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { int hash[5] = {0};//次数,croak对应的次数等于其下标在hash里面存在的次数 unordered_map<char, int>index;//前者是字符，后者是字符的下标 string t = "croak"; for(int j = 0;j < t.size();j++) { index[t[j]] = j;//把croak按顺序给上下标,c:0，r:1,o:2,a:3,k:4 } int n = croakOfFrogs.size(); for(const auto& ch : croakOfFrogs) { //判断是否存在青蛙 if(ch == 'c') { //存在叫完的青蛙，那么派遣它继续叫 if(hash[index['k']] != 0) { hash[index['k']]--; hash[index['c']]++; } //不存在叫完的青蛙，派遣新青蛙 else hash[index['c']]++; } //判断青蛙是否叫完前一个字符 else { //存在叫完的前一个字符，派遣那个青蛙叫这个 if( hash[index[ch] - 1] != 0) { hash[index[ch] - 1]--; hash[index[ch]]++; } else { return -1; } } } //看看是否存在没叫完的情况 for(int i = 0;i < 4;i++) { if(hash[i] != 0) return -1; } return hash[4];//返回k的次数 } };

四.代码讲解

一、初始化映射和计数数组

为了高效处理五个字母的顺序关系，我们首先建立一个映射，将字符'c','r','o','a','k'分别映射到下标0,1,2,3,4。这里使用unordered_map<char, int> index来存储这个映射，方便后续根据字符快速获取其位置。同时，定义一个长度为5的数组hash，用于记录当前每个字母的计数，即正在发出该字母的青蛙数量。初始时所有计数为0。

二、遍历字符串模拟青蛙叫

接下来，遍历输入字符串croakOfFrogs中的每一个字符ch，根据字符类型进行不同的处理。

1. 遇到'c'的情况

当字符为'c'时，表示一只青蛙要开始叫。为了最少青蛙数，我们优先重用已经完成一次叫声的青蛙（即已经叫出过'k'的青蛙）。因此先检查hash[index['k']]是否大于0：

如果大于0，说明有空闲青蛙，则让这只空闲青蛙重新开始叫，即hash[index['k']]--（空闲减少），同时hash[index['c']]++（正在叫 c 的青蛙增加）。
如果等于0，说明没有空闲青蛙，则需要新开一只青蛙，直接hash[index['c']]++。

2. 遇到其他字符（'r','o','a','k'）

对于非'c'的字符，需要保证该字符的前一个字母已经有青蛙在叫，否则顺序错误。例如，要叫'r'，必须存在正在叫'c'的青蛙。通过映射得到当前字符的下标pos = index[ch]，那么前一个字符的下标就是pos - 1。检查hash[pos - 1]是否大于0：

如果大于0，说明有青蛙已经叫完了前一个字母，可以继续叫当前字母。此时将前一个字母的计数减1，当前字母的计数加1，即hash[pos - 1]--和hash[pos]++。
如果等于0，说明顺序错误，没有青蛙能够发出当前字符，直接返回-1。

三、检查有效性并返回结果

遍历结束后，我们需要确保所有青蛙都完成了叫声，即没有正在叫的青蛙残留。检查数组hash中下标0 到 3的计数是否全为0（因为'c','r','o','a'不能有残留）。如果存在非0值，说明字符串不是有效组合，返回-1。如果都为零，则hash[4]中存储的就是总共参与过的青蛙数量，也就是最少需要的青蛙数，直接返回hash[4]即可。