【基础算法总结】模拟篇

一，算法介绍

模拟算法本质就是"依葫芦画瓢"，就是在题目中已经告诉了我们该如何操作，我们只要把题目中的过程转化成代码即可。特点是思路简单，难点是十分考验代码功底。

二，算法原理和代码实现

1576.替换所有的问号

算法原理：

没有那么多弯弯绕绕，就是从前往后遍历字符串，如果出现 ‘?’，就用26个字母判断一个 ‘?’ 字符的前一个和后一个字符，保证不出现前后两个连续相同的字符，再把 ‘?’ 替换即可。

细节问题：

要注意边界情况的判断，就是当 ‘?’ 出现在第一个位置和最后一个位置的处理。

代码实现：

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 || s[i-1] != ch) && (i == n-1 || s[i+1] != ch)){s[i] = ch;break;}}}}return s;}
};

495.提莫攻击

算法原理：

根据示例，可以得到下面的规律：

代码实现：

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

6.Z字形变换

算法原理：

我们不直接把字符进行Z变换，把每个字符的下标抽象出来：

然后在表中找出下标的规律，直接在字符串中根据找出的下标取字符：

细节问题：

当给定行数为 1 行时，计算的公差 d == 0，会造成死循环。所以要特殊处理，此时直接返回原字符串即可。

代码实现：

class Solution 
{
public:string convert(string s, int numRows) {// 处理特殊情况if(numRows == 1) return s;int d = 2 * numRows - 2, n = s.size();string ret;// 处理第一行的字符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;}
};

38.外观数列

算法原理：

本题使用：模拟+双指针
这里的双指针的作用就是从前往后遍历相同字符的区域，计算出相同字符的个数。

代码实现：

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

1419.数青蛙

算法原理：

这道题在模拟算法中是一道比较难的题。
使用：模拟+哈希表。
遍历所给的字符串，与叫声字符串进行对比映射：

通过模拟，可以进行总结：

细节处理：

(1) 两个哈希表的作用：
第一个哈希表用数组模拟，目的是统计字符出现的个数，但不是用字符进行映射统计的，而是根据叫声字符串 "croak"的下标。
第二个哈希表用 hash< char, int > 实现，表示的是叫声字符串"croak"的每个字符，和每个字符对应的下标。
(2) 当遍历完整个 croakOfFrogs 字符串后，还需要把第一个哈希表遍历检查一下。

代码实现：

根据上面的总结，实现代码有多种方式，下面的实现方式是一种通用的，因为可能有些题目给的叫声字符串不是只有五个字符的"croak"，而是其他更长的。

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;else hash[i-1]--, hash[i]++;}}// 除了最后一个字符'k'外，其他字符如果还有出现，直接返回-1for(int i = 0; i < n-1; i++)if(hash[i] != 0) return -1;return hash[n-1];}
};

三，算法总结

解决有关模拟类的题型，最重要的就是根据题目写代码。有些模拟题可能正面做困难，进行优化时一般都是"找规律"进行转换。