模拟算法介绍
模拟就是依葫芦画瓢，题目中要求的操作是什么样的，用代码去实现这个操作即可。
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.提莫攻击
题目描述：提莫的攻击会让敌人进入中毒状态，一次攻击中毒的时间为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字型变化
题目解析：将字符串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.外观数列
题目解析：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.数青蛙
题目解析：一个完整的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'];
}
}