模拟算法详解及 LeetCode 典型题目实践

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 = 0; i < n - 1; ++i) {
            if (hash[i] != 0) {
                return -1;
            }
        }
        return hash[n - 1];
    }
};