算法刷题：替换所有问号与提莫攻击

39. 替换所有问号

题目链接：

1576. 替换所有的问号 - 力扣（LeetCode）

题目描述：

给你一个字符串 s，s 中只包含小写字母和问号。你需要将所有的问号替换为小写字母，使得最终结果中没有两个相邻的字符是相同的。

算法原理（模拟）：

思路

遍历整个字符串，找到问号之后，就用 a~z 的每一个字符去尝试替换即可，确保不与前后字符重复。

模拟解法代码（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 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch)) {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

---

40. 提莫攻击

题目链接：

495. 提莫攻击 - 力扣（LeetCode）

题目描述：

在《英雄联盟》的世界中，有一个叫'提莫'的英雄。他的攻击可以让敌方英雄艾希进入中毒状态。当提莫攻击艾希时，艾希的中毒状态正好持续 duration 秒。请你返回艾希处于中毒状态的总秒数。

解法（模拟 + 分情况讨论）：

算法思路

模拟 + 分情况讨论。计算相邻两个时间点的差值：

• 如果差值大于等于中毒时间，说明上次中毒可以持续 duration 秒。
• 如果差值小于中毒时间，那么上次的中毒只能持续两者的差值。

C++ 算法代码

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size(), ret = 0;
        for (int i = 1; i < n; i++) {
            if (timeSeries[i] - timeSeries[i - 1] < duration)
                ret += timeSeries[i] - timeSeries[i - 1];
            else
                ret += duration;
        }
        // 加上最后一次攻击的中毒时间
        return ret + duration;
    }
};

总结

替换所有问号（LeetCode 1576）使用模拟方法遍历字符串，遇到问号时用 a-z 字符替换，确保不与相邻字符重复；提莫攻击（LeetCode 495）通过分情况讨论计算中毒总时长：若攻击间隔大于中毒时间则累加 duration，否则累加实际间隔时间。