模拟(数青蛙)(5)

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_mapchar, intindex;//前者是字符后者是字符的下标 string t croak; for(int j 0;j t.size();j) { index[t[j]] j;//把croak按顺序给上下标,c:0r: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_mapchar, 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]即可。四、关键细节映射的作用通过index将字符与下标绑定使得我们可以通过pos-1快速定位前一个字母的计数避免繁琐的 if-else 判断。重用机制遇到c时优先检查k的计数体现了最少青蛙的核心思想——尽可能复用已完成的青蛙。顺序验证非c字符必须依赖前一个字母的存在否则立即返回 -1保证了顺序的正确性。最终检查遍历结束后检查前四个字母的计数防止出现未完成的叫声如只有c没有后续。