【优选算法】模拟算法：替换所有的问号，提莫攻击，N字形变换，外观数列，数青蛙
文章目录
1. 替换所有的问号（LC1576）
题目描述
解题思路
按照题目要求，双层循环，外层遍历字符串；内层从a到z依次尝试，与前后不等则填入。
代码实现
publicStringmodifyString(String s){char[] ss = s.toCharArray();int n = ss.length;for(int i =0;i<n;i++){if(ss[i]!='?')continue;for(char ch ='a';ch<='z';ch++)if((i==0|| ch!=ss[i-1])&&(i==n-1||ch!=ss[i+1])){ ss[i]= ch;break;}}returnnewString(ss);}2. 提莫攻击（LC495）
题目描述
解题思路
计算两次“受到攻击”之间的差值x
x >= d，则ret+=dx < d，则ret+=x
最后要加上一个d，表示最后一次“攻击”的时间
代码实现
publicintfindPoisonedDuration(int[] timeSeries,int duration){int ret =0;for(int i =1;i<timeSeries.length;i++){int x = timeSeries[i]-timeSeries[i-1]; ret +=(x>=duration)?duration:x;} ret += duration;return ret;}3. N字形变换（LC6）
题目描述
解题思路
- 解法二：依据模拟过程找规律，把字符的下标模拟到矩阵中：
- 第0行：公差就是一个周期中字符个数
d = n + n - 2 = 2n - 2- 0 -> 0+d -> 0+2d -> 0+3d -> …-> 0+kd
- 第i行：一个周期内有两个元素
- i -> i+d -> i+2d -> … -> i+kd
- d - i -> d - i +d -> d - i + 2d -> … -> d - i + kd
- 第n-1行:
- 第0行：公差就是一个周期中字符个数
n-1 -> n-1+d -> n-1+2d -> … ->n-1+kd
解法一：创建二维数组，按照N形依次填入。时间复杂度和空间复杂度都是字符串长度*numRow
注意： n=1直接返回原字符串，按照上面的规律会陷入死循环。
代码实现
publicStringconvert(String s,int numRows){if(numRows==1)return s;StringBuilder ret =newStringBuilder();int n = s.length();int d =2*numRows -2;//公差int n1 =(n+d-1)/d;//周期个数，向上取整//第0行for(int k =0;k<n1;k++) ret.append(s.charAt(k*d));//中间行for(int i =1;i<numRows-1;i++){for(int k =0;k<n1;k++){if(i+k*d<n) ret.append(s.charAt(i+k*d));if(d-i + k*d<n) ret.append(s.charAt(d-i + k*d));}}//最后一行for(int k =0;k<n1;k++){if(numRows-1+k*d<n) ret.append(s.charAt(numRows-1+k*d));}return ret.toString();}4. 外观数列（LC38）
题目描述
解题思路
利用双指针来模拟过程：left，right初始为0
- right 向右 移动，直到与left指向的字符不同，停止移动
- right - left就是中间的个数，接着left移动到right的位置，循环这个过程
代码实现
publicStringcountAndSay(int n){String s ="1";for(int i =1;i<n;i++){StringBuilder tmp =newStringBuilder();int len = s.length();int count =0;for(int left =0,right=0; right<len;){while(right<len && s.charAt(left)==s.charAt(right)) right++; tmp.append(String.valueOf(right-left)); tmp.append(s.charAt(left)); left = right;} s = tmp.toString();}return s;}5. 数青蛙（LC1419）
题目描述
解题思路
使用哈希表来存c r o a k每个字符：
- 遇到
r o a k这四个字符的时候，看每⼀个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符；如果没有，直接返回 -1 ； - 遇到
c这个字符的时候，看 ‘k’ 这个字符有没有青蛙叫出来。如果有，就让
这个青蛙继续去喊c这个字符；如果没有，就重新搞⼀个青蛙。
代码实现
publicintminNumberOfFrogs(String c){char[] croakOfFrogs = c.toCharArray();int[] croak =newint[5];String s ="croak";Map<Character,Integer> index =newHashMap<>();for(int i =0;i<5;i++) index.put(s.charAt(i),i);for(char ch:croakOfFrogs){if(ch =='c'){if(croak[4]!=0) croak[4]--; croak[0]++;}else{int i = index.get(ch);if(croak[i-1]!=0){ croak[i-1]--; croak[i]++;}elsereturn-1;}}for(int i =0;i<4;i++){if(croak[i]!=0)return-1;}return croak[4];}
