一、替换所有的问号

1.链接

1576. 替换所有的问号 - 力扣（LeetCode）

2.描述

3.思路

本篇开始整理模拟算法相关的题目，所谓模拟算法，实际就是根据题目的要求去一步步实现题目的步骤，这一类题目较多考察细节和代码能力，思路本身不难，但也有部分题目具有优化的空间，一般都是通过要求找到相关的规律，然后利用规律去优化

本题中要求将字符中的'?'替换成其他字符，且该字符不能和前后两个重复，则只需要根据要求去遍历一遍字符串，找到‘？’然后再根据要求判断条件即可，注意前后的边界条件

4.参考代码

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

二、提莫攻击

1.链接

495. 提莫攻击 - 力扣（LeetCode）

2.描述

3.思路

依照题目意思，我们只需要计算每次施法后，有效的中毒时长是多少即可

当两个施法时间间隔大于等于duration时，意味着前一个施法中毒的有效时间就会是一个完整的duration，而当施法时间间隔小于duration时，由于中毒时间会被重置，当前的有效中毒时间就会是下一次施法时间到此时施法时间的时间差，因此，我们只需要遍历一遍数组，累计有效的释法时间即可，最后一个中毒有效时间要额外处理

4.参考代码

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) 
    {
        int ret = duration;//由于题目说timeSeries.size()大于等于1，因为最后一次中毒时间直接初始化给ret
        for(int i = 0;i<timeSeries.size()-1;i++)
        {
            int x = timeSeries[i+1] - timeSeries[i];
            if(x >= duration) ret+=duration;
            else ret+=x;
        }
        return ret;
    }
};

三、Z字形变换

1.链接

6. Z 字形变换 - 力扣（LeetCode）

2.描述

3.思路

4.参考代码

class Solution {
public:
    string convert(string s, int numRows) 
    {
        if(numRows == 1) return s;
        int d = 2*numRows-2;
        int n = s.size();
        int row = numRows;
        string ret;
        //先搞定第一行
        for(int i = 0;i<n;i+=d) ret+=s[i];
        //再来搞定中间行
        for(int i = 1;i<row-1;i++)
        {
            for(int j = i,k=d-j ; j<n || k<n ;j+=d,k+=d)
            {
                if(j < n) ret+=s[j];
                if(k < n) ret+=s[k];
            }
        }
        //最后搞定最后一行
        for(int i = row-1;i<n;i+=d) ret+=s[i];
        return ret;
    }
};

四、外观数列

1.链接

38. 外观数列 - 力扣（LeetCode）

2.描述

3.思路

核心就是模拟如何按照题目要求去模拟得到“描述”这个操作，可以使用双指针遍历去实现该操作

4.参考代码

class Solution 
{
public:
    string countAndSay(int n) 
    {
        string ret = "1";
        while(--n)
        {
            string tmp;
            int left = 0;
            int right = 0;
            while(right < ret.size())
            {
                while(right < ret.size() && ret[right] == ret[left]) right++;
                tmp+=to_string(right-left);
                tmp+=ret[left];
                left = right;
            }

            ret = tmp;
        }
        return ret;
    }
};

五、数青蛙

1.链接

1419. 数青蛙 - 力扣（LeetCode）

2.描述

3.思路

这题的模拟过程需要借助哈希表来完成

4.参考代码

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string s = "croak";
        int n = s.size();

        vector<int> hash(n,0);
        unordered_map<char,int> m;//[字符，字符对应哈希表的下标]
        for(int i =0;i<n;i++)
        {
            m[s[i]] = i;
        }
        for(auto c:croakOfFrogs)
        {
            if(c == 'c')
            {
                if(hash[n-1] != 0) hash[n-1]--;
                hash[0]++; 
            }
            else
            {
                int i = m[c];
                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];
    }
};

总结

本篇的算法思想主要是模拟算法，实际就是按照题目要求去实现功能，主要考验代码能力和部分数学能力等等，整理了几个经典例题提供参考