【C/C++算法】从浅到深学习--- 简单模拟算法（图文兼备 + 源码详解）
绪论：打击蓝桥杯一起加油！！https://i-blog.csdnimg.cn/direct/a692a9f1418a4eb1958533b173f7c893.jpeg#pic_center
每日鼓励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”
绪论：
本篇是一些简单的模拟算法，其中模拟的本质就是就是根据题目意思进行代码的实现，因为本质较为简单以是本章分析也较少，将会通过 5 题进行模拟算法的认识。
————————
早关注不迷路，话不多说安全带系好，发车啦（发起电脑观看）。
模拟算法：
比葫芦画瓢
特点：
[*]思路比较简单
[*]观察代码本事
流通：
[*]模拟算法流程（一定不要空想，而是要草稿纸上过流程）
[*]把流程转化成代码
详细训练：
1. 替换所有的问号
题目：
https://i-blog.csdnimg.cn/direct/e5bd0502a5684256bf1b4bc7f0d705e1.png
分析题目并提出，解决方法：
https://i-blog.csdnimg.cn/direct/907678db022c46398fcc900a8389cbed.png
题解焦点逻辑：
https://i-blog.csdnimg.cn/direct/9929d0508c9b47a5ae70960bb1930ebf.png
https://i-blog.csdnimg.cn/direct/0ae5f0a2a2004b14a632f50b44a8f03e.png
class Solution {
public:
string modifyString(string s) {
//较为简单直接根据题意模拟即可
//当找到一个 ? 时，通过遍历尝试的方法，找到不和前后相等的字符即可
int n = s.size();
for(int i = 0;i < n;i++)
{
if(s == '?')
{
for(char c = 'a';c < 'z';c++)
{
// if(i == 0 && s != c){
// s = c;
// break;
// }else if(i == n - 1 && s != c){
// s = c ;
// break;
// }else if(s != c && s != c){
// s = c;
// break;
// }
//判断和前面与后面的字符是否相等
if((i == 0 || c != s) && (i == n-1 || c != s)){
s = c;
break;
}
}
}
}
return s;
}
};
2. 提莫攻击
题目：
https://i-blog.csdnimg.cn/direct/1975f630d95540539343f194cd245eb3.png
分析题目并提出，解决方法：
明确实例1：
https://i-blog.csdnimg.cn/direct/309d1fd84c384415bc239a256cc6519c.png
明确重置：
https://i-blog.csdnimg.cn/direct/2bd4e3a559a54c3b8a5c30d2b125909d.png
题解焦点逻辑：
https://i-blog.csdnimg.cn/direct/febed5148b5c4f1faf384c6045e6d339.png
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 - timeSeries;
if(x >= duration) res += duration;
else res += x;//加上 和 后面开始时间的差值（因为会重置）
}
res += duration;
return res;
}
};
3. Z 字形变换
题目：
https://i-blog.csdnimg.cn/direct/d36042885e424164baba8fae4dd86717.png
分析题目并提出，解决方法：
解法1：直接模拟，通过一个vector创建矩阵存储，数据z型的过程，最终遍历矩阵即可
解法2：
找规律，通过得出的矩阵，将他们的下标标出来，不难看出下图规律：
https://i-blog.csdnimg.cn/direct/0ffea6f33a0849f2a3ca3850cbd42972.png
题解焦点逻辑：
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;
// 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;
if (j < n)
ret += s;
}
}
// 3. 处理最后⼀⾏
for (int i = numRows - 1; i < n; i += d)
ret += s;
return ret;
}
};
https://i-blog.csdnimg.cn/direct/3bb5b6d15eb14f6ea50f301e4fbbd764.png
4. 外观数列
题目：
https://i-blog.csdnimg.cn/direct/e18919a1aeff4c95b049815ba85840ac.png
分析题目并提出，解决方法：
https://i-blog.csdnimg.cn/direct/9d4055692c5e4832bb18de5035114d6f.png
题解焦点逻辑：
[*]简单的模拟：通过双指针的方式查询连续的区间以及个数
[*]在遍历 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 != res)
// {
// //记录
// tmp += to_string(right - left) + res;
// left = right;
// }
// }
// else
// {
// tmp += to_string(right - left) + res;
// 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 == res) right++;
//到达此处代表出现不同，或者直接到了最后：
tmp += to_string(right - left) + res;
left = right;//从新位置开始继续找
}
res = tmp;
}
return res;
}
};
5. 数田鸡
题目：
分析题目并提出，解决方法：
https://i-blog.csdnimg.cn/direct/772e05eee1c24c549e20f8639c479d88.png
https://i-blog.csdnimg.cn/direct/f02cc490c3a640ebb392ff1ab2239135.png
题解焦点逻辑：
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 = {0};//记录叫的过程
//直接用 6 大小的数组代表 0 c r o c k（留一个位置方便字符对应下标理解）
for(int i = 0; i < croakOfFrogs.size();i++){
if(croakOfFrogs == 'c')
{
if(hash != 0){
hash--;
}
hash++;
}
else
{
//此处代表不是第一个字符
int index;
if(croakOfFrogs == 'r') index = 2;
else if(croakOfFrogs == 'o') index = 3;
else if(croakOfFrogs == 'a') index = 4;
else if(croakOfFrogs == 'k') index = 5;
if(hash != 0)
{
//判断前导是否存在
hash--;
hash++;
}
else
{
return -1;//若前导不存在则是有问题的！
}
}
}
for(int i = 1;i < 5;i++){
if(hash != 0){
return -1;//不等于0就代表没叫玩就结束了那么就填0即可
}
}
return hash;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]