算法专题：模拟算法实战（替换问号、提莫攻击、Z 字形变换等）

1. 如果间隔大于等于中毒持续时间，说明上次中毒效果完全结束，累加完整时长。
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 字形变换

题目链接： 6. Z 字形变换

解题思路

观察 Z 字形排列，可以发现数据是以 2 * numRows - 2 为一个周期进行循环的。第一行和最后一行是公差为周期的等差数列；中间行则包含两个交错序列。

我们可以直接按行构建结果字符串：

1. 先处理第一行，步长为周期。
2. 再处理中间行，每行有两个指针交替前进。
3. 最后处理最后一行，步长为周期。

代码实现

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        
        string ret;
        int d = 2 * numRows - 2, 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 外观数列

题目链接： 38. 外观数列

解题思路

这本质上是一个'读'的过程。第 N 项是对第 N-1 项的描述。例如 "1" 读作 "1 个 1" -> "11"。我们需要统计连续相同字符的个数，然后拼接成新的字符串。

使用双指针法：左指针标记当前字符起始位置，右指针向后扫描直到字符变化，记录长度并拼接。

代码实现

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 数青蛙

题目链接： 1419. 数青蛙

解题思路

青蛙叫的顺序是固定的：c -> r -> o -> a -> k。我们可以用一个哈希表（或数组）记录当前处于每个叫声阶段的青蛙数量。

• 遇到 'c'：如果有刚叫完 'k' 的青蛙，让它复用；否则新开一只青蛙。
• 遇到其他字符：检查前驱阶段是否有青蛙在等待，有则转移状态，无则返回 -1。
• 结束时：所有青蛙必须都叫完了 '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];
    }
};

以上五道题虽然场景不同，但核心都是对过程进行精确模拟。掌握这类题目的关键在于理清状态流转逻辑，并注意边界条件的处理。