算法专题:模拟算法实战
本文选取了五道典型的模拟类算法题,涵盖字符串处理、时间区间计算、字符重排及状态计数。通过遍历与规律分析,解决去重、中毒时长统计、Z 字形转换、外观数列描述及青蛙叫声匹配问题。
039 替换所有的问号
题目链接: 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;
}
};
注意: 实际编码时,边界条件(首尾字符)要单独判断,避免数组越界。
040 提莫攻击
题目链接: 495. 提莫攻击
解题思路
这是一个典型的时间区间合并问题。我们只需关注相邻两次攻击的时间差:


