算法模拟实战：替换所有问号与提莫攻击解析

前言

聚焦算法题实战，系统讲解优选算法。通过剖析动态规划、二分法等高效策略，学会寻找最优解。内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。

1576. 替换所有的问号

题目链接： LeetCode 1576

题目描述：

示例：

解题思路

这道题的核心在于模拟替换过程。我们需要遍历字符串，遇到问号时，尝试用 'a' 到 'z' 的字符进行替换。关键约束是替换后的字符不能与前后相邻的字符重复。由于只需要避免重复，且字母表有 26 个字符，通常第一个不冲突的字符即可满足条件。

C++ 代码实现

class Solution {
public:
    string modifyString(string s) {
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] == '?') {
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    // 检查是否与左边或右边字符重复
                    if ((i == 0 || ch != s[i - 1]) && 
                        (i == n - 1 || ch != s[i + 1])) {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

笔记展示

495. 提莫攻击

题目链接： LeetCode 495

题目描述：

示例：

解题思路

本题采用模拟加分情况讨论的方法。核心逻辑是计算相邻两次攻击的时间差：

1. 如果时间差大于等于中毒持续时间 duration，说明上次中毒效果已完全结束，累加完整的 duration。
2. 如果时间差小于 duration，说明下次攻击在中毒期间提前触发，此时只累加实际的时间差。

更简洁的写法是直接累加 min(duration, 时间差)，最后别忘了加上最后一次攻击带来的完整中毒时间。

C++ 代码实现

方案一：分情况判断

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size(), effect = 0;
        for (int i = 1; i < n; i++) {
            int sub = timeSeries[i] - timeSeries[i - 1];
            if (sub >= duration) {
                effect += duration;
            } else {
                effect += sub;
            }
        }
        return effect + duration;
    }
};

方案二：利用 min 函数简化

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size(), effect = 0;
        for (int i = 1; i < n; i++) {
            int sub = timeSeries[i] - timeSeries[i - 1];
            effect += min(sub, duration);
        }
        return effect + duration;
    }
};

笔记展示