算法实战:替换所有问号与提莫攻击
今天我们来聊聊两道经典的模拟类算法题,分别是 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,表示每次攻击的时间点,以及一个整数 表示中毒持续时间。计算艾希总共处于中毒状态的时间。


