模拟算法实战：替换问号、提莫攻击、Z 字形变换等五题详解
039 替换所有的问号
题目描述：
给定一个字符串 s，其中包含小写字母和问号 ?。你需要将所有的问号替换为小写字母，使得最终字符串中不包含连续重复的字符。
解题思路
采用贪心策略遍历字符串。遇到问号时，尝试用 a 到 z 中的字符进行替换。选择字符的关键在于它不能与前后相邻的字符相同。由于只有三个位置（前、后、当前）需要避开，而字母表有 26 个字符，总能找到一个满足条件的字符。
C++ 实现
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;
}
};
040 提莫攻击
题目描述：
在《英雄联盟》中，提莫的攻击会使目标中毒。给定攻击时间序列 timeSeries 和中毒持续时间 duration，计算总中毒时间。
解题思路
核心在于处理重叠的时间段。遍历攻击时间点，比较当前攻击与上一次攻击的时间差：
- 如果时间差大于等于
duration，说明上次中毒已完全结束，累加完整时长。 - 如果时间差小于
duration，说明上次中毒被中断，只累加时间差部分。 最后别忘了加上最后一次攻击的完整中毒时长。
C++ 实现
{
:
{
ret = ;
n = timeSeries.();
(n == ) ;
( i = ; i < n; i++) {
x = timeSeries[i] - timeSeries[i - ];
(x >= duration) {
ret += duration;
} {
ret += x;
}
}
ret + duration;
}
};
