【模拟】算法实战

---

一、算法原理

模拟就是用计算机来模拟题目中要求的操作，模拟题目通常具有代码量大、操作多、思路繁琐的特点。所谓的"模拟题"，用一句老话所就是"照着葫芦画瓢"，根据题目的表述进行筛选提取关键要素，按需求书写代码解决实际问题。

---

二、算法实战

1. leetcode1576 替换所有的问号

替换所有的问号

解题思路：

这是一道简单的模拟题，意思是一个字符串中有 '?' 字符，将些字符替换为'a' ~ 'z'中的任意一个字符后，使得这个字符串中不会出现连续两个以上的连续字符。首先我们遍历这个字符串，先找到字符 '?' 的位置，然后从'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++){if((i == 0 || ch != s[i-1]) && (i == s.size()-1 || ch != s[i+1])){s[i] = ch;break;}                }}}return s;}
};

---

2. leetcode495 提莫攻击

提莫攻击

解题思路：

首先扫描这个数组，使用cnt统计答案，timeSeries[i]表示此时攻击的开始点，timeSeries[i+1]表示下一次攻击的开始点。

• timeSeries[i + 1] - timeSeries[i] < duration，表示两次攻击重叠。cnt+=timeSeries[i + 1] - timeSeries[i]。
• timeSeries[i + 1] - timeSeries[i] >= duration，表示两次攻击不重叠， cnt+=duration。

因为最后一次攻击是肯定会持续完的，所以我们扫描数组的时候只需要扫描前n-1个元素。但是最后返回结果时候需要返回cnt+duration。

代码实现：

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

---

3. leetcode6 N字形变换

N字形变换

解题思路：

首先我们应该先搞清楚从原字符串到目标字符串是如何变换而来的。

我们可以看到这个过程：先将该字符串以'N'字形的顺序依次填入一个二维数组中，然后将该二维数组中的内容从上到下一行一行拼接起来即可。这里我们可以从中找一些规律出来：

代码实现：

class Solution {
public:string convert(string s, int numRows) {string ret = "";if(numRows == 1)return s;int sub = 2*numRows - 2;for(int i = 0; i < numRows; i++){// 处理第一行和最后一行if(i == 0 || i == numRows-1){for(int j = i; j < s.size(); j += sub){ret += s[j];}}else{// 处理中间行for(int k = i, p = sub - k; k < s.size() || p < s.size(); k += sub, p += sub){if(k < s.size()) ret += s[k];if(p < s.size()) ret += s[p];}}}return ret;}
};

---

4. leetcode38 外观数列

外观数列

解题思路：

题目告诉了我们数列的每一项的变换过程是通过上一项推导出来的，因此我们可以根据上一项模拟数列每一项的形成过程。在数列每一项的模拟过程中，我们依然使用滑动窗口的算法原理来实现。

代码实现：

class Solution {
public:string countAndSay(int n) {// 使用双指针算法进行模拟string start = "1";while(--n){string tmp;for(int left = 0, right = 0; left < start.size(); right++){if(start[left] != start[right]){tmp += to_string(right - left);tmp += start[left];left = right;}}start = tmp;}return start;}
};

---

5. leetcode1419 数青蛙

数青蛙

解题思路：

这道题目属于典型的比较难的模拟题，先开一个哈希表，然后将"croak"按照<char, int>的方式映射进哈希表，这里的int指的是"croak"中字符的下标。开一个cnt来计数，统计每一个字符出现的次数。

从前向后遍历字符串，如果ch=='c'，说明需要一只青蛙开始发出蛙鸣，如果前面统计cnt[n - 1]，这里的n-1表示"croak"字符串的最后一个’k’的下标，意思是如果cnt[n - 1]已经出现过了，说明前面有一只青蛙已经将"croak"，这个字符串全部叫了一遍，那么我们让前面的青蛙继续从头开始叫就可以了，不需要增加青蛙的数量，因此让cnt[n - 1]--，cnt[0]++，如果cnt[n - 1] == 0, 则直接让cnt[0]++。

如果ch!='c'，则说明一只青蛙正在发出蛙鸣的过程中，此时我们让此时青蛙发出蛙鸣的字符的前一个字符的下标cnt[c前面的字符]- -，然后让正在遍历的字符数量cnt[c]++，如果中途发现cnt[c前面的字符] == 0， 说明该字符连续出现了两次以上，或者字幕出现的顺序有问题。直接返回-1即可。

最后我们统计的时候只需要关心"croak"中最后一个’k’出现了几次即可，同时，我们还需要遍历cnt中除最后一个元素外，看前面的字母出现的次数是否为0，若不为0，说明字幕出现的顺序不符合要求，直接返回-1。

代码实现：

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";int n = t.size();vector<int> cnt(n);unordered_map<char, int> hash;for(int i = 0; i < n; i++) hash[t[i]] = i;for(char ch : croakOfFrogs){if(ch == 'c'){if(cnt[n - 1]) cnt[n - 1]--;cnt[0]++;}else{int i = hash[ch];if(cnt[i - 1])cnt[i - 1]--, cnt[i]++;else return -1;}}for(int i = 0; i < n - 1; i++)if(cnt[i] != 0) return -1;return cnt[n - 1];}
};

---

三、总结

模拟的过程就是对真实场景尽可能的模拟，但我们需要注意的是：模拟题并没有我们所想象的那么简单，它的代码中可能会有很多的'坑'，我们在写模拟算法的过程中需要谨慎。