6.优化算法之模拟

1.替换所有的问号

. - 力扣（LeetCode）

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

2.提莫攻击 

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的 总 秒数。

 

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int ret=0;for(int i=0;i<timeSeries.length-1;i++){int x=timeSeries[i+1]-timeSeries[i];if(x>=duration){ret=ret+duration;}else{ret=ret+x;}}return ret+duration;}
}

3.Z字形变换

6. Z 字形变换 - 力扣（LeetCode）

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

 解法一：模拟

解法二：找规律 

class Solution {public static String convert(String s, int numRows) {int n=s.length(),r=numRows;if(r==1||r>=n){return s;}StringBuffer[] mat=new StringBuffer[r];for(int i=0;i<r;i++){mat[i]=new StringBuffer();}for(int i=0,x=0,t=2*r-2;i<n;i++){mat[x].append(s.charAt(i));if(i%t<r-1){//每一个数组框其实代表着每一行所需要打印的数据++x;}else{--x;}}StringBuffer ans=new StringBuffer();for(StringBuffer row:mat){ans.append(row);}return ans.toString();}
}

 

4.外观数列

. - 力扣（LeetCode）

class Solution {public String countAndSay(int n) {String str="1";for(int i=2;i<=n;i++){StringBuffer stringBuffer=new StringBuffer();int start=0;int pos=0;//11//while(pos<str.length()){int m=0;while(pos<str.length()&&str.charAt(pos)==str.charAt(start)){pos++;m++;}stringBuffer.append(Integer.toString(m)).append(str.charAt(start));start=pos;}str=stringBuffer.toString();} return str;}}

5.数青蛙

1419. 数青蛙 - 力扣（LeetCode）

class Solution {public int minNumberOfFrogs(String croakOfFrogss) {char[] croakOfFrogs=croakOfFrogss.toCharArray();//用数组模拟一个哈希表String t="croak";int n=t.length();int[] count=new int[n];Map<Character,Integer> map=new HashMap<>();//[字符x，x对应的下标]for(int i=0;i<n;i++){map.put(t.charAt(i),i);}for(char ch:croakOfFrogs){if(ch==t.charAt(0)){if(count[n-1]!=0){count[n-1]--; }count[0]++;}else{int i=map.get(ch);if(count[i-1]==0){return -1;}else{count[i-1]--;count[i]++;}}}//还要遍历数组看k前面的数字是否为0for(int i=0;i<n-1;i++){if(count[i]!=0){return -1;}}return count[n-1];}
}