目录。

前言。

38. 外观数列。

算法分析。

算法思路。

算法代码。

1419. 数青蛙。

算法分析。

算法思路。

算法代码。

 2671. 频率跟踪器。

算法分析。

算法思路。

算法代码。

前言。

我们已经解释了什么是模拟算法，本文主要讲解leetcode上遇到的一些模拟问题~。

38. 外观数列。

算法分析。

事实上，这个问题是用字符重复的次数代替连续和相同的字符+字符，我们可以举个例子：假设我们现在有11322，然后我们将其压缩�将获得“212322”（按照我们的口头说法，有两个1，两个3，2）。此外，标题还提供了字符串编码序列的递归公式：

• countAndSay（1）=“1”。
• countAndSay（n）countandSay（n-1）行程长度编码，简单来说，countandSay就是count(n-1)字符串按口头形式压缩。

countAndSay（n）countandSay（n-1）行程长度编码，简单来说，countandSay就是count(n-1)字符串按口头形式压缩。

算法思路。

1. 所以对于这个问题：
2. 创建StringBuffer类󿄚创建retstringbufer类并初始化为“1”。
3. ret遍历n次：在遍历过程中，首先需要三个变量，Stringbuffer（tmp;用于存储每次获得的编码），count（有多少个）用于累积与ch相同的字符？;，字符ch（用于取s字符串中的字符）。࿰遍历时c;通过内循环，判断有多少个和ch一样。每次ret后，我们需要给ret赋值tmp字符串。在遍历时，通过内循环，判断有多少个和ch一样。每次ret后，我们需要给ret赋值tmp字符串。

返回结果：当遍历完成后，此时我们可以返回ret。

算法代码。

class Solution { /** * 生成“说数”序列中的第一个 n 项。 * “说数”序列是一个特殊的序列，每一项都是对前一项的描述。 * 例如： * countAndSay(1) 返回 "1"（只有一个数字） * countAndSay(2) 返回 "11"（前一项 "1" 被读作 “一 一、） * countAndSay(3) 返回 "21"（前一项 "11" 被读作 “两 一、） * countAndSay(4) 返回 "1211"（前一项 "21" 被读作 “一 2，然后一 一、） * 以此类推。 * * @param n 项序列中的顺序号，为整型。 * * @param n 项序列中的顺序号，为整型。 * @return 第 n 项目“说数”序列，以字符串的形式。 */ public String countAndSay(int n) { StringBuffer ans = new StringBuffer("1"); for (int i = 1; i < n; i++) { StringBuffer tmp = new StringBuffer(); int size = ans.length(); for (int j = 0; j < size;) { // 从第一个字符开始󿀌统计连续相同字符的数量，并将此数量和字符本身添加到临时字符串缓冲区。 int count = 0; char c = ans.charAt(j); while (j < size && ans.charAt(j) == c) { count++; j++; } tmp.append(count); tmp.append(c); } ans = tmp; } return ans.toString(); } }。

1419. 数青蛙。

1419. 数青蛙。算法分析。

简单来说，这个问题就是找croak字符串是否连续出现，如果是连续出现，这意味着我们只需要一只青蛙。但如果不是连续出现，其他字符（穿插在中间;字符）按照croak顺序出现;，所以可能需要更多的青蛙。

算法思路。

算法代码。

class Solution { public int minNumberOfFrogs(String croakOfFrogs) { //将 croakOfFrogs 转换为字符数组󿀌方便操作 char[] chars=croakOfFrogs.toCharArray(); String ret="croak"; int n=ret.length(); ///用int数组模拟hash表 int[] hash=new int[n]; //创建Map，存储字符，以及字符的下标 Map<Character,Integer> map=new HashMap<>(); for(int i=0;i<n;i++) map.put(ret.charAt(i),i); //进行遍历 for(char ch:chars){ //判断c if(ch=='c'){ ///判断前k字符是否为0，为0就只++ch，否则k也要减1 if(hash[n-1]!=0) hash[n-1]--; hash[0]++; }else{ ///判断字符的下标 int index=map.get(ch); if(hash[index-1]==0) return -1; hash[index-1]--; hash[index]++; } } for(int i=0;i<n-1;i++){ if(hash[i]!=0) return -1; } return hash[n-1]; }}。=0) return -1; } return hash[n-1]; }}。

 2671. 频率跟踪器。

算法分析。

这个问题要求我们实现FrequencyTracker类的方法。所以我们实际上可以和第二道类似󿀌我们可以用两个哈希表来解决这个算法问题。

• 算法思路。
• 初始化：首先，让我们在类中声明两个整形数组，用作哈希表。hash1用于存储数字的次数，hash2是用来存储频率和频率的映射关系。

• 实现add方法：当有人调用这种方法࿰时c;所以这个时候，hash2[hash[number]]，即出现频率-1，hash1[number]要+1，然后再让 hash2[hash[number]]再+1。[仍以上示例为前提，假设我现在调用ad，number=1，然后说明hash1中的number=1.下标元素+1，但是在+1后，此时࿰为1c;它的元素是3，然后我们需要记录hash2中出现次数的元素-1（--hash2[hash[number]]），hash1在执行之后[number]+1后，更新频率（++hash2[hash[number]]）。
• 实现deleteone方法：首先，我们需要判断，hash1中以number为底的元素是0࿰吗？c;若为0直接返回。相反，我们需要类似于add方法，先在hash2中让hash1[number]下标元素-1 ，再让hash1[number]-1.让hash2中的hash1[number]下标元素+1.。

hashFrequency方法a;直接返回hash2[frequency]可以，判断是否大于0。

hashfrequence方法：直接返回hash2[frequency]可以，同时判断是否大于0。

算法代码。

/** * 频率跟踪器，用于跟踪整数组中每个数字的频率 * 具有特定频率的数字是否存在 */class FrequencyTracker { // 哈希表，存储每个数字出现的频率 private int[] hash1; // 哈希表，存储每个频率出现的次数 private int[] hash2; /** * 构造函数󿀌两个哈希表数组的初始化 */ public FrequencyTracker() { hash1 = new int[10001]; hash2 = new int[10001]; } /** * 在向跟踪器中添加数字，数字频率和频率的出现频率相应更新 * * @param number 要添加的数字 */ public void add(int number) { // 当前数字对应的频率为-1，因为我们需要增加这个数字的频率 --hash2[hash1[number]]; // 然后实际增加这个数字的频率 ++hash1[number]; // 最后，增加新的频率计数 ++hash2[hash1[number]]; } /** * 删除跟踪器中的数字，数字频率和频率的出现频率相应更新 * * @param number 要删除的数字 */ public void deleteOne(int number) { if (hash1[number] == 0) return; // 当前数字对应的频率为-1，因为我们即将降低这个数字的频率 --hash2[hash1[number]]; // 然后实际降低这个数字的频率 --hash1[number]; // 最后，减少新的频率计数 ++hash2[hash1[number]]; } /** * 检查具有给定频率的数字是否存在 * * @param frequency 检查目标频率 * @return 如果存在具有给定频率的数字，返回true；否则，返回false */ public boolean hasFrequency(int frequency) { return hash2[frequency] > 0; }}。