> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：熟练掌握模拟算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
基本思想：
模拟算法 == 依葫芦画瓢解题思维要么通俗易懂，要么就是找规律，主要难度在于将思路转换为代码。
特点：
相对于其他算法思维，思路比较简单（没有很多的弯弯绕绕，考察的是代码能力）。
大致做题流程：
模拟算法流程（一定要在演草纸上过一遍 - 容易忽略细节），把流程转换为代码
🌙topic-->1
题目链接：1.模拟-
题目分析：
给一个字符串，替换该字符串全部的 ？ 字符，把该 ？ 修改成若干个小写字母，但是这个字符串不能有重复的小写字母。
算法原理：
- 解法：采用模拟是的思路讲解
图解：
代码演示：
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.模拟
题目分析：
题目说的是：给一个数组（这个数组的元素说明了在第几秒发出攻击），给一个 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.模拟
题目分析：
给一个字符串，根据给定的行数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.模拟
题目分析：
这个题目可能有点抽象，简单来说就是一个读数问题，如何读呢？
第一项：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.模拟
题目分析：
给你一个字符串 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]; } };
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
