目录

外观数列(medium)

题目解析

讲解算法原理

编写代码

数⻘蛙（medium）

题目解析

讲解算法原理

编写代码

---

外观数列(medium)

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定⼀个正整数n，输出外观数列的第n项。
「外观数列」是⼀个整数序列，从数字1开始，序列中的每⼀项都是对前⼀项的描述。你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1)="1"
countAndSay(n)是对countAndSay(n-1)的描述，然后转换成另⼀个数字字符串。
前五项如下：1. 1
2. 11
3. 21
4. 1211
5. 111221
第⼀项是数字1描述前⼀项，这个数是1即“⼀个1”，记作"11"描述前⼀项，这个数是11即“⼆个1”，记作"21"描述前⼀项，这个数是21即“⼀个2+⼀个1”，记作"1211"描述前⼀项，这个数是1211即“⼀个1+⼀个2+⼆个1”，记作"111221"要描述⼀个数字字符串，⾸先要将字符串分割为最⼩数量的组，每个组都由连续的最多相同字符
组成。然后对于每个组，先描述字符的数量，然后描述字符，形成⼀个描述组。要将描述转换为数字字符串，先将每组中的字符数量⽤数字替换，再将所有描述组连接起来。
例如，数字字符串"3322251"的描述如下图：

⽰例1：输⼊：n=1输出："1"解释：这是⼀个基本样例。
⽰例2：输⼊：n=4输出："1211"解释：
countAndSay(1)="1"
countAndSay(2)=读"1"=⼀个1="11"
countAndSay(3)=读"11"=⼆个1="21"
countAndSay(4)=读"21"=⼀个2+⼀个1="12"+"11"="1211"
提⽰：
1<=n<=30

讲解算法原理

解法（模拟）：
算法思路：
所谓「外观数列」，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。

编写代码

c++算法实现：

class Solution
{
public:string countAndSay(int n) {string ret = "1";for(int i = 1; i < n; i++) // 解释 n - 1 次 ret 即可{string tmp;int len = ret.size();for(int left = 0, right = 0; right < len; ){while(right < len && ret[left] == ret[right]) right++;tmp += to_string(right - left) + ret[left];left = right;}ret = tmp;}return ret;}
};

java算法实现：

class Solution
{public String countAndSay(int n) {String ret = "1";for(int i = 1; i < n; i++) // 解释 n - 1 次 ret 即可{StringBuilder tmp = new StringBuilder();int len = ret.length();for(int left = 0, right = 0; right < len; ){while(right < len && ret.charAt(left) == ret.charAt(right)) 
right++;tmp.append(Integer.toString(right - left));tmp.append(ret.charAt(left));left = right;}ret = tmp.toString();}return ret;}
}

 

数⻘蛙（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个字符串croakOfFrogs，它表⽰不同⻘蛙发出的蛙鸣声（字符串"croak"）的组合。由于同⼀时间可以有多只⻘蛙呱呱作响，所以croakOfFrogs中会混合多个“croak”。
请你返回模拟字符串中所有蛙鸣所需不同⻘蛙的最少数⽬。要想发出蛙鸣"croak"，⻘蛙必须依序输出‘c’,’r’,’o’,’a’,’k’这5个字⺟。如果没
有输出全部五个字⺟，那么它就不会发出声⾳。如果字符串croakOfFrogs不是由若⼲有效的"croak"字符混合⽽成，请返回-1。
⽰例1：
输⼊：croakOfFrogs="croakcroak"输出：1
解释：⼀只⻘蛙“呱呱”两次⽰例2：
输⼊：croakOfFrogs="crcoakroak"输出：2
解释：最少需要两只⻘蛙，“呱呱”声⽤⿊体标注
第⼀只⻘蛙"crcoakroak"第⼆只⻘蛙"crcoakroak"
⽰例3：
输⼊：croakOfFrogs="croakcrook"输出：-1
解释：给出的字符串不是"croak"的有效组合。
提⽰：
1<=croakOfFrogs.length<=105
字符串中的字符只有'c','r','o','a'或者'k'

讲解算法原理

解法（模拟+分情况讨论）
算法思路：
模拟⻘蛙的叫声。
◦ 当遇到 'r' 'o' 'a' 'k' 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，
有没有⻘蛙叫出来。如果有⻘蛙叫出来，那就让这个⻘蛙接下来喊出来这个字符；如果没有，直接返回 -1 ；
◦ 当遇到 'c' 这个字符的时候，我们去看看 'k' 这个字符有没有⻘蛙叫出来。如果有，就让
这个⻘蛙继续去喊 'c' 这个字符；如果没有的话，就重新搞⼀个⻘蛙。

编写代码

c++算法实现：

class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";int n = t.size();vector<int> hash(n); // ⽤数组来模拟哈希表unordered_map<char, int> index; //[x, x这个字符对应的下标] for(int i = 0; i < n; i++)index[t[i]] = i;for(auto ch : croakOfFrogs){if(ch == 'c'){if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;}else{int i = index[ch];if(hash[i - 1] == 0) return -1;hash[i - 1]--; hash[i]++;}}for(int i = 0; i < n - 1; i++)if(hash[i] != 0)return -1;return hash[n - 1];}
};

java算法实现：

class Solution
{public int minNumberOfFrogs(String c) {char[] croakOfFrogs = c.toCharArray();String t = "croak";int n = t.length();int[] hash = new int[n]; // 数组模拟哈希表Map<Character, Integer> index = new HashMap<>(); // [x, x这个字符对应的下标]for(int i = 0; i < n; i++)index.put(t.charAt(i), i);for(char ch : croakOfFrogs){if(ch == t.charAt(0)){if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;}else{int i = index.get(ch);if(hash[i - 1] == 0) return -1;hash[i - 1]--; hash[i]++;}}for(int i = 0; i < n - 1; i++)if(hash[i] != 0)return -1;return hash[n - 1];}
}