模拟算法专题：替换问号、提莫攻击、Z 字形变换等五题解析

解法：模拟 + 分情况讨论

思路：模拟 + 分情况讨论。

我们只要计算相邻两个时间点的差值即可：

1. 如果差值大于等于中毒时间，说明上次中毒可以持续 duration 秒；
2. 如果差值小于中毒时间，那么上次的中毒只能持续两者的差值。

算法实现

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

041 Z 字形变换

题目描述：

算法思路：模拟 + 找规律

表格 1：row = 4 时各行的数字序列

表格 2：用周期 T = 2row - 2 表示的数字规律

不难发现，数据是以 $2 imes row - 2$ 为一个周期进行规律变换的。

第一行、最后一行为差为 $2 imes row - 2$ 的等差数列；中间行除了首尾元素外，下标围绕周期倍数对称取值。

算法实现

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        string ret;
        int d = 2 * numRows - 2;
        int n = s.size();
        // 1、先处理第一行
        for (int i = 0; i < n; i += d) ret += s[i];
        // 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];
            }
        }
        // 3、处理最后一行
        for (int i = numRows - 1; i < n; i += d) ret += s[i];
        return ret;
    }
};

042 外观数列

题目描述：

解法思路：模拟

所谓【外观数列】，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。

算法实现

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 (right < len && ret[left] == ret[right]) right++;
                tmp += to_string(right - left) + ret[left];
                left = right;
            }
            ret = tmp;
        }
        return ret;
    }
};

043 数青蛙

题目描述：

解法：位运算 / 状态机

模拟青蛙的叫声。

• 当遇到 'r', 'o', 'a', 'k' 这四个字符的时候，检查前驱字符是否有青蛙叫出来。如果有，让该青蛙继续喊当前字符；如果没有，返回 -1。
• 当遇到 'c' 这个字符的时候，检查是否有已完成的青蛙（即刚喊完 'k'）。如果有，复用该青蛙；如果没有，新建一只青蛙。

算法实现

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];
    }
};