算法————模拟算法
目录
一、模拟算法
二、题目
1、替换所有的问号
（1）题目
编辑
（2）解题思路
（3）代码实现
编辑
2、提莫攻击
（1）题目
（2）解题思路
（3）代码解答
3、Z字形变换
（1）题目
（2）解题思路
（3）代码实现
4、外观数组
（1）题目
编辑
（2）解题思路
（3）代码书写
5、数青蛙
（1）题目
（2）解题思路
（3）代码书写
一、模拟算法
顾名思义该类型的题目的思路十分简单，只需要根据题目来写代码
二、题目
1、替换所有的问号
（1）题目
（2）解题思路
只需遍历字符串找出？，将？的位置替换成左右两边不同的字母
（3）代码实现
class Solution
{
public:string modifyString(string s){int n = s.size();for(int i = 0; i<s.size();i++){if(s[i]=='?'){for(char ch = 'a';ch<='z';ch++){if((i==0||s[i-1]!=ch)&&(i==n-1||s[i+1]!=ch)){s[i] = ch; }}}}return s;}};2、提莫攻击
（1）题目
（2）解题思路
我们观察发现当两次攻击的时间间隔大于duration，中毒时间就是duration.如果小于duration,中毒持续的时间就是两次攻击的秒数相减，只要把中毒时间都加到一起就是最后的结果
注意：不要忘记最后的三秒
（3）代码解答
class Solution
{
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int sum = 0;int n = timeSeries.size();for(int i = 0 ; i < n - 1; i++){if(timeSeries[i+1]-timeSeries[i]<duration){sum += timeSeries[i+1]-timeSeries[i];}else{sum += duration;}}return sum + duration;}
};3、Z字形变换
（1）题目
（2）解题思路
方法一:直接模拟
首先将他们按照Z字行来排列，在输出
方法二:根据规律，直接输出
我们首先将行数设置为n ,观察上图我们可以发现第一行和最后一行每一个相隔2*n-2（设为公差d）
中间的第k行遵循k , d-k, d+k ,d+d-k ,d+d+d+k ,d+d+d-k的规律
（3）代码实现
class Solution
{
public:string convert(string s, int numRows) {string r;if(numRows == 1){return s;}int d = 2 * numRows-2;for(int i = 0; i < s.size(); i += d){r+=s[i];}for(int k = 1; k < numRows - 1; k++){for(int i = k, j = d-k; i < s.size() || j < s.size(); i+=d,j+=d){if(i < s.size()){r+=s[i];}if(j < s.size()){r+=s[j];}}}for(int k = numRows - 1; k<s.size(); k+=d){r+=s[k];}return r;}
};4、外观数组
（1）题目
（2）解题思路
模拟+双指针：我们可以发现这个本质就是找字符串中有几个不同
（3）代码书写
class Solution
{
public:string countAndSay(int n) {string s = "1";for(int i = 0; i < n-1; i++){ string tmp ;int left = 0;int right = 0;while(right<s.size()){while(right < s.size() && s[left] == s[right]){right++;}tmp += to_string(right-left) + s[left];left = right ;}s = tmp;}return s;}
};5、数青蛙
（1）题目
（2）解题思路
我们可以借助哈希来模拟记录每一个字母对应出现的次数
（3）代码书写
class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) {string t ="croak";int n = t.size();vector<int> hash(n,0);unordered_map<char ,int> index;for(int i = 0; i<n;i++){index[t[i]] = i; }for(auto ch : croakOfFrogs){if(ch=='c'){if(hash[n-1]==0) hash[0]++;else{hash[n-1]--;hash[0]++;}}else{int i = index[ch];if(hash[i-1] == 0) return -1;else{hash[i-1]--;hash[i]++;}}}for(int i = 0 ; i<n-1; i++){if(hash[i]!=0)return -1;}return hash[n-1];}
};