【C/C++算法】从浅到深学习--- 简单模拟算法（图文兼备 + 源码详解）_c++模拟算法
绪论：冲击蓝桥杯一起加油！！
每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”
绪论：
本篇是一些简单的模拟算法，其中模拟的本质就是就是根据题目意思进行代码的实现，因为本质较为简单所以本章分析也较少，将会通过 5 题进行模拟算法的认识。
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。
模拟算法：
比葫芦画瓢
特点：
- 思路比较简单
- 考察代码能力
流畅：
- 模拟算法流程（一定不要空想，而是要草稿纸上过流程）
- 把流程转化成代码
具体训练：
1. 替换所有的问号
题目：
分析题目并提出，解决方法：
题解核心逻辑：
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++) { // if(i == 0 && s[i+1] != c){ // s[i] = c; // break; // }else if(i == n - 1 && s[i-1] != c){ // s[i] = c ; // break; // }else if(s[i+1] != c && s[i-1] != c){ // s[i] = c; // break; // } //判断和前面与后面的字符是否相等 if((i == 0 || c != s[i-1]) && (i == n-1 || c != s[i+1])){ s[i] = c; break; } } } } return s; }};2. 提莫攻击
题目：
分析题目并提出，解决方法：
理解实例1：
理解重置：
题解核心逻辑：
class Solution {public: int findPoisonedDuration(vector<int>& timeSeries, int duration) { int res = 0; for(int i = 0;i < timeSeries.size() - 1;i++){//不考虑最后一个因为直接加上就好 int x = timeSeries[i+1] - timeSeries[i]; if(x >= duration) res += duration; else res += x;//加上 和 后面开始时间的差值（因为会重置） } res += duration; return res; }};3. Z 字形变换
题目：
分析题目并提出，解决方法：
解法1：直接模拟，通过一个vector创建矩阵存储，数据z型的过程，最终遍历矩阵即可
解法2：
找规律，通过得出的矩阵，将他们的下标标出来，不难看出下图规律：
题解核心逻辑：
class Solution {public: string convert(string s, int numRows) { // 处理边界情况 if (numRows == 1) return s; string ret; int d = 2 * numRows - 2, n = s.size(); // 1. 先处理第⼀⾏ 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. 外观数列
题目：
分析题目并提出，解决方法：
题解核心逻辑：
- 简单的模拟：通过双指针的方式查询连续的区间以及个数
- 在遍历 n 次即可得到 n 的外观数
class Solution {public: string countAndSay(int n) { string res = \"1\"; // for(int i= 0 ; i < n - 1;i++){//进行n次 // int left = 0 ,right = 0;//使用一个双指针判断连续个数 // string tmp;//存储一次的情况 // while(right < res.size()){ // right++; // if(right < res.size()){//在范围内 // if(res[right] != res[right-1]) // { // //记录 // tmp += to_string(right - left) + res[right-1]; // left = right; // } // } // else // { // tmp += to_string(right - left) + res[right-1]; // break; // } // } // res = tmp; // } //更简洁的写法： for(int i = 0; i < n - 1;i++){ string tmp; int len = res.size(); for(int left = 0,right = 0; right < len;){ //寻找第一个不同的位置（注意包括最后） while(right < len && res[right] == res[left]) right++; //到达此处代表出现不同，或者直接到了最后： tmp += to_string(right - left) + res[left]; left = right;//从新位置开始继续找 } res = tmp; } return res; }};5. 数青蛙
题目：
分析题目并提出，解决方法：
题解核心逻辑：
class Solution {public: int minNumberOfFrogs(string croakOfFrogs) { //通过hash的方式记录青蛙叫的过程 //当是 r o a k 字符时：需要再hash中判断 其前导字符（ r 前导字符是 c、o -> r、...）是否存在 //若存在 则代表正常：在hash中 当前字符++，前导字符-- //若不存在，则代表不正常，也代表字符串不连续 是有问题的 返回-1 //当是 c 字符时：分成两种情况， //一种是前面有青蛙叫完了（k值 不等与0）: //1. 那么 k--、c++,让之前的青蛙继续往后叫（重复前面的操作） //第二种则是前面没青蛙，则 k == 0 //那么就直接 c++，继续往后即可 int hash[6] = {0};//记录叫的过程 //直接用 6 大小的数组代表 0 c r o c k（留一个位置方便字符对应下标理解） for(int i = 0; i < croakOfFrogs.size();i++){ if(croakOfFrogs[i] == \'c\') { if(hash[5] != 0){ hash[5]--; } hash[1]++; } else { //此处代表不是第一个字符 int index; if(croakOfFrogs[i] == \'r\') index = 2; else if(croakOfFrogs[i] == \'o\') index = 3; else if(croakOfFrogs[i] == \'a\') index = 4; else if(croakOfFrogs[i] == \'k\') index = 5; if(hash[index - 1] != 0) { //判断前导是否存在 hash[index - 1]--; hash[index]++; } else { return -1;//若前导不存在则是有问题的！ } } } for(int i = 1;i < 5;i++){ if(hash[i] != 0){ return -1;//不等于0就代表没叫玩就结束了那么就填0即可 } } return hash[5]; }};
