本文讲解模拟算法系列的5道经典题，在讲解题目的同时提供AC代码，点击题目即可打开对应OJ链接
目录
模拟算法的介绍
1、替换所有的问号
2、提莫攻击
3、 Z 字形变换
4、外观数列
5、数青蛙
模拟算法的介绍
题目中明确告诉你要干什么，思路简单，较考察代码能力
做题步骤：
- 模拟算法流程（自己一定要演示一下）
- 把流程转换为代码
大部分的模拟题的优化方式都是通过找规律
1、替换所有的问号
算法思路：
从前往后遍历整个字符串，当出现问号时，枚举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 ch = 'a'; ch <= 'z'; ch++)
{ //如果为第一个位置或最后一个位置，则利用||不用判断前面或后面的字符
if ((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1]))
{
s[i] = ch;
break;
}
}
}
}
return s;
}
};2、提莫攻击
算法思路：
模拟+分情况讨论。
计算相邻两个时间点的差值：
- 如果差值大于等于中毒时间，说明上次中毒可以持续 duration 秒；
- 如果差值小于中毒时间，那么上次的中毒只能持续两者的差值
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int ret = 0;
for (int i = 1; i < timeSeries.size(); i++)
{
int x = timeSeries[i] - timeSeries[i - 1];
if (x >= duration) ret += duration;
else ret += x;
}
return ret + duration;//要把最后一个位置的中毒时间加上
}
};3、 Z 字形变换
分析题目：
解题思路：
可以定义一个字符串用来保存结果，当遇到目标字符就利用string的+=来保存结果，所以我们只需知道需要保存的字符的顺序和位置即可
下面找规律按照①~④推得来：
class Solution {
public:
string convert(string s, int numRows) {
//处理边界情况【处理第一行时会死循环,报超出时间限制】
if (numRows == 1) return s;
string ret;//保存结果的字符串
//1、处理第一行
int d = 2 * numRows - 2, n = s.size();
for (int i = 0; i < n; i += d) ret += s[i];
//2、处理中间行
for (int k = 1; k < numRows - 1; k++)//循环中间的每一行
{
for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
{ //两个元素哪个没走到头就加哪个
if (i < n) ret += s[i];
if (j < n) ret += s[j];
}
}
//3、处理最后一行
for (int i = numRows - 1; i < n; i += d) ret += s[i];
return ret;
}
};4、外观数列
解题思路：
class Solution {
public:
string countAndSay(int n) {
string ret = "1";//初始状态
for (int i = 1; i < n; i++) //进行n-1次即为答案
{
string tmp;//要用临时变量保存每次得到的结果，直接加到ret上就累积了，结果不对
int len = ret.size();
for (int left = 0, right = 0; right < len;)
{
while (right < len && ret[left] == ret[right]) right++;//找连续相同区域
tmp += to_string(right - left) + ret[left];//利用to_string将整数转换为字符串
left = right;
}
ret = tmp;//每次都更新下结果
}
return ret;
}
};5、数青蛙
解题思路：模拟+哈希表
注：最后模拟完后，哈希表中应该只有k位置有数，其他位置都应没数，如果有，则不符题意，即代码最后还要做一下判断
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
string t = "croak";
int n = t.size();
vector<int> hash(n); //数组模拟哈希表
unordered_map<char, int> index; //保存字符及其下标，方便找到字符
for (int i = 0; i < n; i++) index[t[i]] = i;
for (auto ch : croakOfFrogs)
{
if (ch == 'c')
{
if (hash[n - 1] != 0) hash[n - 1]--;
hash[0]++;
}
else
{
int i = index[ch];//先获取该字符的下标
if (hash[i - 1] == 0) return -1;//若前驱字符不存在
hash[i - 1]--, hash[i]++;
}
}
//判断除了k位置外，其他的位置若也有数，则说明不是croak的有效组合
for (int i = 0; i < n - 1; i++)
if (hash[i] != 0) return -1;
return hash[n - 1];//k位置出现几次，就至少几只青蛙
}
};
