算法实战：替换所有问号与提莫攻击
今天我们来聊聊两道经典的模拟类算法题，分别是 LeetCode 1576'替换所有的问号'和 495'提莫攻击'。这两道题虽然场景不同，但核心都在于对边界条件和状态变化的细致处理。
1576. 替换所有的问号
题目要求：
给定一个字符串 s，其中包含小写英文字母和问号 ?。你需要将每个 ? 替换为一个小写字母，使得最终字符串中没有任何两个相邻字符是相同的。如果存在多个解，返回任意一个即可。
解题思路：
这道题的核心逻辑其实很直观，就是模拟替换过程。我们从头到尾遍历字符串，一旦遇到 ?，就尝试用 a 到 z 的字符去填充。关键约束条件是：新填入的字符不能等于它左边的字符（如果存在），也不能等于右边的字符（如果存在）。
这里有个细节需要注意：当 ? 位于字符串开头或结尾时，只需要检查一侧的邻居即可。由于字母表有 26 个字符，而最多只有 2 个邻居需要避开，所以一定能找到合适的字符。
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;
}
};
495. 提莫攻击
题目要求：
在《英雄联盟》的背景故事中，提莫的攻击会让艾希中毒。给定一个非递减的整数数组 timeSeries，表示每次攻击的时间点，以及一个整数 duration 表示中毒持续时间。计算艾希总共处于中毒状态的时间。
解题思路： 这是一个典型的区间合并问题，但我们可以用更简单的模拟方式解决。我们需要关注的是两次攻击之间的时间间隔。
- 间隔大于等于 duration：说明上一次中毒效果已经完全释放，中间有一段完全清醒的时间。此时累加完整的
duration。 - 间隔小于 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];
// 如果间隔小于中毒时长，只算间隔；否则算完整时长
if (diff < duration) {
ret += diff;
} else {
ret += duration;
}
}
// 加上最后一次攻击带来的完整中毒时间
return ret + duration;
}
};
总结
这两道题都是考察基础逻辑和边界处理的典型例子。替换问号题重点在于遍历时的局部约束检查，而提莫攻击题则考验对时间轴上区间重叠关系的理解。掌握这类模拟思维，对于解决其他涉及状态流转的算法题很有帮助。
