【优选算法必刷100题：专题六】（模拟算法）第039~343题：替换所有的问号、提莫攻击、Z 字形变换、外观数列、数青蛙
🎬 个人主页：艾莉丝努力练剑
❄专栏传送门：《C语言》《数据结构与算法》《C/C++干货分享&学习过程记录》
《Linux操作系统编程详解》《笔试/面试常见算法：从基础到进阶》《Python干货分享》
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬 艾莉丝的简介：
🎬艾莉丝的算法专栏简介：
文章目录
039 替换所有的问号
力扣链接：1576. 替换所有的问号
题目描述：
1.1 解法：模拟的思想
纯模拟。从前往后遍历整个字符串，找到问号之后，就用a~z的每一个字符去尝试替换即可。
1.2 算法实现
// 模拟classSolution{public: string modifyString(string s){for(int i =0;i < s.size();i++){if(s[i]=='?')// 替换{for(char ch ='a';ch <='z';ch++){if((i ==0|| ch != s[i -1])&&(i == s.size()-1|| ch != s[i +1])){ s[i]= ch;break;}}}}return s;}};
1.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！040 提莫攻击
力扣链接：495. 提莫攻击
题目描述：
2.1 解法：模拟 + 分情况讨论
思路：模拟 + 分情况讨论。
我们只要计算相邻两个时间点的差值即可：
（1）如果差值大于等于中毒时间，说明上次中毒可以持续duration秒；（2）如果差值小于中毒时间，那么上次的中毒只能持续两者的差值。2.2 算法实现
classSolution{public:intfindPoisonedDuration(vector<int>& timeSeries,int duration){int ret =0;int n = timeSeries.size();for(int i =1;i < n;i++)// 计算当前位置和前面位置的差{int x = timeSeries[i]- timeSeries[i -1];if(x >= duration){ ret += duration;}else{ ret += x;}}// 最后一次中毒的时间是要把中毒时间全部算上的return ret + duration;}};
2.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！041 Z 字形变换
力扣链接：6. Z 字形变换
题目描述：
3.1 算法思路：模拟 +找规律
3.1.1 表格1：row = 4时各行的数字序列
找规律，用row代替行数，row = 4时画出的N字形如下：
| 行号 | 数字（表达式） | 数字（值，row=4） |
|---|---|---|
| 1 | 0, 2row-2, 4row-4 | 0, 6, 12 |
| 2 | 1, 2row-3, 2row-1, 4row-5, 4row-3 | 1, 5, 7, 11, 13 |
| 3 | 2, 2row-4, 2row, 4row-6, 4row-2 | 2, 4, 8, 10, 14 |
| 4 | 3, 2row+1, 4row-1 | 3, 9, 15 |
3.1.2 表格2：用周期T = 2row - 2表示的数字规律
不难发现，数据是以2roW-2为一个周期进行规律变换的。将所有数替换成用周期来表示的变量：
| 行号 (i) | 数字序列（用 T 表示） | 说明 |
|---|---|---|
| i=0 | 0, T, 2T | 公差为 T 的等差数列 |
| i=1 | 1, T-1, T+1, 2T-1, 2T+1 | 第一个数为 i，之后每组两个数围绕 T 的倍数对称 |
| i=2 | 2, T-2, T+2, 2T-2, 2T+2 | 同上 |
| i=3 | 3, T+3, 2T+3 | 公差为 T 的等差数列（最后一行数字为 i, T+i, 2T+i, …） |
可以观察到，第一行、第四行为差为2roW-2的等差数列；第二行、第三行除了第一个数取值为行数，每组下标为(2n - 1 , 2n)的数围绕（2row - 2）的倍数左右取值。
以此规律，我们可以写出迭代算法。
3.2 算法实现
classSolution{public: string convert(string s,int numRows){// 处理边界情况if(numRows ==1)return s;// 公差d == 0 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;}};
3.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！042 外观数列
力扣链接：38. 外观数列
题目描述：
4.1 解法思路：模拟
所谓【外观数列】，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。
4.2 算法实现
classSolution{public: string countAndSay(int n){ string ret ="1";for(int i =1;i < n;i++)// 解释 n - 1次 ret 即可{ 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];// to_string：个数转换 left = right;} ret = tmp;}return ret;}};
4.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
043 数青蛙
力扣链接：1419. 数青蛙
题目描述：
5.1 解法：位运算
模拟青蛙的叫声。
- 当遇到
'r''o''a''k'这四个字符的时候，我们要去看看每一个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符；如果没有，直接返回-1; - 当遇到
'c'这个字符的时候，我们去看看'k'这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去喊'c'这个字符；如果没有的话，就重新搞一个青蛙。
5.2 算法实现
classSolution{public:intminNumberOfFrogs(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];}};
5.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
结尾
uu们，本文的内容到这里就全部结束了，艾莉丝再次感谢您的阅读！
结语：希望对学习Python相关内容的uu有所帮助，不要忘记给博主“一键四连”哦！
往期回顾：
【优选算法必刷100题：专题五】（位运算算法）第033~38题：判断字符是否唯一、丢失的数字、两整数之和、只出现一次的数字 II、消失的两个数字
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡૮₍ ˶ ˊ ᴥ ˋ˶₎ა
