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

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

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