【C/C++算法】从浅到深学习--- 简单模拟算法（图文兼备 + 源码详解） ...

绪论：打击蓝桥杯一起加油！！

每日鼓励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”
    绪论​：
本篇是一些简单的模拟算法，其中模拟的本质就是就是根据题目意思进行代码的实现，因为本质较为简单以是本章分析也较少，将会通过 5 题进行模拟算法的认识。
————————
早关注不迷路，话不多说安全带系好，发车啦（发起电脑观看）。
  

---

模拟算法：

比葫芦画瓢
特点：

• 思路比较简单
  
• 观察代码本事
  

流通：

• 模拟算法流程（一定不要空想，而是要草稿纸上过流程）
  
• 把流程转化成代码
  

详细训练：

1. 替换所有的问号

题目：

分析题目并提出，解决方法：

题解焦点逻辑：

1. class Solution {
2. public:
3.     string modifyString(string s) {
4.         //较为简单直接根据题意模拟即可
5.         //当找到一个 ? 时，通过遍历尝试的方法，找到不和前后相等的字符即可
6.         int n = s.size();
7.         for(int i = 0;i < n;i++)
8.         {
9.             if(s[i] == '?')
10.             {
11.                 for(char c = 'a';c < 'z';c++)
12.                 {
13.                     // if(i == 0 && s[i+1] != c){
14.                     //     s[i] = c;
15.                     //     break;
16.                     // }else if(i == n - 1 && s[i-1] != c){
17.                     //     s[i] = c ;
18.                     //     break;
19.                     // }else if(s[i+1] != c && s[i-1] != c){
20.                     //     s[i] = c;
21.                     //     break;
22.                     // }
24.                     //判断和前面与后面的字符是否相等
25.                     if((i == 0 || c != s[i-1]) && (i == n-1 || c != s[i+1])){
26.                         s[i] = c;
27.                         break;
28.                     }
29.                 }
30.             }
31.         }
32.         return s;
33.     }
34. };

复制代码

2. 提莫攻击

题目：

分析题目并提出，解决方法：

明确实例1：

明确重置：

题解焦点逻辑：

1. class Solution {
2. public:
3.     int findPoisonedDuration(vector<int>& timeSeries, int duration) {
4.         int res = 0;
5.         for(int i = 0;i < timeSeries.size() - 1;i++){//不考虑最后一个因为直接加上就好
6.             int x = timeSeries[i+1] - timeSeries[i];
7.             if(x >= duration) res += duration;
8.             else res += x;//加上 和 后面开始时间的差值（因为会重置）
9.         }
10.         res += duration;
11.         return res;
12.     }
13. };

复制代码

3. Z 字形变换

题目：

分析题目并提出，解决方法：

解法1：直接模拟，通过一个vector创建矩阵存储，数据z型的过程，最终遍历矩阵即可
解法2：
找规律，通过得出的矩阵，将他们的下标标出来，不难看出下图规律：

题解焦点逻辑：

1. class Solution {
2. public:
3.     string convert(string s, int numRows) {
4.         // 处理边界情况
5.         if (numRows == 1)
6.             return s;
7.         string ret;
8.         int d = 2 * numRows - 2, n = s.size();
9.         // 1. 先处理第⼀⾏
10.         for (int i = 0; i < n; i += d)
11.             ret += s[i];
12.         // 2. 处理中间⾏
13.         for (int k = 1; k < numRows - 1; k++) // 枚举每⼀⾏
14.         {
15.             for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {
16.                 if (i < n)
17.                     ret += s[i];
18.                 if (j < n)
19.                     ret += s[j];
20.             }
21.         }
22.         // 3. 处理最后⼀⾏
23.         for (int i = numRows - 1; i < n; i += d)
24.             ret += s[i];
25.         return ret;
26.     }
27. };

复制代码

4. 外观数列

题目：

分析题目并提出，解决方法：

题解焦点逻辑：

• 简单的模拟：通过双指针的方式查询连续的区间以及个数
  
• 在遍历 n 次即可得到 n 的外观数
  

1. class Solution {
2. public:
3.     string countAndSay(int n) {
4.         string res = "1";
5.         // for(int i= 0 ; i < n - 1;i++){//进行n次
6.         //     int left = 0 ,right = 0;//使用一个双指针判断连续个数
7.         //     string tmp;//存储一次的情况
8.         //     while(right < res.size()){
9.         //         right++;               
10.         //         if(right < res.size()){//在范围内
11.         //             if(res[right] != res[right-1])
12.         //             {
13.         //                 //记录
14.         //                 tmp += to_string(right - left) + res[right-1];
15.         //                 left = right;
16.         //             }
17.         //         }
18.         //         else
19.         //         {
20.         //             tmp += to_string(right - left) + res[right-1];
21.         //             break;
22.         //         }
23.         //     }
24.         //     res = tmp;
25.         // }
26.         
27.         //更简洁的写法：
28.         for(int i = 0; i < n - 1;i++){
29.             string tmp;
30.             int len = res.size();
31.             for(int left = 0,right = 0; right < len;){
32.                 //寻找第一个不同的位置（注意包括最后）
33.                 while(right < len && res[right] == res[left]) right++;
34.                 //到达此处代表出现不同，或者直接到了最后：
35.                 tmp += to_string(right - left) + res[left];
36.                 left = right;//从新位置开始继续找
37.             }
38.             res = tmp;
39.         }
40.         return res;
41.     }
42. };

复制代码

5. 数田鸡

题目：

分析题目并提出，解决方法：

题解焦点逻辑：

1. class Solution {
2. public:
3.     int minNumberOfFrogs(string croakOfFrogs) {
4.         //通过hash的方式记录青蛙叫的过程
6.         //当是 r o a k 字符时：需要再hash中判断 其前导字符（ r 前导字符是 c、o -> r、...）是否存在
7.         //若存在 则代表正常：在hash中 当前字符++，前导字符--
8.         //若不存在，则代表不正常，也代表字符串不连续 是有问题的 返回-1
10.         //当是 c 字符时：分成两种情况，
11.         //一种是前面有青蛙叫完了（k值 不等与0）:
12.         //1. 那么 k--、c++,让之前的青蛙继续往后叫（重复前面的操作）
13.         //第二种则是前面没青蛙，则 k == 0
14.         //那么就直接 c++，继续往后即可
16.         int hash[6] = {0};//记录叫的过程
17.         //直接用 6 大小的数组代表 0 c r o c k（留一个位置方便字符对应下标理解）
19.         for(int i = 0; i < croakOfFrogs.size();i++){
20.             if(croakOfFrogs[i] == 'c')
21.             {
22.                 if(hash[5] != 0){
23.                     hash[5]--;
24.                 }
25.                 hash[1]++;
26.             }
27.             else
28.             {
29.                 //此处代表不是第一个字符
30.                 int index;
31.                 if(croakOfFrogs[i] == 'r') index = 2;
32.                 else if(croakOfFrogs[i] == 'o') index = 3;
33.                 else if(croakOfFrogs[i] == 'a') index = 4;
34.                 else if(croakOfFrogs[i] == 'k') index = 5;
36.                 if(hash[index - 1] != 0)
37.                 {
38.                     //判断前导是否存在
39.                     hash[index - 1]--;
40.                     hash[index]++;
41.                 }
42.                 else
43.                 {
44.                     return -1;//若前导不存在则是有问题的！
45.                 }
46.             }
47.         }
48.         
49.         for(int i = 1;i < 5;i++){
50.             if(hash[i] != 0){
51.                 return -1;//不等于0就代表没叫玩就结束了那么就填0即可
52.             }
53.         }
54.         return hash[5];
55.     }
56. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。