一、外观数列
题目解析
对于这道题，给定一个n，要求我们返回外观数列的第n个元素。
所谓外观数列，countAndSay(n)是countAndSay(n-1)行程长度编码。
而行程长度编码，简单来说就是将一个字符串中连续相同字符，修改成出现的次数+字符。
例如：字符串"21" ： 2出现了一次，就变成了12，而1出现了一次，就变成了11。最终字符串就变成了1211。
算法思路
了解了题目大概要求，现在来看如何实现：
给定一个n，要求返回第n个外观数列，也就是对字符串"1"，进行n-1次行程编码。
所以，我们只需要实现一个字符串行程编码（也就是统计一个字符串中字符出现的次数，然后再跟上字符拼接上一个新的字符串即可）；
然后进行n-1次行程编码，就可以获得最终结果。
代码实现
class Solution {
public:
string countAndSay(int n) {
string ret = "1";
for (int i = 1; i < n; i++) // 进行n-1次编码
{
int l = 0, r = 0;
int sz = ret.size();
string tmp;
while (r < sz) {
while (r < sz && ret[r] == ret[l])
r++;
// 字符串拼接
tmp += (to_string(r - l) + ret[l]);
l = r;
}
ret = tmp;
}
return ret;
}
};二、数青蛙
题目解析
对于这道题，给定一个字符串croakOfFrogs，其中只包含c、r、o、a、k；
青蛙要像发送蛙鸣，就必须按照c、r、o、a、k的顺序，少一个字母都不能发送蛙鸣。
题目要求我们根据字符串croakFrogs中，所有蛙鸣所需要青蛙的最少数目。
注意：题目中明确说明，croakOfFrogs中不是由若干个有效的croak字符组成，就返回-1。（也就是说，在croakOfFrogs中。如果存在字符没有按照croak的顺序，或者缺少某一个字符，就返回-1）
算法思路
了解了这道题是什么意思，那如何求解呢？
思路：
对于这道题，遍历croakOfFrogs字符串肯定是必不可少的；
在遍历croakOfFrogs字符串的过程中，我们要判断当前字符串是否是满足条件的（按照croak顺序），还要统计需要青蛙的最少数量。
所以，这里我们就可以使用一个
hash表，hash表中统计的是：当前喊到了该字符的数量。在遍历到
i位置时：
- 如果该位置字符是
c：判断是否有青蛙已经喊到了k，如果喊道k，就可以让喊到k的青蛙再从c开始喊；（保证需要青蛙数量最少)；如果没有青蛙喊到k，就让一个新的青蛙从c开始喊。- 如果当前位置字符不是
c：此时，就要判断前面是否存在青蛙喊到了上一个字符（例如：当前位置是r，就要判断是否有青蛙喊到了c）如果有就让青蛙喊当前位置的字符；如果没有，就表示croakOfFrogs字符串不是有效的，就返回-1了。
描述完了整个过程，接下来就是将这个过程转换成代码：
首先，创建
hash表（这里使用vector<int>模拟hash表）。初始化hash表在遍历字符串之前，这里可以再创建一个
unordered_map（也就是hash表）index，其中存储字符和对应的下标。然后，遍历字符串
croakOfFrogs（"croak"字符串的长度为n）：
遍历到字符
c：当前字符对应的下标i（在hash表中对应的下标），hash[i]++;判断
hash[n-1]：如果hash[n-1] > 0，就hash[n-1]--;；否则就什么都不做。遍历到其他字符：当前字符对应下标
i，判断hash[i-1]：如果
hash[i-1] == 0，当前字符串不符合条件，返回-1；如果
hash[i-1] > 0，就hash[i-1]--; hash[i]++;。遍历完字符串
croakOfFrogs后，再遍历hash表（除'k'以外所有元素），如果存在值>0的就返回-1。最后，返回
hash[n-1]即可。
代码实现
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
string str = "croak";
int n = str.size();
vector<int> hash(n);unordered_map<char, int> index;for (int i = 0; i < n; i++)index.insert({str[i], i});for (auto& e : croakOfFrogs) {if (e == 'c') {if (hash[n - 1] > 0)hash[n - 1]--;hash[0]++;} else {int i = index[e];if (hash[i - 1] == 0)return -1;hash[i]++;hash[i - 1]--;}}for (int i = 0; i < n - 1; i++) {if (hash[i] > 0)return -1;}return hash[n - 1];}};本篇文章到这里就结束了，感谢支持
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws