LeetCode 1419 数青蛙：状态模拟求最少青蛙数量｜Java 题解

• 🏠博客主页：小谢同学的小破站
• ✍️本文由 小谢同学的小破站 原创，首发于 CSDN 💻
• ☕JavaSE专栏：JavaSE
• 📗JavaEE初阶专栏：JavaEE初阶
• 📘JavaEE进阶专栏：JavaEE进阶
• 🧩数据结构专栏：数据结构
• ⚙️算法专栏：算法
• 📚MySQL初阶专栏：MySQL初阶
• 🔐MySQL进阶专栏：MySQL进阶
• 🌐计算机网络专栏：计算机网络
• 💻C语言专栏：C语言
• 👍欢迎点赞👍 收藏⭐ 留言📝，发现错误欢迎指正！
• ✨脚踏实地，持续深耕，奔赴自己的目标✨
  ----- 📌分割线 📌-------

数青蛙

• 1. 题目解析
• 2. 算法原理
• 3. 编写代码

前言：
   这里是小谢同学的一道小小的算法题目,希望这个解法能帮助到你~

1. 题目解析

简单来说:

 给你一个字符串,来让你判断这个字符串是不是完整的蛙叫,并且要求返回一个尽可能小的青蛙数量

例如:

编号	输入	输出	解释
示例 1	"croakcroak"	1	一只青蛙"呱呱"两次
示例 2	"crcoakroak"	2	最少两只：第一只 crcoakroak，第二只 crcoakroak
示例 3	"croakcrook"	-1	不是 "croak" 的有效组合
示例 4	"croakcroa"	-1	有青蛙叫到一半就没了

简单来说：

1. 一只青蛙完整叫声顺序：c → r → o → a → k
2. 遇到 c：要么启用一只空闲老青蛙，要么新增一只青蛙；
3. 遇到 k：代表这只青蛙叫完一轮，青蛙释放出来，可以重复使用；
4. 中间顺序乱掉、叫到一半中断，直接返回 -1；
5. 全程记录同时正在叫的青蛙峰值，就是答案。

提示（约束）

• 1 <= croakOfFrogs.length <= 10^5
• 字符串中的字符只有 'c'、'r'、'o'、'a' 或者 'k',并没有多余的字符

这道题不就是相当于一个模拟的方法?题目要求我们数青蛙,我们进行模拟即可~

2. 算法原理

1. 建立顺序映射：c=0，r=1，o=2，a=3，k=4，代表蛙鸣的5个阶段。
2. 维护计数器数组，统计处在每个阶段的青蛙数量。
3. 遍历字符串每一个字符：
   • 如果是 c（阶段0）：
     • 如果有已经叫完（k阶段）空闲青蛙，就复用；没有空闲，总青蛙数+1。阶段0计数+1。
   • 如果是其他字符（r/o/a/k）：
     • 看前一个阶段有没有青蛙，没有的话说明顺序非法，直接返回 -1。
     • 前一阶段计数减一，当前阶段计数加一。
   • 当字符是 k（阶段4）：叫完了，这只青蛙就会回到空闲池，可以再次被使用。

不断重复这个过程,直到遍历数组结束

4. 遍历结束，必须保证：除k阶段以外，其他阶段全部为0。

---

3. 编写代码

易错点:

1. 遍历结束之后一定要校验！

例如输入"ccroak"，两个 c 开头，后面只完成一次 croak，有一只青蛙卡在 c 阶段没叫完，应该返回 -1，很多人忘记这一步。

2. k 结束之后，青蛙不是消失，而是变成空闲，可以重复再叫一遍 c，不需要一直新增青蛙。
3. 字符顺序不能乱，例如直接出现r，前面没有c，直接非法返回 - 1。

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
    	//转化为字符数组
        char[] s = croakOfFrogs.toCharArray();
        //创建青蛙叫
        String t = "croak";
        int n = t.length();
        int[] hash = new int[n];
        //用来存储对应字符和对应字符的下标
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(t.charAt(i), i);
        }
        for (char ch : s) {
            if (ch == t.charAt(0)) {
            //判断最后一个位置是否有青蛙叫完
                if (hash[n - 1] != 0) {
                    hash[n - 1]--;//复用已经叫完的青蛙
                }
                hash[0]++;
            } else {
            //拿到对应字符的下标
                int index = map.get(ch);
                //判断前一个字符是否有
                if (hash[index - 1] == 0) {
                    return -1;
                } else {
                    hash[index]++;
                    hash[index - 1]--;
                }
            }
        }
        //防止没有叫完的青蛙
        for (int i = 0; i < n-1; i++) {
            if(hash[i]!=0) {
                return -1;
            }
        }
        return hash[n - 1];
    }
}

---

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2502_93799892/article/details/167174232