【算法系列篇】模拟算法-1：https://developer.aliyun.com/article/1430524
4. 外观数列
https://leetcode.cn/problems/count-and-say/
4.1 题目要求
给定 ，输出外观数列的第 n 项对前一项的描述。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1
11
21
1211
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
class Solution { public String countAndSay(int n) { } }
4.2 做题思路
这道题可以使用双指针来管理相同数字的区间，left 指针和 right 指针都从 0 位置开始，当 right 所指向的内容和 left 所指的内容相同时，right 继续向后移，如果不相等，则可以更新字符串中的内容，更新完成之后，left 指针指向 right 指针所指的位置，然后 right 指针继续向后移动，直到 right 指向字符串的末尾。
4.3 Java代码实现
class Solution { public String countAndSay(int n) { String ret = "1"; for(int i = 1; i < n; i++) { StringBuilder tmp = new StringBuilder(); int left = 0, right = 0; while(right < ret.length()) { while(right < ret.length() && 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; } }
5. 数青蛙
https://leetcode.cn/problems/minimum-number-of-frogs-croaking/
5.1 题目要求
给你一个字符串 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’
class Solution { public int minNumberOfFrogs(String croakOfFrogs) { } }
5.2 做题思路
这道题目的意思是根据叫声来判断最少的青蛙数，那么如何才能判断是否是青蛙呢？就根据他的叫声，当听到 ‘c’ 的时候，如果后面依次出现’r’ ‘o’ ‘a’ ‘k’ 字符，那么这就可以算作一个青蛙，如果在 croak 后面又出现了 croak ，可以认为是一只青蛙叫了两声,“croakcroak”，但是如果在第一只青蛙叫的过程中又出现了 ‘c’ 的时候，这只能是第二只青蛙的叫声——“crocakroak”，这就是有两只青蛙 。因为‘c’ ‘r’ ‘o’ ‘a’ ‘k’ 需要是按顺序出现，所以当遇到 ‘r’ 的时候，需要知道前面 ‘c’ 是否出现了最少一次，后面的 ‘o’ ‘a’ ‘k’ 也是如此，如果前面的字母并没有出现，就直接返回 -1。
但是这样做的话，统计的不是最少的青蛙数，如果想要统计出最少的青蛙数，当遇到 ‘c’ 字符的时候，可以判断字符 ‘k’ 是否存在，如果存在就说明一个青蛙已经叫完了，它可以再叫第二声，也就是 k 的数量–，c 的数量++。
5.3 Java代码实现
class Solution { public int minNumberOfFrogs(String croakOfFrogs) { String s = "croak"; int n = s.length(); Map<Character,Integer> map = new HashMap<>(); //这个哈希表中存放叫声对应的字符和下标 for(int i = 0; i < n; i++) { map.put(s.charAt(i),i); } //这个哈希表用来统计字符出现的次数，也就是模拟出蛙叫的过程 int[] hash = new int[n]; for(int i = 0; i < croakOfFrogs.length(); i++) { char ch = croakOfFrogs.charAt(i); //当遇到 'c' 字符的时候，需要判断 'k' 字符是否出现 if(map.get(ch) == 0) { if(hash[n - 1] != 0) { hash[n - 1]--; hash[0]++; }else { hash[0]++; } }else { if(hash[map.get(ch) - 1] == 0) return -1; hash[map.get(ch) - 1]--; hash[map.get(ch)]++; } } //当字符串遍历完之后，如果除 k 位置可以不为0之外，其他字符位置数量如果不为0， //则说明有不正确的叫声，直接返回-1 for(int i = 0; i < n - 1; i++) { if(hash[i] != 0) return -1; } return hash[n-1]; } }
总结
在本篇博客中，我们深入探讨了模拟算法的定义、应用和实现。模拟算法是一种强大的工具，可以帮助我们模拟复杂系统、解决优化问题以及验证和测试系统的行为。
通过模拟算法，我们可以模拟现实世界中的各种过程、系统或现象，并生成与真实情况相似的结果。这使得我们能够更好地理解和预测复杂系统的行为，优化解决方案，并验证系统的正确性和性能。
在设计和实现模拟算法时，我们需要选择适当的模型，定义合适的步骤和规则，并进行数据收集和结果分析。这些步骤的正确性和准确性对于生成可靠的模拟结果至关重要。
模拟算法在多个领域中有着广泛的应用，包括科学研究、工程设计、优化和决策等方面。它们为我们提供了一种强大的工具，可以帮助我们理解和探索复杂系统的行为，并支持我们做出更加明智的决策。
尽管模拟算法有着诸多优点，但我们也要认识到它们的局限性。模拟算法往往基于假设和简化，可能无法完全精确地模拟现实情况。因此，在使用模拟算法时，我们需要谨慎地评估结果的可靠性，并结合领域知识和实际数据进行综合分析。
总而言之，模拟算法是一种强大的计算机算法，通过模拟目标对象的行为和规则来生成与真实情况相似的结果。它在科学研究、工程设计、优化和决策等领域中扮演着重要角色。通过善用模拟算法，我们可以更好地理解和应对复杂系统，为未来的发展和创新提供有力支持。
