算法模拟专题：LeetCode 精选例题解析

算法模拟专题

本文通过五个 LeetCode 算法题深入讲解模拟算法，涵盖字符串处理、时间区间计算、数学规律推导及状态机模拟。

39. 替换所有的问号

题目链接

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何连续重复的字符。

注意：你不能修改非 '?' 字符。题目测试用例保证除 '?' 字符之外，不存在连续重复的字符。

在完成所有转换后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。

示例 1： 输入：s = "?zs" 输出："azs" 解释：只有 'z' 是无效的修改，因为字符串 'zzs' 中有连续重复的两个 'z'。

示例 2： 输入：s = "ubv?w" 输出："ubvaw" 解释：只有替换成 'v' 和 'w' 不符合题目要求。

解题思路

遍历字符串，当碰到一个问号时，用 'a'~'z' 进行替换，并判断是否与前后的字符重复。

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;
    }
};

40. 提莫攻击

题目链接

在《英雄联盟》的世界中，有一个叫'提莫'的英雄。他的攻击可以让敌方英雄艾希进入中毒状态。