---

前言

模拟算法,顾名思义,就是一种直接按照问题描述的步骤和规则进行逐步操作的解题方法.它不依赖复杂的数学推导或数据结构优化,而是忠实还原题目要求的处理流程,通过一步步执行指令来解决问题.模拟算法大部分考察的是代码能力.

其核心在于：
​流程还原：将题目中的操作步骤转化为代码逻辑。
​状态跟踪：维护当前问题的状态（如字符串、数组等），并按照规则更新状态。
​无需优化：以直观方式实现,不追求效率,确保正确.

我本人见的大部分模拟题好像都无可优化(或资历尚浅吧).

模拟算法好像有点像暴力解法?模拟算法是否就是暴力算法?
模拟算法是直接按题目规则逐步构造解,而暴力算法是尝试所有可能，再验证正确性.
相比之下模拟算法更像是模拟人的思路.

所以模拟算法,其实不是,也无需从暴力解法优化而来,尝试按照问题描述的步骤和规则进行逐步操作解题.

---

题目：

038. 替换所有的问号（easy）

分析

class Solution {
public:string modifyString(string s) {for(int i = 0;i < s.size();i++){char& ch = s[i];if(ch == '?'){for(char chr = 'a';chr <= 'z';chr++){if(((i == 0) || chr != s[i-1]) && ((i == s.size() - 1) || chr != s[i+1])){ch = chr;break;}}}}return s;}
};

---

039. 提莫攻击（easy）

分析

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

---

040. N 字形变换（medium）

分析

class Solution {
public:string convert(string s, int numRows) {int n = s.size();if(numRows >= n || numRows == 1) return s;          //如果行数大于串的总大小或者等于1,其Z字变换后的字符串还是s.int t = numRows * 2 - 2;                                  //算出2/3个Z字,周期需要的字符数,为了算出最后构造的二维数组需要多少列.int numColumns = (t + n - 1)/t * (numRows - 1);           //(t + n - 1)/t算出周期数,(r-1)是一个周期需要的列数.vector<string> mat(numRows,string(numColumns,0));   //以列做横,方便后续取非0字符.int x = 0,y = 0;for(int i = 0;i<n;i++){mat[x][y] = s[i];if(i % t < numRows - 1)                               //判断每个周期中其内部有没有到达Z字的转折点.{x++;}else{x--;y++;}}string ret;for(auto& arr : mat){for(auto& c : arr){if(c) ret += c;           //不可以c!='0'做条件,还有很多其他值为"假值".}}return ret;}
};

---

041. 外观数列 (medium)

分析

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

---

042. 数⻘蛙（medium）

分析

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";int n = t.size();vector<int> _hash(n);unordered_map<char,int> chToin;for(int i = 0;i < t.size();i++){chToin[t[i]] = i;}for(int i = 0;i < croakOfFrogs.size();i++){int index = chToin[croakOfFrogs[i]];if(index == 0){if(_hash[chToin['k']] != 0) _hash[chToin['k']]--;_hash[index]++;}else{if(_hash[index - 1] == 0) return -1;_hash[index - 1]--;_hash[index]++;}}for(int i = 0;i < n - 1;i++) if(_hash[i] != 0) return -1;return _hash[chToin['k']];}
};

---

总结

因为模拟算法的特性,边界情况是重点.

---

本文章为作者的笔记和心得记录，顺便进行知识分享，有任何错误请评论指点：）。