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

代码实现

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        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;
            }
        }
        // 最后一次攻击必定贡献完整的 duration
        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"。

解题思路

本质是迭代统计连续相同字符的个数。使用双指针 left 和 right 扫描当前字符串，当字符不同时，记录个数并拼接字符，作为下一轮输入。

代码实现

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 的青蛙可用则复用，否则新增一只。
• 遇到其他字符：检查前驱状态是否存在，不存在则非法。
• 最终检查所有青蛙是否都完成了叫声（即没有卡在中间状态的青蛙）。

代码实现

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

总结： 这五道题均围绕模拟过程展开，关键在于准确理解题意中的状态变化规则，并妥善处理边界情况。