模拟算法专题：替换问号、提莫攻击等 5 题详解

解题思路

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

1. 如果时间差大于等于 duration，说明上次中毒效果已完全结束，累加完整时长。
2. 如果时间差小于 duration，说明下次攻击在前次中毒结束前开始，此时只累加时间差部分，避免重复计算重叠区域。 最后别忘了加上最后一次攻击的完整 duration。

代码实现

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

041 Z 字形变换

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

解题思路

观察 Z 字形排列的规律，可以发现数据呈现周期性变化。周期长度 T = 2 * numRows - 2。

• 第一行和最后一行：字符索引间隔固定为 T。
• 中间行：每两个字符一组，分别位于当前周期的第 k 位和第 T-k 位。

利用这个数学规律，我们可以直接通过下标访问原字符串，无需构建二维数组，从而优化空间复杂度。

代码实现

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 外观数列

题目描述： 给定整数 n，返回外观数列的第 n 项。该数列由上一项的描述生成。

解题思路

这本质上是一个字符串迭代过程。对于每一项，我们需要统计连续相同字符的个数，并将'个数 + 字符'拼接成下一项。 例如：1 -> 11 (1 个 1) -> 21 (2 个 1) -> 1211 (1 个 2, 1 个 1)。 使用双指针 left 和 right 来扫描当前字符串，识别连续段。

代码实现

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

题目描述： 给定字符串 croakOfFrogs，表示多只青蛙发出的叫声混合。求最少需要多少只青蛙才能发出这些叫声。

解题思路

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

• 当遇到 'c'：如果有刚叫完 'k' 的青蛙，复用它；否则新增一只青蛙。
• 当遇到其他字符：必须存在对应的前驱字符状态的青蛙，将其状态后移一位。
• 遍历结束后，所有青蛙都应回到 'k' 状态，否则输入非法。

代码实现

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

以上五道题虽然场景不同，但核心都在于对流程的精确模拟。掌握这类题目的关键在于拆解状态变化，找到循环或递推的规律，从而写出简洁高效的代码。