模拟算法实战：经典题目详解
模拟算法是面试和竞赛中的高频考点，核心在于将问题转化为计算机可执行的步骤。本文选取了五道典型题目，涵盖字符串处理、区间计算、规律推导及状态机模型，通过 C++ 实现展示解题思路。
039 替换所有的问号
题目： LeetCode 1576. 替换所有的问号
解法思路
纯模拟遍历。从前往后扫描字符串，遇到 ? 时，尝试用 a~z 的字符替换。关键在于确保替换后的字符不与前后相邻字符重复。
代码实现
class Solution {
public:
string modifyString(string s) {
for (int i = 0; i < s.size(); i++) {
if (s[i] == '?') {
// 尝试 a-z 进行替换
for (char ch = 'a'; ch <= 'z'; ch++) {
// 检查是否与左右邻居冲突
if ((i == 0 || ch != s[i - 1]) &&
(i == s.size() - 1 || ch != s[i + 1])) {
s[i] = ch;
break;
}
}
}
}
return s;
}
};
技术要点：由于只需要避开左右两个字符，而字母表有 26 个，必然存在至少一个可用字符，无需回溯。
040 提莫攻击
题目： LeetCode 495. 提莫攻击
解法思路
模拟中毒过程。核心在于计算两次攻击的时间间隔与中毒持续时间的关系：
- 若间隔大于等于持续时间，上次中毒效果完整结算。
- 若间隔小于持续时间，则上次中毒被提前打断，只计算实际重叠前的时长。
代码实现
class Solution {
:
{
ret = ;
n = timeSeries.();
( i = ; i < n; i++) {
x = timeSeries[i] - timeSeries[i - ];
(x >= duration) {
ret += duration;
} {
ret += x;
}
}
ret + duration;
}
};
