【算法杂货铺】模拟

🌈前言🌈

📁1576. 替换所有的问号编辑

📁 495. 提莫攻击

📁 6. Z 字形变换

📁38. 外观数列

📁1419. 数青蛙

📁 总结

🌈前言🌈

欢迎观看本期【算法杂货铺】，本期内容将讲解算法中的模拟，模拟算法就是将题目给用代码语言翻译出来，是一个非常简单的算法，重要的是看懂题目，以及翻译成代码，此外，画图注重细节也是很重要的。

本篇文章注重讲解不同题目，从三个角度，带你从零开始理解模拟算法。

1. 讲解多种习题的题目；2. 算法原理；3. 代码展示。

📁1576. 替换所有的问号

📂 题目解析

这是一套非常简单的题目，即将 ‘ ？’ 替换成前后不相等的小写字母即可。“？zs” 可以替换成，除“zzs”以外的任何字符串。

📂 算法原理

做模拟题目，重要的就是看懂题目，在此基础上，我们只要画图即可，将各种可能推演出来，翻译成代码即可。

通过上图的展示，我们就将?所有可能出现的位置给枚举出来，现在我们只要保证每一种情况成立即可。

纯模拟。从前往后遍历整个字符串，找到问号之后，就⽤ a ~ z 的每⼀个字符去尝试替换即可。

📂 代码展示

class Solution {
public:
    string modifyString(string s) {
        for(int i=0;i<s.size();i++)
        {
            if(s[i] == '?')
            {
               for(char ch = 'a' ; ch <='z';ch++)
               {
                 /*

                 1）如果 i==0，只要保证s[i+1] != ch即可。
                 2）如果 i == size-1 , 只要保证 s[i-1] != ch即可。
                 3）若i在区间[1, size-2]中,则要保证 s[i-1] != ch && s[i+1] != ch

                 */
                 if((i==0 || s[i-1] != ch) && (i==s.size()-1 || s[i+1] != ch))
                 {
                     s[i] = ch;
                 }
               }
            }
        }
        return s;
    }
};

📁 495. 提莫攻击

📂 题目解析

别看题目这么长就害怕，其实非常好理解，就是给我们一个非递减的整数数组，第i个元素表示第i秒发动的攻击，会持续d秒。

如果从第i秒开始，持续d秒，到i+d秒；如果第i+1秒受到攻击，则会从第i+1秒内重新计算，持续到第i+1+d秒，以此类推。

📂 算法原理

这道题，就是一道模拟+分类讨论的题目。对于模拟题来说，我们尽可能的画图，方便理解。

我们首先来看示例1，第1秒和第4秒发起了攻击，其实这个在整个时间段内有1~5秒，第 t[i] 秒发动了攻击，加上d秒，不会影响到第 t[i+1] 秒,即得出公式，t[i] - t[i-1] >= d。

这里为什么可以等于d呢，是因为是从第t[i]秒开始算起。

例如t = {1,3} ,d= 2 :

3 - 1 >= 2，从第1秒到第2秒是持续的时间，不会影响到第3秒。

当i到了最后攻击的时段时，我们只需要总秒数+d即可，因为最后一项后不会在攻击了，只会持续d秒了。

因此我们得出两种结论，即t[ i ] - t[ i - 1] >= d 时，总秒数+d ; 遍历到数组最后一个位置时，总秒数 + d。

画出示例2的图，我们便可知，t[ i ] - t [i - 1] < d时，总秒数加上 t[ i ] 到 t [i - 1]内持续的时间，即ret += t[ i ] - t[ i - 1]。

以上，就是这道题目的所有情况，其实只要画出图来，一切就很清晰了。

📂 代码展示

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

📁 6. Z 字形变换

📂 题目解析

其实通过题目，就可以看出模拟解法，通过一个矩阵，找出矩阵的规律，在一次遍历这个矩阵即可。

但如果这个时间复杂度会是len*N，如果数据量较大，可能会报错。所以我们要进行优化。

对于模拟算法来说，绝大多数的优化都是找规律，我们通过画图，找出矩阵的规律，即可。

📂 算法原理

通过画图，我们可以得出以下结论，由于篇幅限制，我们这里之以示例2为例，但以下结论适用于本题任何场景，当然如果numRows=0，则就是原字符串，需要特殊处理。

📂 代码展示

class Solution {
public:
    string convert(string s, int numRows) {
        int d = 2 * numRows - 2;
        int n = s.size();
        string ret;
        //特殊判断
        if(numRows == 1)
        {
            return s;
        }

        //处理第0行
        for(int i = 0;i < n;i += d)
        {
            ret += s[i];
        }

        //处理第1行 - 第n-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];
            }
        }

        //处理最后一行
        for(int i = numRows-1;i < n ; i += d)
        {
            ret += s[i];
        }
        return ret;
    }
};

📁38. 外观数列

📂 题目解析

画图可知，每一项都是由前一项翻译出来的，第一项为“1”，例如第2项是1个1得出来的，第3项是由第2项得出，即1个2和1个1。

就是判断连续且相同的字符有多少个，添加到新字符串中。

📂 算法原理

这道题就是模拟+双指针的思路，如下图所示：

当right遍历到字符串尾的时候，新字符串=“231231”

📂 代码展示

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        //翻译n-1次
        for(int i=1;i<n;i++)
        {
            string temp;
            int len = ret.size();
            for(int right = 0,left =0;right < len;)
            {
                while(right < len && ret[right] == ret[left])
                    right++;
                temp += to_string(right - left) + ret[left];
                left = right;
            }
            ret = temp;
        }
        return ret;
    }
};

📁1419. 数青蛙

📂 题目解析

其中这个提示是比较总要的，所以单独放了出来。

出现一次“crock”就代表了一声蛙鸣，代表有一只青蛙，题目要求返回最小的青蛙个数，所以两声“crock”最少可以有1只青蛙。如果不是字符“croak”不是有效组合，返回-1。

📂 算法原理

这里我们采用模拟+哈希的算法。

如下图所示，以“croakcroak”为例子，当s[i]是c的时候，我们c索引对应的值++，碰见r的时候，c--,r++,直到遍历到k，此时代表有一只青蛙。k就代表着最少的青蛙个数

遍历到第二个c的时候，因为求的最少的青蛙个数，k此时不为0，所以可以k--,c++。

因此，可以得出以下结论：

对于r,o,a,k 找一下前驱字符，判断是否为空，如果不是空，前驱字符--，当前字符++；否则返回-1。

对于c来说，判断k是不是空，如果不是空，k--,c++；如果为空，c++。

📂 代码展示

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n); //模拟哈希

        unordered_map<char,int> index; //记录字符的下标
        for(int i=0;i<n;i++)
        {
            index[t[i]] = i;
        }

        for(auto ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                //检查k是否为空，即判断是否已有青蛙
                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]++;
            }
        }

        //当遍历完数组后，k之前的字符必须为空，否则为无效字符
        for(int i=0;i<n-1;i++)
        {
            if(hash[i] != 0)
            {
                return -1;
            }
        }
        return hash[n-1];

    }
};