个人主页 ： 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];
    }
};