【C/C++算法】从浅到深学习--- 简单模拟算法（图文兼备 + 源码详解）
绪论：冲击蓝桥杯一起加油！！
每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”
绪论：
本篇是一些简单的模拟算法，其中模拟的本质就是就是根据题目意思进行代码的实现，因为本质较为简单所以本章分析也较少，将会通过 5 题进行模拟算法的认识。
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。
模拟算法：
比葫芦画瓢
特点：
- 思路比较简单
- 考察代码能力
流畅：
- 模拟算法流程（一定不要空想，而是要草稿纸上过流程）
- 把流程转化成代码
具体训练：
1. 替换所有的问号
题目：
分析题目并提出，解决方法：
题解核心逻辑：
classSolution{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：
理解重置：
题解核心逻辑：
classSolution{public:intfindPoisonedDuration(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：
找规律，通过得出的矩阵，将他们的下标标出来，不难看出下图规律：
题解核心逻辑：
classSolution{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 的外观数
classSolution{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. 数青蛙
题目：
分析题目并提出，解决方法：
题解核心逻辑：
classSolution{public:intminNumberOfFrogs(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;elseif(croakOfFrogs[i]=='o') index =3;elseif(croakOfFrogs[i]=='a') index =4;elseif(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];}};
