博客主页小谢同学的小破站✍️本文由小谢同学的小破站原创首发于 CSDN ☕JavaSE专栏JavaSEJavaEE初阶专栏JavaEE初阶JavaEE进阶专栏JavaEE进阶数据结构专栏数据结构⚙️算法专栏算法MySQL初阶专栏MySQL初阶MySQL进阶专栏MySQL进阶计算机网络专栏计算机网络C语言专栏C语言欢迎点赞 收藏⭐ 留言发现错误欢迎指正✨脚踏实地持续深耕奔赴自己的目标✨----- 分割线 -------数青蛙1. 题目解析2. 算法原理3. 编写代码前言这里是小谢同学的一道小小的算法题目,希望这个解法能帮助到你~1. 题目解析简单来说:给你一个字符串,来让你判断这个字符串是不是完整的蛙叫,并且要求返回一个尽可能小的青蛙数量例如:编号输入输出解释示例 1croakcroak1一只青蛙呱呱两次示例 2crcoakroak2最少两只第一只crcoakroak第二只crcoakroak示例 3croakcrook-1不是croak的有效组合示例 4croakcroa-1有青蛙叫到一半就没了简单来说一只青蛙完整叫声顺序c → r → o → a → k遇到c要么启用一只空闲老青蛙要么新增一只青蛙遇到k代表这只青蛙叫完一轮青蛙释放出来可以重复使用中间顺序乱掉、叫到一半中断直接返回-1全程记录同时正在叫的青蛙峰值就是答案。提示约束1 croakOfFrogs.length 10^5字符串中的字符只有c、r、o、a或者k,并没有多余的字符这道题不就是相当于一个模拟的方法?题目要求我们数青蛙,我们进行模拟即可~2. 算法原理建立顺序映射c0r1o2a3k4代表蛙鸣的5个阶段。维护计数器数组统计处在每个阶段的青蛙数量。遍历字符串每一个字符如果是c阶段0如果有已经叫完k阶段空闲青蛙就复用没有空闲总青蛙数1。阶段0计数1。如果是其他字符r/o/a/k看前一个阶段有没有青蛙没有的话说明顺序非法直接返回-1。前一阶段计数减一当前阶段计数加一。当字符是k阶段4叫完了这只青蛙就会回到空闲池可以再次被使用。不断重复这个过程,直到遍历数组结束遍历结束必须保证除k阶段以外其他阶段全部为0。 返回目录3. 编写代码易错点:遍历结束之后一定要校验例如输入ccroak两个 c 开头后面只完成一次 croak有一只青蛙卡在 c 阶段没叫完应该返回-1很多人忘记这一步。k结束之后青蛙不是消失而是变成空闲可以重复再叫一遍 c不需要一直新增青蛙。字符顺序不能乱例如直接出现r前面没有c直接非法返回 - 1。classSolution{publicintminNumberOfFrogs(StringcroakOfFrogs){//转化为字符数组char[]scroakOfFrogs.toCharArray();//创建青蛙叫Stringtcroak;intnt.length();int[]hashnewint[n];//用来存储对应字符和对应字符的下标HashMapCharacter,IntegermapnewHashMap();for(inti0;in;i){map.put(t.charAt(i),i);}for(charch:s){if(cht.charAt(0)){//判断最后一个位置是否有青蛙叫完if(hash[n-1]!0){hash[n-1]--;//复用已经叫完的青蛙}hash[0];}else{//拿到对应字符的下标intindexmap.get(ch);//判断前一个字符是否有if(hash[index-1]0){return-1;}else{hash[index];hash[index-1]--;}}}//防止没有叫完的青蛙for(inti0;in-1;i){if(hash[i]!0){return-1;}}returnhash[n-1];}} 返回目录