本文主要是介绍leetcode 1419. 数青蛙（medium）（优质解法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：力扣（LeetCode）官网 - 全球极客挚的技术成长平台
代码：
class Solution {public int minNumberOfFrogs(String croakOfFrogs) {String t="croak";int tLength=t.length();// hash 数组用来存放青蛙喊的过程，记录有多少个青蛙喊到了哪个字符int[] hash=new int[tLength];HashMap<Character,Integer> index_char=new HashMap<>();//将字符和对应的下标添加到 index_char 中for(int i=0;i<tLength;i++){index_char.put(t.charAt(i),i);}//遍历 croakOfFrogs 字符串，分析青蛙蛙鸣的流程for(int i=0;i<croakOfFrogs.length();i++){// 获取字符在 hash 数组中的下标int index=index_char.get(croakOfFrogs.charAt(i));if(index==0){//查询有没有喊完的青蛙可以继续喊if(hash[tLength-1]>0){//有喊完的青蛙hash[tLength-1]--;}//没有喊完的青蛙hash[index]++;}else{//判断是否有青蛙在喊前一个字符if(hash[index-1]>0){//有青蛙在喊前一个字符hash[index-1]--;hash[index]++;}else{//没有青蛙在喊前一个字符return -1;}}}//判断是否有没喊完的青蛙for(int i=0;i<tLength-1;i++){if(hash[i]!=0){return -1;}}return hash[tLength-1];}
}题解：
本题采用的解法是模拟，模拟题目的要求，找到最终的结果。
首先需要搞清题意，青蛙是根据字符串 croak 呱呱叫，只有完整的叫了 croak 才算完，如果叫的字符串不完整或者不正确，都直接返回 -1 即可
我们可以认为，青蛙叫的时候必须按照 c -> r -> o -> a -> k 的顺序，只有叫了前一个字符才能叫后一个字符，我们可以用一个数组 hash 来记录有几只青蛙叫到了哪个字符，并用哈希表来记录字符与下标的对应关系，以示例 2 为例 croakOfFrogs = "croakcroak"
定义一个 i 指针遍历 croakOfFrogs 字符串，让青蛙叫，当 i 指向 c 字符时表示要叫 c 字符，首先需要判断是否有已经叫好的青蛙可以来接着叫，叫好的青蛙记录在 k 字符对应的个数，个数为 0 代表没有叫好的青蛙，那就需要一个新的青蛙来叫，将 hash 数组中 c 字符对应下标中的数据 ++，然后 i 向后继续遍历
hash
c r o a k
0 0 0 0 0
croakOfFrogs
c r o a k c r o a k
i
i 指针指向 r ，在青蛙喊 r 字符前需要确定有没有青蛙已经喊了 c 字符，如果没有青蛙喊 c 字符，说明就不能喊到 r 字符，此时 croakOfFrogs 中的数据就是错误的，返回 -1，但此时在 hash 数组中 c 字符对应的数据为 1 ，代表有 1 个青蛙叫到了 c 字符，可以让叫到 c 字符的青蛙继续叫 r 字符，所以在 hash 表中 c 字符对应的数据 - - ，r 字符对应的数据 ++
hash
c r o a k
1 0 0 0 0
croakOfFrogs
c r o a k c r o a k
i
此时 i 指针向前遍历指向 o ，也是同样的处理方法，判断是否有青蛙喊到 o 字符之前的 r 字符，要是有就让该青蛙喊到 o 字符
hash
c r o a k
0 1 0 0 0
croakOfFrogs
c r o a k c r o a k
i
当 i 移动到第一个 k 字符以后，数据如下所示，青蛙喊到 k 字符就代表这只青蛙喊完了，hash 数组中 k 字符对应的值就是喊完的青蛙数目
i 继续向下遍历
hash
c r o a k
0 0 0 0 1
croakOfFrogs
c r o a k c r o a k
i
当 i 继续向下遍历，遍历到 c 字符，先要判断此时是否有已经叫好在休息的青蛙，hash 数组中 k 字符对应的个数就是休息青蛙的数目，此时有 1 只青蛙在休息，所以不需要新的青蛙来叫，直接让正在休息的这个青蛙叫即可
于是让 k 字符对应的数据减一，c 字符对应的数据加一，在休息的青蛙就去接着叫了
hash
c r o a k
1 0 0 0 0
croakOfFrogs
c r o a k c r o a k
i
等 i 指针遍历完 croakOfFrogs 字符串以后，hash 数组中，k 字符对应的数目就是发出叫声的青蛙数目，但要注意，如果除了 k 的其他字符在 hash 数组有对应的数据说明有没叫完青蛙，这就代表 croakOfFrogs 字符串不符合规定，直接返回 -1
这篇关于leetcode 1419. 数青蛙（medium）（优质解法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
