前言
前面我们学习的算法，当读完题目之后可就能就会知道使用哪种算法，这种算法就类似于一种模板，而有一类算法却不能称为特定的模板，这种就叫做模拟算法。模拟算法是指：根据题目提供的信息，将该题目的解决过程模拟出来就能够得到最终的结果，模拟算法比较简单，只要能够根据题目的意思将题目给模拟出来，一般都能够解决这个问题。
模拟算法是一种计算机算法，用于模拟或仿真现实世界中的某个过程、系统或现象。它通过运行一系列的步骤或规则来模拟目标对象的行为，并生成与真实情况相似的结果。
1.替换所有问号
https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/
1.1 题目要求
给你一个仅包含小写英文字母和 ‘?’ 字符的字符串 s，请你将所有的 ‘?’ 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。
注意：你 不能 修改非 ‘?’ 字符。
题目测试用例保证 除 ‘?’ 字符 之外，不存在连续重复的字符。
在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。
示例 1：
输入：s = "?zs" 输出："azs" 解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。 只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。
示例 2：
输入：s = "ubv?w" 输出："ubvaw" 解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。 因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。
提示：
- 1 <= s.length <= 100
- s 仅包含小写英文字母和 ‘?’ 字符
class Solution { public String modifyString(String s) { } }
1.2 做题思路
这个题目的思路很简单，我们只需要遍历一遍字符串，然后将字符为 ? 的字符更改为除 ? 之外的其他 26 个小写英文字母，并且保证相邻的字符不能重复。通过模拟算法，我们是可以直接解决这个问题的，需要多加注意的就是下标的越界问题，当下标为字符串的第一个字符的时候，它只有右边的一个相邻字符；当字符为中间的 n 个字符的时候，它需要考虑左右两个相邻字符；而当字符为最后一个字符的时候，则只有左边一个相邻的字符。
1.3 Java代码实现
class Solution { public String modifyString(String ss) { //因为Java代码操作字符串较复杂，所以我们可以将字符串转换为数组来操作 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 || ch != s[i - 1]) && (i == n - 1 || ch != s[i +1])) { s[i] = ch; break; } } } } return String.valueOf(s); } }
2. 提莫攻击
https://leetcode.cn/problems/teemo-attacking/
2.1 题目要求
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续 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 。
提示：
- 1 <= timeSeries.length <= 104
- 0 <= timeSeries[i], duration <= 107
- timeSeries 按 非递减 顺序排列
class Solution { public int findPoisonedDuration(int[] timeSeries, int duration) { } }
2.2 做题思路
这道题目也就是需要根据提莫攻击的时间和次数来计算受到伤害的时间，只需要根据题目给的timeSeries数组来知道受到攻击的时间的次数，然后结合给定的 duraction 来计算总共时间。
但是，我们需要考虑一个特殊的情况，当两次攻击的间隔时间小于受到伤害的持续时间的话，那么受到伤害的持续时间就会被重置。
根据上面的两种情况我们可以将提莫的攻击间隔分为两种情况：攻击间隔时间大于伤害持续时间；攻击间隔时间小于等于伤害持续时间。当攻击间隔时间大于伤害持续时间的时候，我们只需要加上这个duraction就行了，当间隔时间小于等于伤害持续时间的话，就加上这两次的攻击间隔时间的差，而不是duraction。
2.3 Java代码实现
class Solution { public int findPoisonedDuration(int[] timeSeries, int duration) { int ret = 0; for(int i = 0; i < timeSeries.length - 1; i++) { if(timeSeries[i + 1] - timeSeries[i] > duration) ret += duration; else ret += timeSeries[i + 1] - timeSeries[i]; } return ret += duration; } }
3. N 字形变换
https://leetcode.cn/problems/zigzag-conversion/
3.1 题目要求
将一个给定字符串 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);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI" 解释： P I N A L S I G Y A H R P I
示例 3：
输入：s = "A", numRows = 1 输出："A"
提示：
- 1 <= s.length <= 1000
- s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
- 1 <= numRows <= 1000
class Solution { public String convert(String s, int numRows) { } }
3.2 做题思路
这个题目是什么意思呢？就是将给定的字符串变换成 numRows 行 N 型图形，举个例子：
我们可以使用二维数组来模拟出来结果，但是这样的时间复杂度和空间复杂度都很高，那么时候有一种方法可以降低时间复杂度和空间复杂度呢？是有的，我们只需要多观察，然后找出其中的规律：那些字符处于第一行，哪些字符处于最后一行，然后再将这些重新组合的字符拼接在一起就可以了，所以这道题的关键就在于如何找到其中的规律。
3.3 Java代码实现
class Solution { public String convert(String ss, int numRows) { if(numRows == 1) return ss; char[] s = ss.toCharArray(); int n = s.length; int d = 2 * numRows - 2; StringBuilder ret = new StringBuilder(); //处理第一行数据 for(int i = 0; i < n; i += d) ret.append(s[i]); //处理中间 numRows-2 行数据 for(int i = 1; i < numRows - 1; i++) { for(int j = i, k = d - j; j < n || k < n; j += d, k += d) { if(j < n) ret.append(s[j]); if(k < n) ret.append(s[k]); } } //处理最后一行数据 for(int i = numRows - 1; i < n; i += d) ret.append(s[i]); return ret.toString(); } }
【算法系列篇】模拟算法-2：https://developer.aliyun.com/article/1430526
