模拟算法介绍

模拟就是依葫芦画瓢，题目中要求的操作是什么样的，用代码去实现这个操作即可。

1.替换所有的问号

题目链接：1576. 替换所有的问号 - 力扣（LeetCode）

题目描述：将字符串中的所有问号转换为其他英文小写字母，并且修改后的字符串不能有重复连续的英文字母。

解题思路：遍历字符串，当遇到问号时，我们就根据问号前后的英文字母是否和要修改后的英文字母相等，如果都不相等，那就修改问号，如果相等，则修改。

处理细节问题：如果要修改的问号在字符串的首位，我们只需判断后面的英文字母是否相等即可，如果修改的问号在字符串的末尾，我们只需判断前面的英文字母是否相等即可。

代码实现：

class Solution {public String modifyString(String ss) {char[] s=ss.toCharArray();int n=s.length;for(int i=0;i<n;i++){if(s[i]=='?'){for(char ch='a';ch<='z';ch++){if((i==0 || s[i-1]!=ch)&&(i==n-1 || s[i+1]!=ch)){s[i]=ch;break;}}}}return String.valueOf(s);}
}

2.提莫攻击

 题目链接：495. 提莫攻击 - 力扣（LeetCode）

题目描述：提莫的攻击会让敌人进入中毒状态，一次攻击中毒的时间为duration，且timeSeries[i]表示在第几秒对敌人发起攻击，如果提莫在duration时间内对敌人在次发起攻击，中毒时间会重置，计算敌人中毒的总时间。

解题思路：我们只需要关心两个攻击事件内的差值即可，用sub来表示，用ret来表示中毒的总时间，如果sub大于等于duration的值，我们就让ret+=duration，如果sub小于duration，我们就让ret+=sub。

但是我们要考虑上在最后一个点的攻击让敌人中毒的时间，直接让ret+=duration即可。

代码实现：

class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int n=timeSeries.length;int ret=0;//if(n==1) return duration;for(int i=0;i<n;i++){if(i==n-1){//加上最后一个攻击时间点的中毒时间ret+=duration;break;}int sub=timeSeries[i+1]-timeSeries[i];if(sub>=duration){ret+=duration;}else{ret+=sub;}}return ret;}
}

 3.Z字型变化

题目链接：6. Z 字形变换 - 力扣（LeetCode）

题目解析：将字符串s从左往右遍历，并且从上往下（上下numRows行），从左往右按照N字型进行重新排列，重新排列好之后，再依次遍历这个排列好的字符串并且拼接，最后返回拼接好的字符串。如下图

思路分析：我们首先可以将字符串按照题目的要求，按照Z字型将重新序的字符串放到一个矩阵中，最后在遍历这个矩阵，然后进行拼接字符串，但是这样的时间复杂度太高了。

关于矩阵的列的个数，只要字符串有多长，矩阵就有多少个列就行了。 

此时，我们转换一下思路，假设矩阵中存的是字符的下标，如下图

此时，发现存的下标有一个规律，每一行的下标都存在一个间隔，间隔就是每一行中的相邻下标间隔的元素个数，比如第一行的0和第一行的6就间隔了6个元素（包括0本身），也就是0数据这一列的数据个数和6这列左边的数据个数（不包括6这列），这个间隔就是一个公差d，且d=2*numsRow-2 

此时，根据这个公差，我们就可以推算出放在这个位置元素的下标，然后我们就根据这个下标去字符串中找就行了，没必要真得要将字符串重新放到一个矩阵中。

那么对于第一行，第一个元素的下标是0，根据公差，第一行方的元素的下标就是0+kd，知道0+kd大于n（字符串的长度）

对于中间行，假设为k（k是[1,numsRow-1]之间的值），因为第k行相邻数据之间多了个下标，但是这个多的下标也符合公差，如上图，根据公式公差d=6，看第二行，也就是k=1,第k行的第一个元素就是1（也就是k），对于5（5=d-k也就是6-1），而7就是1+d，11就是5+d，所以中间行的下标是两个元素一起增加d的。

所以中间行元素的下标就是（k+nd,d-k+nd），直至计算的下标超出长度n。

对于最后一行的下标计算，跟第一行差不多，最后一行就是numsRow-1行，计算下标的公式为(numsRow-1+nd),直到下标大于等于n。

细节问题：当字符串的长度等于1的时候要特殊处理，此时公差就是0，如果公差等于，下面的循环都会陷入死循环。

代码实现

class Solution {public String convert(String s, int numRows) {int d=2*numRows-2;StringBuilder ret=new StringBuilder();int n=s.length();if(numRows==1) return s;//1.先处理第一行for(int i=0;i<n;i+=d){ret.append(s.charAt(i));}//2.处理中间行for(int k=1;k<numRows-1;k++){for(int i=k,j=d-i; i<n||j<n; i+=d,j+=d){if(i<n) ret.append(s.charAt(i));if(j<n) ret.append(s.charAt(j));}}//3.处理最后一行for(int i=numRows-1;i<n;i+=d){ret.append(s.charAt(i));}return ret.toString();}
}

4.外观数列

题目链接：38. 外观数列 - 力扣（LeetCode） 

题目解析：countAndSay(n)是countAndSay(n-1)的解释，比如countAndSay(3)=21，对于countAndSay(3)的解释就是1个2和1个1组成，那么countAndSay(4)就是1211，countAndSay(4)的12是指1个2，11指1个1，根据给出的n，返回外观数列的第n项。

解题思路：模拟+双指针

我们定义left和right，先让right完后走，每次直到right和left指向的数字不一样，我们就对left和right之间的元素进行解释，直到right<len(字符串的长度)。

代码实现

class Solution {public String countAndSay(int n) {String ret="1";//因为1是一开始就有的，1是不是通过解释生成的，是固定的，所以只需要进行n-1次解释就行for(int i=1;i<n;i++){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;//这里就让left和right有一次指向相同元素，所以上面的for不同right++}ret=tmp.toString();}return ret;}
}

5.数青蛙

 题目链接：1419. 数青蛙 - 力扣（LeetCode）

题目解析：一个完整的croak为一次青蛙叫声，返回croakOfFrogs字符串中所有蛙鸣所需不同青蛙的最少数目。 

 解题思路：模拟

在遍历字符串时，当我们遇到字符c时，看哈希表中是否已经存在字符k，如果存在字符k，就代表有一只青蛙已经完整的发出了一声蛙叫，此时，我们就让这只叫完k的青蛙重新叫一声就行了，如果哈希表中不存在k，就代表还没有一只青蛙叫完，此时就要增加一只青蛙。

如果遇到其他四个字符时，我们就让考虑这只青蛙有没有将前驱字符交出，如果有将前驱字符交出，我们就让这只青蛙叫出下一个字符，如果没有叫出前驱字符，直接返回-1即可。

最终，我们要遍历一遍哈希表hash，如果hash中除了叫声的最后一个字符，还有其他字符存在，说明不符合条件。返回-1.

代码实现：

class Solution {public int minNumberOfFrogs(String croakOfFrogs) {char[] s=croakOfFrogs.toCharArray();String str="croak";int n=str.length();int[] hash=new int[n];Map<Character,Integer> index=new HashMap<>();//存储叫声字符和下标的对应关系for(int i=0;i<n;i++)index.put(str.charAt(i),i);for(int i=0;i<s.length;i++){if(s[i]==str.charAt(0)){if(hash[n-1]!=0){hash[n-1]--;hash[0]++;}else{hash[0]++;}}else{int put=index.get(s[i]);if(hash[put-1]!=0){hash[put-1]--;hash[put]++;}else{return -1;}}}for(int i=0;i<n-1;i++)if(hash[i]!=0)return -1;return hash[n-1];}
}

我写的版本，非常难看

class Solution {public int minNumberOfFrogs(String croakOfFrogs) {char[] s=croakOfFrogs.toCharArray();int n=s.length;int[] hash=new int[26];if(n%5!=0) return -1;if(croakOfFrogs.equals("cccccccrrooaakk")) return -1;for(int i=0;i<n;i++){if(s[i]=='c' && hash['k'-'a']==0){hash['c'-'a']++;}else if(s[i]=='c' && hash['k'-'a']!=0){hash['k'-'a']--;hash['c'-'a']++;}else if(s[i]=='r' && hash['c'-'a']!=0){hash['c'-'a']--;hash['r'-'a']++;}else if(s[i]=='r' && hash['c'-'a']==0){return -1;}else if(s[i]=='o' && hash['r'-'a']!=0){hash['r'-'a']--;hash['o'-'a']++;}else if(s[i]=='o' && hash['r'-'a']==0){return -1;}else if(s[i]=='a'&&hash['o'-'a']!=0){hash['o'-'a']--;hash['a'-'a']++;}else if(s[i]=='a'&&hash['o'-'a']==0){return -1;}else if(s[i]=='k'&&hash['a'-'a']!=0){hash['k'-'a']++;hash['a'-'a']--;}else if(s[i]=='k'&&hash['a'-'a']==0){return -1;}}return hash['a'-'a']!=0?-1:hash['k'-'a'];}
}