【算法杂货铺】模拟

🌈前言🌈

📁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;elseret += 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];}
};