1.概念解析
什么是模拟算法？
简单来说就是按照题目给定的规则与逻辑，按步骤细致地重现事件的发展流程，进而获取最终结果的算法。
2.替换所有的问号
题目描述：
示例：
题目链接：替换所有的问号
题解:
这题很简单，显然是先遍历一遍数组，然后在遍历的时候，如果遇到 ? 就替换为与该位置前后都不相同的数，所以也要对要替换的数遍历一遍，直到发现合适的数。
细节问题：
注意边界情况，没有两个相邻的数。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
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;
}
};
3.提莫攻击
题目描述：
示例：
题目链接：提莫攻击
题解:
做模拟算法题的精髓就是要画图，只有图画明白了，才能找到规律，而不是凭空想象。
所以根据规律发现相邻两数之差是突破点，如果相邻两数之差大于 duration，那么不用重置中毒时间；如果相邻两数之差小于 duration，那么要重置中毒时间。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int ret = 0;
for (int i = 1; i < timeSeries.size(); ++i) {
int x = timeSeries[i] - timeSeries[i - 1];
if (x >= duration) {
ret += duration;
} else {
ret += x;
}
}
return ret + duration;
}
};
4.Z 字形变换
题目描述：
示例：
题目链接：Z 字形变换
题解:
本题的意思是要你根据题目给出的 Z 字形字符串，将其从上到下，从左至右的方式以一个新字符串的方式返回，显然这是一个找规律性极强的题目，所以画图！
第一步：
首先我们将每个数的索引按照 Z 字形填入，我们是从第一行开始录入，所以可以发现第一行和最后一行都是一个等差数列，然后发现规律，公差是 0~6 之间元素的个数，所以得出 d=2n-2。
第二步：
接下来处理中间的行数，发现如图的 1 ~ 7 ~ 13，5 ~ 11 ~ 17 也是以 6 为公差，只不过是两个数两个数的差，所以得出规律（k，d-k）。
细节问题：
注意 for 循环的判断条件为 i < n || j < k，而不是&&，因为当一个越界之后，另一个可能还没越界判断完。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) {
return s;
}
string ret;
int n = s.size();
int d = 2 * numRows - 2;
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 < k; 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;
}
};
5.外观序列
题目描述：
示例：
题目链接：外观序列
题解:
其实题目意思就是对上一行的序列进行解释，比如第三行为 21，那么第四行的意思就是一个 2 一个 1。
细节问题：
所以很明显这题要用双指针解决，因为要持续向后查找有几个相同的，直到不同为止。
left 和 right 都从 0 开始，然后 right 向后移动，直到该位置和前一个位置不相同，然后记录长度和数字，直接让 left=right，开始下一段。
代码实现：
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string countAndSay(int n) {
string ret = "1";
for (int i = 1; i < n; ++i) {
string tmp;
int len = ret.size();
for (int left = 0, right = 0; right < len;) {
while (ret[left] == ret[right]) {
right++;
}
tmp += to_string(right - left) + ret[left];
left = right;
}
ret = tmp;
}
return ret;
}
};
6.数青蛙
题目描述：
示例：
题目链接：数青蛙
题解:
要理解本题题意，就是一只青蛙要完整叫完 croak，如果一只青蛙没叫完，那么就需要另一只青蛙来发出叫声。
第一步：
首先，以如图所示为例子，第一个 c，计入该位置为 1，接下来到 r，该位置变为 1，上一个位置变为 0，可以理解为 一个 1 一直在移动，表示这个叫声遍历到哪里了，直到遍历到 k 为止。
第二步：
注意在遍历过程中注意要像图中分类，对于字符 c，若 k 位置不为 0，那么表示有青蛙闲置，那么之前叫完的青蛙就可以再次叫；对于其他字符，要找该字符的前一个字符不符合 croak 的顺序和字符，若不符合字符，直接返回 -1。
细节问题：
注意处理完所有字符时，要判断一下是否还有没叫完的叫声。
代码实现：
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
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') {
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]++;
}
}
for (int i = ; i < n - ; ++i) {
(hash[i] != ) {
;
}
}
hash[n - ];
}
};
