算法优选：模拟类题目实战解析

问题描述： 给定非递减的时间序列数组和中毒持续时间，计算艾希的总中毒时长。若再次攻击发生在中毒期间，则刷新中毒时间。

思路分析： 这是一个区间合并的变种。我们遍历攻击时间点，判断下一次攻击是否在当前中毒效果结束之前。如果是，则累加两次攻击的时间差；否则，累加完整的中毒时长。最后一个攻击点一定会贡献完整的 duration。

代码实现：

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) return 0;
        int total = 0;
        for (int i = 0; i < timeSeries.length - 1; i++) {
            // 如果下次攻击在当前中毒期内，只算间隔时间
            if (timeSeries[i + 1] <= timeSeries[i] + duration) {
                total += timeSeries[i + 1] - timeSeries[i];
            } else {
                // 否则算满整个中毒时长
                total += duration;
            }
        }
        // 最后一次攻击必定贡献完整时长
        total += duration;
        return total;
    }
}

6. N 字形变换

问题描述： 将字符串按照指定行数进行之字形排列，然后按行读取生成新字符串。

思路分析： 观察下标变化规律。第一行和最后一行的元素间距固定为 2 * numRows - 2。中间行的元素在一个周期内有两个位置，分别对应当前行号 i 和 d - i（d 为周期）。特别地，当行数为 1 时，直接返回原字符串即可。

代码实现：

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        
        int n = s.length();
        int d = 2 * numRows - 2;
        StringBuilder ret = new StringBuilder();
        
        // 第一行
        for (int i = 0; i < n; i += d) {
            ret.append(s.charAt(i));
        }
        
        // 中间行
        for (int i = 1; i < numRows - 1; i++) {
            for (int j = i, k = d - i; j < n || k < n; j += d, k += d) {
                if (j < n) ret.append(s.charAt(j));
                if (k < n) ret.append(s.charAt(k));
            }
        }
        
        // 最后一行
        for (int i = numRows - 1; i < n; i += d) {
            ret.append(s.charAt(i));
        }
        
        return ret.toString();
    }
}

38. 外观数列

问题描述： 第 1 项是 "1"，后续每一项是对前一项的描述（例如 "11" 表示前一项有一个 1），求第 n 项。

思路分析： 这本质上是行程长度编码（RLE）的应用。可以通过递归或迭代实现。这里采用迭代方式，利用滑动窗口统计连续相同字符的数量，拼接成新的字符串。

代码实现：

class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";
        
        String prev = countAndSay(n - 1);
        StringBuilder sb = new StringBuilder();
        int len = prev.length();
        
        for (int left = 0, right = 0; right < len; ) {
            // 扩展右边界直到字符不同
            while (right < len && prev.charAt(right) == prev.charAt(left)) {
                right++;
            }
            // 记录数量
            sb.append(right - left).append(prev.charAt(left));
            // 移动左边界
            left = right;
        }
        return sb.toString();
    }
}

1419. 数青蛙

问题描述： 给定一个由 "c", "r", "o", "a", "k" 组成的字符串，计算最少需要多少只青蛙才能发出这些叫声。每只青蛙必须按顺序完成 "croak"。

思路分析： 我们可以维护一个状态机，跟踪当前有多少只青蛙处于叫出 "c", "r", "o", "a", "k" 后的等待状态。遇到 "c" 时，优先复用刚叫完 "k" 的青蛙，如果没有则新建一只。遇到其他字符时，检查是否有青蛙处于前一状态。最后检查所有青蛙是否都完成了叫声。

代码实现：

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        if (croakOfFrogs.length() % 5 != 0) return -1;
        
        // hash[0]: c, hash[1]: r, hash[2]: o, hash[3]: a, hash[4]: k
        int[] hash = new int[5];
        String s = "croak";
        
        for (char ch : croakOfFrogs.toCharArray()) {
            int idx = s.indexOf(ch);
            if (idx == -1) return -1;
            
            if (idx == 0) {
                // 遇到 'c'，优先使用刚结束的叫蛙，否则新增
                if (hash[4] > 0) hash[4]--;
                hash[0]++;
            } else {
                // 遇到其他字符，必须有前驱状态的青蛙
                if (hash[idx - 1] == 0) return -1;
                hash[idx - 1]--;
                hash[idx]++;
            }
        }
        
        // 检查是否所有青蛙都完成了叫声（即没有停留在 c,r,o,a 状态的青蛙）
        return hash[0] != 0 ? -1 : hash[4];
    }
}

以上几道题涵盖了模拟算法中常见的几种模式：边界处理、区间合并、数学规律推导、状态流转等。掌握这些核心逻辑，面对类似的模拟题时就能快速找到切入点。