LeetCode 1576 替换所有问号和 495 提莫攻击：模拟算法实战解析

39. 替换所有问号

题目描述

给定一个字符串 s，你需要将其中所有的问号 ? 替换为小写英文字母，使得替换后的字符串中不包含连续重复的字符。

思路分析

这道题的核心在于模拟替换过程。我们需要从左到右遍历字符串，一旦遇到问号，就尝试用 'a' 到 'z' 之间的字符进行填充。关键在于选择一个字符后，必须确保它既不与前面的字符相同，也不与后面的字符相同。

具体逻辑如下：

1. 遍历字符串，定位到每一个 ?。
2. 从 'a' 开始尝试替换。
3. 检查当前字符是否与左侧邻居（如果存在）冲突，以及是否与右侧邻居（如果存在）冲突。
4. 找到第一个不冲突的字符后立即填入并跳出循环，继续处理下一个问号。

C++ 代码实现

class Solution {
public:
    string modifyString(string s) {
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] == '?') {
                // 尝试用 a~z 替换
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    // 确保不与前一个字符相同，且不与后一个字符相同
                    // 注意边界情况：i==0 表示没有前驱，i==n-1 表示没有后继
                    if ((i == 0 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch)) {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

40. 提莫攻击

题目描述

在《英雄联盟》的背景设定中，提莫的攻击会让敌人进入中毒状态。给定一个非递减的整数数组 timeSeries，表示提莫攻击的时间点，以及一个整数 duration 表示中毒持续时间。每次攻击都会重置中毒计时器。请计算艾希总共处于中毒状态的秒数。

思路分析

这是一个典型的模拟结合分情况讨论的问题。我们只需要关注相邻两次攻击的时间间隔即可。

对于任意两次相邻攻击 timeSeries[i-1] 和 timeSeries[i]：

1. 如果时间间隔大于等于 duration，说明上一次中毒效果已经持续了完整的 duration 秒，中间没有重叠。
2. 如果时间间隔小于 duration，说明下一次攻击在前一次中毒结束前就已经开始了，此时实际贡献的中毒时间是两者的时间差。

最后别忘了加上最后一次攻击带来的完整 duration 秒，因为之后没有新的攻击来中断它。

C++ 代码实现

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size();
        if (n == 0) return 0;
        
        int ret = 0;
        for (int i = 1; i < n; i++) {
            // 计算相邻两次攻击的时间差
            int diff = timeSeries[i] - timeSeries[i - 1];
            // 取较小值：要么是中毒时长，要么是间隔时间
            ret += (diff < duration ? diff : duration);
        }
        // 加上最后一次攻击的完整中毒时间
        return ret + duration;
    }
};

总结

这两道题都采用了模拟的思想。第一题考察字符串遍历与边界条件的处理，第二题则侧重于区间合并的逻辑简化。在实际编码中，注意处理空数组或单元素数组的边界情况，能有效避免运行时错误。