【算法】模拟

个人主页 ： zxctscl
如有转载请先通知

前言

模拟算法就是根据题目所给的照葫芦画瓢。
考察的是代码能力。
步骤：1.模拟算法流程（一定得自己先过一遍流程）
2.把流程转化为代码

1. 1576. 替换所有的问号

1.1 分析

题目的意思很显而易见，遍历一遍字符串如果是？，就找一个小写字母来替换它，而它的前面一个字符和它不相同，它后面一个字符和它也不能相同。得处理一下边界情况，如果?在开始位置，就不用比较它前面位置，比较后面那个位置就行。同样在结尾位置的话，就比较前面的一个字符相不相等就行。

1.2 代码

class Solution {
public:string modifyString(string s) {int n =s.size();for(int i=0;i<n;i++){if(s[i]=='?'){for(char ch='a';ch<='z';ch++){if((i==0||ch!=s[i-1])&&(i==n-1||ch!=s[i+1])){s[i]=ch;break;}}}}return s;}
};

2. 495. 提莫攻击

2.1 分析

当前这个位置减去前面一个位置的差，如果大于等于中毒时间，那么就全部加上中毒时间；如果差小于中毒时间，那么就是加上这个差值。得注意最后一个值没有判断，最后的值还得再加上一个中毒时间才行。

2.2 代码

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int n=timeSeries.size();int ret=0;for(int i=1;i<n;i++){       int t=timeSeries[i]-timeSeries[i-1];if(t>=duration)  {ret+=duration;}else ret+=t;}return ret+duration;}
};

3. 6. Z 字形变换

3.1 分析

一、题目解析
按题目所述，像下面图片这样的就是Z字型。

二、算法原理
要想得到最后为Z字型输出的字符串，可以直接开一个矩阵直接先把字符一个一个放进去再一行一行输出。
但还可以用另外一个方式，就是找规律。

举个例子：把字符的下标都写到矩阵里面，就发现了规律。
第一行每间隔2n-2就出现一次，为了方便描述，就把间隔叫做公差d=2n-2,第一行只需要输出每次个d个数的字符就可以。
最后一行和第一行一样，也是间隔d个字符数。
来看中间几行，1和5到11和13中间间隔的也是d个数，那么直接一次性输出两个就行。

3.2 代码

class Solution {
public:string convert(string s, int numRows) {   if(numRows==1)return s;string ret;int d=2*numRows-2;int n=s.size();for(int i=0;i<n;i+=d)ret+=s[i];、//第一行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];}}for(int i=numRows-1;i<n;i+=d)//最后一行{ret+=s[i];}return ret;}
};

4. 38. 外观数列

4.1 分析

模拟题目的意思
找到连续相同的字符解释一下，可以利用双指针来进行，如果两个指针指向的位置字符相同就一直走，不一样就停下来，中间元素的个数就是指针的差值；然后让左边指针指向右边指针的位置，再重复上面的操作就可以了。

4.2 代码

class Solution {
public:string countAndSay(int n) {string ret="1";for(int i=1;i<n;i++){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];left=right;}ret=tmp;}return ret;}
};

5. 1419. 数青蛙

5.1 分析

模拟
用一个哈希表时刻记录每一次字符出现的情况。如果青蛙叫了c时候，那么就用1记录一下有一个青蛙叫了c字符;遍历到r的时候看看前面有没有青蛙叫了c,有就让这个青蛙继续叫r,在哈希表了让c减减，r加加就行。当又遇到一个c时候，表示又有一个青蛙过来，然后继续遍历到o的时候，要看看哈希表前面有没有青蛙叫过r，有的话r减减，o加加，继续往后重复直到k。
但是题目要求青蛙数目最少，这里k中有数的时候，此时又有c时候，就从k里面搬一个青蛙来从c开始叫，k减减，c加加，重复上面过程。k里面的数存的就刚好是结果。
但是如果除了k里面还有非0元素，那么就返回-1。

如果在在哈希表中，在r位置之前没有c那么就返回-1：

总结，都得找前驱字符，如果前驱字符有，那么前驱字符减减，当前字符加加；没有就返回-1。
最后一个字符看看它是不是在哈希表里面存在，存在就是最后一个字符减减，当前字符加加；不存在就当前字符加加。

5.2 代码

class Solution
{
public:int minNumberOfFrogs(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];}
};