> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。> 目标：熟练掌握模拟算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
基本思想：
模拟算法 == 依葫芦画瓢解题思维要么通俗易懂，要么就是找规律，主要难度在于将思路转换为代码。
特点：
相对于其他算法思维，思路比较简单（没有很多的弯弯绕绕，考察的是代码能力）。
大致做题流程：
模拟算法流程（一定要在演草纸上过一遍 - 容易忽略细节），把流程转换为代码
🌙topic-->1
题目链接：1.模拟-->力扣（LeetCode）
题目分析：
给一个字符串，替换该字符串全部的 ？ 字符，把该 ？ 修改成若干个小写字母，但是这个字符串不能有重复的小写字母。
算法原理：
- 解法：采用模拟是的思路讲解
图解：
代码演示：
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;
}
};🌙topic-->2
题目链接：2.模拟 - 力扣（LeetCode）
题目分析：
题目说的是：给一个数组（这个数组的元素说明了在第几秒发出攻击），给一个 duration ，这个变量是攻击时产生被毒的时间，统计该人物被中毒的时间是多少。
算法原理：
- 解法：采用模拟是的思路讲解
图解：
代码演示：
class Solution
{
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration)
{
int ret = 0;
for (int i = 1; i < timeSeries.size(); i++)
{
int tmp = timeSeries[i] - timeSeries[i - 1];
if (tmp >= duration) ret += duration; // x > d
else ret += tmp; // x < d
}
return ret + duration; // 最后一个元素加上 d
}
};🌙topic-->3
题目链接：3.模拟 - 力扣（LeetCode）
题目分析：
给一个字符串，根据给定的行数numRows，从上往下，从左到右 Z 字形排列。
算法原理：
- 解法一：创建一个二维数组，之后遍历字符串，时间复杂度为O(N²)，空间复杂度为O(N²)
- 解法二：采用模拟算法（本质上找规律，减少时间复杂度和空间复杂度）
图解：
代码演示：
class Solution
{
public:
string convert(string s, int numRows)
{
// 处理边界情况(只有一行)
if(numRows == 1)
return s;
string ret;
int d = 2 * numRows - 2;// 公差
int n = s.size();// 字符个数
// 处理第一行
for(int i = 0;i < n;i += d)
ret += s[i];
// 处理 K 行
for(int k = 1;k < numRows - 1;k++) // 枚举 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];
}
}
// 处理最后一行
for(int i = numRows - 1;i < n;i += d)
ret += s[i];
// 返回
return ret;
}
};🌙topic-->4
题目链接：4.模拟 - 力扣（LeetCode）
题目分析：
这个题目可能有点抽象，简单来说就是一个读数问题，如何读呢？
第一项：1
第二项我们就需要读第一项数字：一个一，简化为 11
第三项我们就需要读第二项数字：两个一，简化为21
第四项我们就需要读第三项数字：一个二，一个一，简化为：1211
.....
算法原理：
- 解法：采用模拟的算法 + 双指针算法
图解：
代码演示：
class Solution {
public:
string countAndSay(int n)
{
// 初始字符串为 1
string ret = "1";
// 循环 n-1 就可以了
for(int i = 1;i < n;i++)
{
string tmp; // 交换变量
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];// 不要忘记把自己追加上 ret[left]
left = right;
}
ret = tmp;// 迭代
}
return ret;
}
};🌙topic-->5
题目链接：5.模拟 - 力扣（LeetCode）
题目分析：
给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
算法原理：
- 解法：采用模拟的算法 + 哈希桶
图解：
代码演示：
class Solution
{
public:
int minNumberOfFrogs(string croakOfFrogs)
{
string t = "croak";
int n = t.size();
vector<int> hash(n); // ⽤数组来模拟哈希表
unordered_map<char, int> index; //[x, x这个字符对应的下标]
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]++;
}
}
for (int i = 0; i < n - 1; i++)
if (hash[i] != 0)
return -1;
return hash[n - 1];
}
};🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
