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

041 Z 字形变换

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

解题思路

观察 Z 字形的规律，可以发现字符是按周期循环填充的。周期长度 T = 2 * numRows - 2。

• 首行和末行：每隔 T 个字符取一个。
• 中间行：每两个字符一组，分别位于第 k 个和第 T-k 个偏移量处。

我们可以直接通过数学公式计算每一行的索引，无需构建二维数组，从而优化空间复杂度。

表格辅助理解

当 row = 4 时，周期 T = 6：

C++ 实现

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，返回外观数列的第 n 项。该数列由递归规则生成：每一项是对前一项的描述。

解题思路

这是一个典型的递归或迭代模拟问题。我们需要统计上一轮字符串中连续相同字符的个数及其值，拼接成下一轮字符串。 例如："1" -> "11" (1 个 1) -> "21" (2 个 1) -> "1211" (1 个 2, 1 个 1)。 使用双指针法遍历字符串即可高效完成统计。

C++ 实现

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，由字符 'c', 'r', 'o', 'a', 'k' 组成，代表青蛙叫声。求最少需要多少只青蛙才能发出这个叫声序列。

解题思路

这实际上是一个状态机问题。每只青蛙必须按顺序发出 c->r->o->a->k 的声音。

• 维护一个计数器数组，记录处于各个发声阶段的青蛙数量。
• 遇到 'c'：如果有刚叫完 'k' 的青蛙复用，则减少其计数；否则新增一只青蛙。
• 遇到其他字符：检查前驱状态是否有青蛙可用，若有则转移状态，否则非法。
• 结束时所有青蛙应都回到 'k' 状态。

C++ 实现

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

以上五个题目涵盖了模拟算法中的常见模式：贪心替换、区间合并、周期性规律、字符串压缩及状态机计数。掌握这些核心逻辑，能显著提升解决此类问题的效率。