算法——模拟

1. 什么是模拟算法？

官方一点来说

模拟算法（Simulation Algorithm）是一种通过模拟现实或抽象系统的运行过程来研究、分析或解决问题的方法。它通常涉及创建一个模型，模拟系统中的各种事件和过程，以便观察系统的行为，收集数据并得出结论。这类算法适用于复杂的系统，其中涉及许多相互作用的元素和随时间变化的状态。

通俗来说

我们只需要对照题目，提取出对应的流程，将这个流程转换成代码。需要注意的是， 我们要在草稿纸上过一遍流程，不然很容易出问题。

2. 应用实例

1. 替换所有的问号

题目链接：1576. 替换所有的问号 - 力扣（LeetCode）

解析：分析一下这道题目，我们大致可以遍历一遍数组，在‘?’处从‘a’~‘z’挑选一个合适的字符替换该位置，代码如下

class Solution 
{
public:string modifyString(string s) {int n = s.size();for (int i = 0; i < n; i++){if (s[i] == '?'){for (char c = 'a'; c <= 'z'; c++){// 如果?在0位默认前面是符合要求的，最后一位同理if ((i == 0 || c != s[i-1]) && (i == n-1 || c != s[i+1]))s[i] = c;}}}return s;}
};

2. 提莫攻击

题目链接：495. 提莫攻击 - 力扣（LeetCode）

解析：分析题目，我们可以知道每次提莫攻击时，都会重置中毒时间，因此我们只需要计算一下两个攻击的间隔时间，若小于duration就加上这个间隔时间，若大于等于则加上duration即可，即

这之后由于最后一段中毒时间没有统计上去，直接加上即可，代码如下

class Solution 
{
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int time = 0, n = timeSeries.size();for (int i = 1; i < n; i++){int del = timeSeries[i] - timeSeries[i-1];if (del >= duration) time += duration;else time += del; }return time + duration;}
};

3. Z字型变换

题目链接：6. Z 字形变换 - 力扣（LeetCode）

解析：分析这道题目，我们可以知道整个字符串s会被排列成numrows行，仔细观察可以发现所有的下标均满足下面的变化规律：0 -> numRows-1 -> 0 ->numRows-1，我们可以对下标的变化进行模拟，即设定一个flag表示当前下标向下还是向上移动，移动到边界时将i与flag修改成正确值，同时创建一个<int, string>的哈希表来储存每行字符串，最后遍历一遍哈希表即可（注：这里需要对numRows为1做特殊情况处理），代码如下

class Solution 
{
public:string convert(string s, int numRows) {if (numRows == 1) return s;int n = s.size();unordered_map<int, string> hash;string ret;int i = 0, flag = 1;// flag为1表示向下移动for (auto& ch : s){if (i == numRows) flag = 0, i -= 2;if (i == -1) flag = 1, i += 2;hash[i] += ch;if (flag) i++;else i--;}for (int i = 0; i < numRows; i++) ret += hash[i];return ret;}
};

4. 外观数组

题目链接：38. 外观数列 - 力扣（LeetCode）

解析：分析题目，我们可以发现这道题的意思是让我们每次描述前一个字符串，因此我们只需要创建一个临时字符串s即可，然后每次统计描述之后更新s即可，代码如下

class Solution 
{
public:string countAndSay(int n) {string s = "1";while (--n){string pre = s;string now;int num = 0;for (int left = 0, right = 0; right < pre.size(); right++){if (pre[left] != pre[right]) {now += to_string(num) + pre[left];left = right;num = 1;}else num++;}now += to_string(num)+ pre.back();s = now;}return s;}
};