力扣算法--数青蛙与外观数列问题
引言
在力扣（LeetCode）的算法练习中，“数青蛙”和“外观数列”是两道很有意思的中等难度题目，它们分别从字符串的逻辑校验与计数、递归与字符串压缩的角度，考察我们对算法的理解和运用。本文将带大家深入剖析这两道题的解题思路与实现方法。
一、数青蛙（LeetCode 1419）
题目剖析
我们需要处理一个表示青蛙蛙鸣的字符串，判断其是否由有效“croak”组合而成，若有效，返回模拟这些蛙鸣所需不同青蛙的最少数目；若无效，返回 -1 。青蛙发出“croak”需依次输出 'c'、'r'、'o'、'a'、'k' 这 5 个字符，且要保证字符顺序和完整性。
解题思路
1. 初始化辅助结构：定义目标蛙鸣字符串 "croak"，创建哈希数组 hash 记录每个阶段（对应 "croak" 每个字符位置）的青蛙数量，用 unordered_map 存储每个字符在目标字符串中的下标，方便快速查找。
2. 遍历处理输入字符串：
- 遇到 'c' 时，先查看是否有完成一轮“croak”（处于 'k' 阶段，即 hash 最后一个元素）的青蛙，若有则复用（该阶段数量减 1 ），然后增加 'c' 阶段数量；
- 遇到其他字符时，检查前一阶段数量是否为 0 ，为 0 说明字符顺序混乱，返回 -1 ，否则前一阶段数量减 1 ，当前阶段数量加 1 。
3. 结果验证与返回：遍历 hash 数组（除最后一个元素），若有非 0 值，说明蛙鸣不完整，返回 -1 ；否则返回最后一个元素值，即所需最少青蛙数。
代码实现class Solution { public:int minNumberOfFrogs(string croakOfFrogs) {string tmp = "croak";int n = tmp.size();vector<int> hash(n, 0);unordered_map<char, int> index;for (int i = 0; i < n; ++i) {index[tmp[i]] = i;}int maxFrogs = 0;for (char e : croakOfFrogs) {int idx = index[e];if (e == 'c') {if (hash[n - 1] > 0) {hash[n - 1]--;}hash[idx]++;maxFrogs = max(maxFrogs, hash[0]);} else {int prevIdx = idx - 1;if (hash[prevIdx] == 0) {return -1;}hash[prevIdx]--;hash[idx]++;}}for (int i = 0; i < n - 1; ++i) {if (hash[i] != 0) {return -1;}}return maxFrogs;} };
二、外观数列（LeetCode 38）
题目剖析
外观数列由递归公式定义， countAndSay(1) = "1" ， countAndSay(n) 是 countAndSay(n - 1) 的行程长度编码（RLE），需要根据给定整数 n ，返回外观数列的第 n 个元素。行程长度编码是把连续相同字符替换为重复次数和该字符的串联。
解题思路
1. 初始化：从第 1 项 "1" 开始。
2. 迭代推导：循环 n-1 次，每次对当前字符串做「计数 + 描述」：
- 用双指针 left / right 找连续相同字符的区间。
- 拼接区间长度和字符，生成新字符串。
3. 返回结果：迭代完成后，得到第 n 项的外观数列。
本质是用迭代模拟行程长度编码（RLE），逐步推导结果，逻辑清晰高效 。
代码实现class Solution { public:string countAndSay(int n) {string ret="1";for(int i=1;i<n;i++){string tmp;for(int left=0,right=0;right<ret.size();){while(right<ret.size()&&ret[right]==ret[left])right++;tmp+=to_string(right-left)+ret[left];left=right;}ret=tmp;}return ret;} };
三、总结
“数青蛙”题主要围绕字符串字符的顺序校验与计数逻辑，考察对复杂条件下字符串处理的能力；“外观数列”题则结合递归与行程长度编码，让我们体会到递归思想在字符串处理中的应用。通过练习这类题目，能有效提升我们分析问题、运用算法解决实际场景的能力，大家可以多在力扣上尝试不同解法，加深对算法的理解。