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