模拟算法精选：替换问号、提莫攻击与 Z 字形变换等 5 题解析

这是一个典型的区间合并问题。我们只需关注相邻两次攻击的时间差：

• 如果间隔大于等于 duration，说明上次中毒效果完全释放，累加 duration。
• 如果间隔小于 duration，说明下次攻击打断了上次效果，只累加实际间隔时间。 最后别忘了加上最后一次攻击的完整 duration。

2.2 代码实现

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        if (timeSeries.empty()) return 0;
        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;
            }
        }
        // 最后一次攻击必定贡献完整的 duration
        return ret + duration;
    }
};

2.3 实战要点

注意边界情况：如果数组为空，直接返回 0。循环从第二个元素开始，每次计算与前一个元素的差值。这种分情况讨论的逻辑非常清晰，不容易出错。

041 Z 字形变换

题目描述： 将字符串按照给定的行数 numRows 以 Z 字形排列，然后按行读取生成新字符串。

3.1 算法思路

Z 字形变换本质是一个周期性问题。观察发现，字符的排列是以 2 * numRows - 2 为一个周期的。

• 第一行和最后一行是公差为该周期的等差数列。
• 中间的行除了首尾外，每个周期内有两个字符，分别位于正向和反向路径上。

我们可以直接通过数学公式计算每行字符的下标，避免构建二维数组，从而节省空间。

3.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;
    }
};

3.3 实战要点

中间行的逻辑稍微复杂一点，因为每个周期有两个字符。使用 i 和 j 两个指针同步递增，分别代表正向和反向位置的索引。只要有一个索引越界就停止该行的处理。这种写法比模拟二维数组要高效得多。

042 外观数列

题目描述： 给定一个整数 n，返回外观数列的第 n 项。外观数列每一项是对前一项的描述。

4.1 解法思路

这完全是模拟过程。对于第 i 项，我们需要遍历第 i-1 项的字符串，统计连续相同字符的个数，然后将'个数 + 字符'拼接到结果中。

4.2 代码实现

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

4.3 实战要点

使用双指针 left 和 right 来快速定位连续段。right 一直向后移动直到字符不同，此时 right - left 就是计数。记得使用 to_string 将数字转为字符串拼接。这个逻辑虽然简单，但容易在指针更新时出错，建议多调试几次。

043 数青蛙

题目描述： 给定一个由 c, r, o, a, k 组成的字符串，表示青蛙叫声。求最少需要多少只青蛙才能发出这个声音。

5.1 解法思路

这可以看作是一个状态机问题。每只青蛙都在执行 c -> r -> o -> a -> k 的状态流转。

• 遇到 c：如果有刚叫完 k 的青蛙复用，就让它继续；否则新增一只青蛙。
• 遇到其他字符：必须确保前驱状态有青蛙可用，否则非法。
• 结束时：所有青蛙必须都回到了 k 状态，否则说明叫声不完整。

5.2 代码实现

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n, 0); // 记录处于各状态的青蛙数量
        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];
    }
};

5.3 实战要点

这里的 hash 数组实际上记录了当前有多少只青蛙正处于 c, r, o, a, k 这五个阶段。关键在于状态转移的合法性检查：如果当前字符的前驱状态没有青蛙，说明顺序错了，直接返回 -1。最后还要确保没有青蛙卡在中间状态没叫完。