模拟算法总结（Java）

秒速五厘米 2024-04-25 08:44 3阅读 0赞

**目录**

模拟算法概述

练习

练习1：替换所有的问号

练习2：提莫攻击

练习3：Z字形变换

--------------------

## 模拟算法概述 ##

**模拟**：根据题目要求的实现过程进行编程模拟，即题目要求什么就实现什么

解决这类题目，需要：

> **1. 根据题目要求模拟算法流程**
> 
> **2. 将算法流程转换为代码**

接下来，我们以几道练习来进一步理解和掌握模拟算法

## 练习 ##

### 练习1：替换所有的问号 ###

**题目链接：**

[1576. 替换所有的问号 - 力扣（LeetCode）][1576. _ - _LeetCode]

**题目描述：**

给你一个仅包含小写英文字母和 `'?'` 字符的字符串 `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` 仅包含小写英文字母和 `'?'` 字符

**思路分析：**题目要求我们将所有的?替换为小写字母，且不包含**连续重复的**字符，我们按照题目要求进行替换即可

接下来，我们**模拟替换过程**：

![1c2bae2c41664be4b944c1ede90deb18.jpeg][]

当?出现在**第一位**时，只需判断所替换的字符是否与后一位相同，因此，我们使用for循环，当所替换的字符不与后一位相同时，即可将?替换为该字符

![675e0d0ca2af41a0ab4cf8cf6e867c3c.jpeg][]

当?出现在**中间**时，需要判断所替换的字符是否与其前后字符相同，当所替换的字符不与前后字符相同时，即可替换

![b073665445dc45279192737e47538453.jpeg][]

当?出现在**最后一位**时，只需判断所替换的字符是否与前一位相同，当不相同时，即可替换  
**代码实现：**

class Solution {
        public String modifyString(String s) {
            char[] chs = s.toCharArray();
            int len = chs.length;
            for(int i = 0; i < len; i++){
                if(chs[i] == '?'){//当出现?，进行替换
                    for(char ch = 'a'; ch <= 'z'; ch++){
                        if((i == 0 || ch != chs[i-1]) && 
                            (i == len - 1 || ch != chs[i+1])){//注意处理?出现在第一位或最后一位的情况
                                chs[i] = ch;
                                break;
                            }
                    }
                }
            }
            return new String(chs);
        }
    }

### 练习2：提莫攻击 ###

**题目链接：**

[495. 提莫攻击 - 力扣（LeetCode）][495. _ - _LeetCode]

**题目描述：**

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

当提莫攻击艾希，艾希的中毒状态正好持续 `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` 按 **非递减** 顺序排列

**思路分析：**在t时刻发起攻击后，进入中毒状态，duration 时间后解除，而在 duration 时间内又发起攻击，则在发起攻击时刻重新计时，过程如下图所示：![bdd5605079a14145a24c460b5e1f6fcd.jpeg][]

我们可以计算出两次攻击的间隔时间：**d = t2 - t1**

> 当d >= duration时，在两次攻击间隔内，中毒时间为duration
> 
> 当d < duration时，在两次攻击时间间隔内，中毒时间为d

![60f1a93b71e04adbbb6e987043b021de.jpeg][]

因此，我们只需要计算出相邻两次攻击的间隔时间，再计算出中毒时间，最后求出中毒时间总和，即可求出中毒总时间

注：在最后一次攻击后，也有一段中毒时间

![435bdbb1b484427b905731fcd5c25cc5.jpeg][]

**代码实现：**

class Solution {
        public int findPoisonedDuration(int[] timeSeries, int duration) {
            if(timeSeries.length <= 1) return duration;//当只有一次攻击时，直接返回duration
            int sum = 0;
            for(int i = 0; i < timeSeries.length - 1; i++){
                int d = timeSeries[i+1] - timeSeries[i];
                if(d >= duration) sum += duration;
                else sum += d;
            }
            sum += duration;//最后一次攻击后的中毒时间
            return sum;
        }
    }

### 练习3：Z字形变换 ###

**题目链接：**

[6. Z 字形变换 - 力扣（LeetCode）][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);

**示例 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`

**思路分析：**

我们以题目示例为例，来进行一次变换：

![4557bf72974141c5b56ac7110ecadab7.jpeg][]

此时， 先从上往下，再从左下往右上，再从上往下... 将字符串变换成了"Z"字形，也类似于"N"

我们首先按题目要求进行变换，要进行从上往下，再从坐下往右上的变换，因此我们需要一个矩阵，所有我们可以创建一个二维数组

我们从第0行开始，向下填写：

![4f4f3617fa21487cb6089ab5f711907a.jpeg][]

设当前为（x, y），向下填写：（x+1, y），直到填写到numRow - 1行

接下来，从左下到右上开始填写：

![4ca29fa6b44a45d886cd383c388f2ef4.jpeg][]

从（x, y）开始，向右上填写：(x + 1, y - 1)，直到填写到第0行

...

一直填写直到最后一个字符，然后再从左到右，从上到下读取所有字符

> **如何判断是向下填写还是向右上填写？**

我们可以使用变量flag进行标记，当x为0 或x为numRow时，就改变转向，即flag = -flag，当flag为1时，就向下填写；而当flag为-1时，就向右上填写

**代码实现：**

class Solution {
        public String convert(String s, int numRows) {
            if(numRows == 1) return s;//当间隔为1时，变换后仍为原字符串，直接返回即可
            char[] chs = s.toCharArray();
            char[][] arr = new char[numRows][chs.length];//直接将列数设置为字符串长度即可
            int x = 0, y = 0;
            int flag = -1;//标记转向
            for(int i = 0; i < chs.length; i++){
                if(x == 0 || x == numRows - 1){//当处于第一行和最后一行时，改变转向
                    flag = -flag;
                }
                arr[x][y] = chs[i];
                if(flag == 1){//向下填写
                    x++;
                }else{//向右上填写
                    x--;
                    y++;
                }
            }
            StringBuilder ret = new StringBuilder();
            for(int i = 0; i < arr.length; i++){//遍历数组，从左到右，从上到下，将数组中的字符拼接
                for(int j = 0; j < arr[0].length; j++){
                    if(arr[i][j] != 0){
                        ret.append(arr[i][j]);
                    }
                }
            }
            return ret.toString();
        }
    }

通过观察变换后的字形我们可以发现：变换后的字形具有周期性，因此我们可以寻找其中的变换规律，从而直接得出变换后的字符串

![4bb7ff7f3b3143acb4ef3f407cd1e8a6.jpeg][]

第一行与最后一行类似，我们以第一行为例，来观察其中的规律：

设第一行两个字符之间的间隔为 d，为了更方便观察规律，我们以下标来标识每一个字符：

![e6cb9f1dd173466992165a54ed8d6373.jpeg][]

当numRow为4时，d为6，而间隔d，其实就是从0到6（不包括6）的字符个数，因此，我们只需求出从x1 到 x2的字符个数，即可求出d

> **如何求出字符个数？**

我们将中间的字符都移动到第二列：

![6edac622a6d149f8b705260a483af577.jpeg][]

即可发现当移动到第二列后，第二列**只缺少第一个和最后一个元素，**因此 **d = 2\*numRow - 2**

则第一行元素为：0，0 +d，0 + 2\*d，0 + 3\*d，... 0 + n\*d

最后一行元素为：numRow - 1，numRow - 1 + d，numRow - 1 + 2\*d，...numRow - 1 + n\*d

接下来，我们寻找中间元素（第i行）的变换规律：

我们可以发现：**第i行的两个字符下标和为d**

因此，第i行元素为：i，d - i，i + d，d - i + d... i + n\*d，d - i + n\*d

由上述规律，我们即可直接找到每一行的字符

**注：当numRow为1时，d = 0，此时第一行元素始终为0，陷入死循环，因此要特殊处理该情况**

**代码实现：**

class Solution {
        public String convert(String s, int numRows) {
            if(numRows <= 1) return s;//处理特殊情况
            int d = numRows*2 - 2;//间隔d
            int n = s.length();
            StringBuilder ret = new StringBuilder();
            for(int i = 0; i < n; i+= d){//添加第一行字符
                ret.append(s.charAt(i));
            }
            for(int row = 1; row < numRows - 1; row++){//添加中间行字符
                for(int i = row, j = d - row; i < n || j < n; i += d, j += d){
                    if(i < n) ret.append(s.charAt(i));
                    if(j < n) ret.append(s.charAt(j));
                }
            }
            for(int i = numRows - 1; i < n; i += d){//添加最后一行字符
                ret.append(s.charAt(i));
            }
            return ret.toString();
        }
    }

[1576. _ - _LeetCode]: https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/
[1c2bae2c41664be4b944c1ede90deb18.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e8d35d7f65ff4a508b63384c17d72109.jpeg
[675e0d0ca2af41a0ab4cf8cf6e867c3c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/978e0f5c874d433b8adc8b3eb7064d62.jpeg
[b073665445dc45279192737e47538453.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/90e89df5ad7542fdb971688b5c5a78e4.jpeg
[495. _ - _LeetCode]: https://leetcode.cn/problems/teemo-attacking/description/
[bdd5605079a14145a24c460b5e1f6fcd.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/bae06d76a9174095942128decd505e9e.jpeg
[60f1a93b71e04adbbb6e987043b021de.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/81bd2fee5a37403fa8d7311594a0a081.jpeg
[435bdbb1b484427b905731fcd5c25cc5.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e1d7638ab0724c09a8bce47687b933ff.jpeg
[6. Z _ - _LeetCode]: https://leetcode.cn/problems/zigzag-conversion/description/
[4557bf72974141c5b56ac7110ecadab7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e4974a5f642849a5bd4d8b8d6b694d53.jpeg
[4f4f3617fa21487cb6089ab5f711907a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/aa4e61cb7cb8488fa7fc7dd11459e7cd.jpeg
[4ca29fa6b44a45d886cd383c388f2ef4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/aece7b8f3886480eb081a15fcac06213.jpeg
[4bb7ff7f3b3143acb4ef3f407cd1e8a6.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/adb51681aba747eab9551273643bd170.jpeg
[e6cb9f1dd173466992165a54ed8d6373.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/a0e32662d0754ed29837e571614c0551.jpeg
[6edac622a6d149f8b705260a483af577.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/fa893ea44938499aa7a18eabc87129b0.jpeg