《算法题讲解指南：优选算法-模拟》--41.外观数列，42.数青蛙

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

41.外观数列

题目链接：

题目描述：

题目示例：

解法（模拟）：

算法思路：

C++算法代码：

算法总结及流程解析：

42.数青蛙

题目链接：

题目描述：

题目示例：

解法（模拟+分情况讨论）：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

41.外观数列

题目链接：

38. 外观数列 - 力扣（LeetCode）

题目描述：

题目示例：

解法（模拟）：

算法思路：

      所谓【外观数列】，其中只是依次统计字符串中连续且相同的字符的个数。依据题意，依次模拟即可。

C++算法代码：

class Solution { public: // string func(string s) // { // string ret; // int left = 0, right = 0, len = 0; // while(right < s.size()) // { // if(s[right] == s[left]) // { // right++; // } // else // { // len = right - left; // ret += to_string(len); // ret += s[left]; // left = right; // } // } // len = right - left; // ret += to_string(len); // ret += s[left]; // return ret; // } string countAndSay(int n) { // string ret = "1"; // while(--n) // { // ret = func(ret); // } // return ret; string ret = "1"; while(--n) { string s; //巧妙用一下双指针来获取相同数字的长度 int left = 0, right = 0, len = 0; while(right < ret.size()) { if(ret[right] == ret[left]) { right++; } else { len = right - left; s += to_string(len);//to_string可以将数字转换出字符 s += ret[left]; left = right; } } len = right - left; s += to_string(len); s += ret[left]; ret = s; } return ret; } };

算法总结及流程解析：

42.数青蛙

题目链接：

1419. 数青蛙 - 力扣（LeetCode）

题目描述：

题目示例：

解法（模拟+分情况讨论）：

算法思路：

      模拟青蛙的叫声。

• 当遇到 'r'  'o'  'a'  'k' 这四个字符的时候，我们要去看看每一个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那么就让这个青蛙接下来喊出这个字符；如果没有，直接返回 -1；
• 当遇到 ‘c’ 这个字符的时候，我们去看看 ‘k’ 这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去 ‘c’ 这个字符；如果没有的话，就重新整一个青蛙出来

C++算法代码：

class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { // //暴力算法：模拟 // //通过一个数组hash模拟存放croak这五个字母 // int n = croakOfFrogs.size(); // vector<int> hash(5, 0); // for(int i = 0; i < n; i++) // { // if(croakOfFrogs[i] == 'c') // { // if(hash[4]) // { // hash[4]--; // } // hash[0]++; // } // else if(croakOfFrogs[i] == 'r') // { // if(hash[0]-- == 0) // { // return -1; // } // hash[1]++; // } // else if(croakOfFrogs[i] == 'o') // { // if(hash[1]-- == 0) // { // return -1; // } // hash[2]++; // } // else if(croakOfFrogs[i] == 'a') // { // if(hash[2]-- == 0) // { // return -1; // } // hash[3]++; // } // else // { // if(hash[3]-- == 0) // { // return -1; // } // hash[4]++; // } // } // for(int i = 0; i < hash.size() - 1; i++) // { // if(hash[i] != 0) // { // return -1; // } // } // return hash[4]; //代码优化：使用一个哈希表存放croak在数组hash中对应的下标，便于快速访问 //就可以不用像上面那样用五个if else来分别判断 string s = "croak"; int n = s.size(); vector<int> hash(n, 0);//用数组模拟哈希表hash来存放croak几个字符 unordered_map<char, int> index; //存放字符所对应在数组hash中的下标 for(int i = 0; i < n; i++) { index[s[i]] = i; } for(int i = 0; i < croakOfFrogs.size(); i++) { int x = index[croakOfFrogs[i]]; //获取到当前字符的下标 if(x != 0) //当前字符为r、o、a、k { if(hash[x - 1]-- == 0) { return -1; } hash[x]++; } else//当前字符为c { if(hash[n - 1]) { hash[n - 1]--; } hash[x]++; } } //如果遍历完字符串后数组hash中除了最后一位k有值， //还有其他字符也有值，则说明有传声还没有完成，则返回-1 for(int i = 0; i < n - 1; i++) { if(hash[i] != 0) { return -1; } } return hash[n - 1]; } };

算法总结及流程解析：

结束语

      到此，41.外观数列，42.数青蛙 这两道算法题就讲解完了。外观数列：模拟统计连续相同字符的个数并生成新字符串。通过双指针计数，迭代n-1次得到结果。数青蛙：通过模拟青蛙叫声过程，分析字符序列croak的匹配逻辑。算法使用哈希表记录字符位置，并动态维护各阶段字符计数：当遇到c时复用已完成k的青蛙或新增青蛙；其他字符则需前驱字符存在才能继续。最后检查未完成序列的青蛙数量。希望大家能有所收获！