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

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

1. 替换所有问号 (LeetCode 1576)

题目描述

给你一个字符串 s，请你将所有的 ? 替换为小写英文字母，使得最终结果中不包含连续重复的字符。

解题思路

这道题的核心在于模拟替换过程。我们需要从左到右遍历字符串，当遇到 ? 时，尝试用 '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] == '?') {
                // 尝试 'a' 到 'z'
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    // 检查是否与左边不同，且与右边不同
                    bool leftOk = (i == 0 || s[i - 1] != ch);
                    bool rightOk = (i == n - 1 || s[i + 1] != ch);
                    
                    if (leftOk && rightOk) {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

细节注意

在遍历时，如果当前是 ?，我们直接修改原字符串即可。注意边界情况，比如第一个字符或最后一个字符，不需要检查不存在的邻居。

2. 提莫攻击 (LeetCode 495)

题目描述

给定一个非递减的整数数组 timeSeries，表示提莫攻击的时间点，以及一个整数 表示中毒持续时间。计算总中毒时间。