模拟算法实战：替换问号、提莫攻击、Z 字形变换等 5 题详解

模拟算法专题：5 道经典题目解析

本专题聚焦于模拟类算法，涵盖字符串处理、时间序列计算及状态追踪。以下通过 C++ 实现五道典型题目，重点在于理清逻辑边界与优化遍历策略。

039 替换所有的问号

题目描述： 给定一个字符串 s，将其中所有的问号 ? 替换为小写英文字母，使得最终结果中不包含连续重复的字符。

解题思路

采用纯模拟策略。从左到右遍历字符串，遇到 ? 时，尝试用 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++) {
                    // 检查左邻居和右邻居
                    bool left_ok = (i == 0 || ch != s[i - 1]);
                    bool right_ok = (i == s.size() - 1 || ch != s[i + 1]);
                    if (left_ok && right_ok) {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

040 提莫攻击

题目描述： 在《英雄联盟》中，提莫的攻击会让目标中毒持续 duration 秒。给定攻击时间序列 timeSeries，计算总中毒时长。

解题思路

核心是计算相邻两次攻击的时间间隔。如果间隔大于等于 duration，则上次中毒完整持续；否则，只计算间隔时间。最后一次攻击必定贡献完整的 duration。

代码实现

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

041 Z 字形变换

题目描述： 将字符串按照给定的行数 numRows 以 Z 字形排列，然后按行读取生成新字符串。

解题思路

观察规律可知，字符排列具有周期性，周期 T = 2 * numRows - 2。

• 第一行和最后一行是公差为 T 的等差数列。
• 中间行除了首尾元素外，每两个一组围绕周期的倍数对称分布。

代码实现

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        
        string ret;
        int d = 2 * numRows - 2;
        int n = s.size();
        
        // 1. 处理第一行
        for (int i = 0; i < n; i += d) ret += s[i];
        
        // 2. 处理中间行
        for (int k = 1; k < numRows - 1; k++) {
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {
                if (i < n) ret += s[i];
                if (j < n) ret += s[j];
            }
        }
        
        // 3. 处理最后一行
        for (int i = numRows - 1; i < n; i += d) ret += s[i];
        
        return ret;
    }
};

042 外观数列

题目描述： 返回外观数列的第 n 项。该数列由前一项的数字读法生成（如 "1" -> "11" -> "21"）。

解题思路

本质是模拟'读'的过程。遍历上一项字符串，统计连续相同字符的个数，拼接成新的字符串。

代码实现

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for (int i = 1; i < n; i++) {
            string tmp;
            int len = ret.size();
            for (int left = 0, right = 0; right < len;) {
                while (right < len && ret[left] == ret[right]) right++;
                tmp += to_string(right - left) + ret[left];
                left = right;
            }
            ret = tmp;
        }
        return ret;
    }
};

043 数青蛙

题目描述： 给定字符串 croakOfFrogs，由多个青蛙发出的 "croak" 组成。求最少需要多少只青蛙才能发出这个叫声序列。

解题思路

模拟青蛙的状态流转。维护一个数组记录当前处于 c, r, o, a, k 各阶段的青蛙数量。

• 遇到 c：若没有刚结束叫唤的青蛙（即 k 阶段），则新增一只；否则复用。
• 遇到其他字符：必须存在前驱状态的青蛙，将其状态后移。
• 最后所有青蛙必须都完成叫唤（回到 k 或空闲），否则非法。

代码实现

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n); // 记录各阶段青蛙数量
        unordered_map<char, int> index;
        
        for (int i = 0; i < n; i++) index[t[i]] = i;
        
        for (auto ch : croakOfFrogs) {
            if (ch == 'c') {
                // 优先复用刚结束的叫蛙，如果没有则新开
                if (hash[n - 1] > 0) hash[n - 1]--;
                hash[0]++;
            } else {
                int i = index[ch];
                if (hash[i - 1] == 0) return -1; // 无前驱状态，非法
                hash[i - 1]--;
                hash[i]++;
            }
        }
        
        // 检查是否所有青蛙都完成了叫唤
        for (int i = 0; i < n - 1; i++) {
            if (hash[i] != 0) return -1;
        }
        return hash[n - 1];
    }
};

以上题目均侧重于对业务逻辑的抽象与模拟，掌握此类思维有助于解决大量涉及状态机或流程控制的工程问题。