【算法专场】模拟（下）

前言

38. 外观数列

算法分析

算法思路

算法代码

1419. 数青蛙

算法分析

算法思路

算法代码

2671. 频率跟踪器

算法分析

算法思路

算法代码

前言

在前面我们已经讲解了什么是模拟算法，这篇主要是讲解在leetcode上遇到的一些模拟题目~

38. 外观数列

算法分析

这道题其实就是要将连续且相同的字符替换成字符重复的次数+字符，我们可以举个例子：假设现在我们有113322，那么我们将其压缩，就会得到“212322”（按照我们口头来说的话，就是有2个1，2个3，2个2）。并且题目给了我们字符串的编码序列的递归公式：

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

算法思路

那么对于这道题：

创建StringBuffer类：创建一个ret的StringBuffer类并初始化为“1”
将ret遍历n遍：在遍历的过程中，我们首先需要三个变量，一个tmp的StringBuffer类（用来存储每次遍历得到的编码），一个count（用来累加与ch相同的字符有多少个），一个字符ch（用来取s字符串中的字符）。在遍历的时候，通过一个内循环，来判断和ch相同的有多少个.当遍历完每一次ret后，我们需要将tmp字符串赋值给ret。
返回结果：当遍历完成后，此时我们返回ret即可。

算法代码

class Solution {/*** 生成“说数”序列中的第 n 项。* “说数”序列为一个特殊的序列，其中每一项都是对前一项的描述。* 例如：* countAndSay(1) 返回 "1"（只有一个数字）* countAndSay(2) 返回 "11"（前一项 "1" 被读作 “一 1”）* countAndSay(3) 返回 "21"（前一项 "11" 被读作 “两 1”）* countAndSay(4) 返回 "1211"（前一项 "21" 被读作 “一 2，然后一 1”）* 以此类推。** @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. 数青蛙

算法分析

这道题简单的来说就是要我们找croak字符串是不是连续出现的，如果是连续出现的，则说明此时我们只需要1只青蛙即可。但如果不是连续出现的，中间穿插了其他的字符（且是按照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){//判断cif(ch=='c'){//判断前面k字符是否为0，为0就只++ch，否则k也要减1if(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];}}

2671. 频率跟踪器

算法分析

这道题要求我们将FrequencyTracker类中的方法实现。那么我们可以其实可以与第二道类似，我们可以利用两个哈希表来解决这道算法题。

算法思路

初始化：首先我们先在类中声明两个整型数组，当做哈希表来用。hash1用来存储数字出现的次数，hash2则是用来存储出现的次数和频率的映射关系。
实现add方法：当有人调用该方法，那么此时对于此时hash2[hash[number]]，即出现的频率要-1，对于hash1[number]要+1，然后再让 hash2[hash[number]]再+1。【依旧是以上面的例子为前提，假设我现在调用add，number=1，那么就说明在hash1中以number=1为下标的元素要+1，但是在+1后，此时对于1来说，它的元素就为3，那么我们就需要将本来在hash2中记录1出现次数的元素-1（--hash2[hash[number]]），在执行完hash1[number]+1后，再更新一下频率（++hash2[hash[number]]）。

实现deleteone方法：我们首先需要判断一下，在hash1中以number为底的元素是不是为0，若为0直接返回。反之我们则需要跟add方法类似，先在hash2中让以hash1[number]为下标的元素-1 ，再让hash1[number]-1,再让在hash2中让以hash1[number]为下标的元素+1.
实现hashFrequency方法：直接返回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;}
}