模拟算法详解：编程与问题分析实战

6.Z 字形变换

【题目】：6. Z 字形变换

【算法思路】

解法一：模拟

模拟过程中需要进行周期性计算，因此直接按照需求进行循环，最后遍历二维数组。由于矩阵需要一定数量的列来进行周期性计算，为了简化运算，直接使用了 n 列，即使有些列可能不会用到，也不影响结果。这样会导致空间复杂度为 O(len * n)，时间复杂度为 O(len * n)。根据结果，99% 的优化方案是通过寻找规律来减少不必要的计算。

解法二：找规律，优化模拟

通过分析同行元素的位置信息，得到公差。关键在于通过找规律，利用元素的位置关系，结合矩阵结构推导出公式，用于字符串的处理。

【代码实现】

class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.size();
        //计算公差
        int d = 2 * numRows - 2;
        if (numRows == 1) return s;
        string ret;
        //处理第一行
        for (int i = 0; i < n; i += d) ret += s[i];
        for (int k = 1; k < numRows - 1; k++) {
            //枚举 1~n-2 行
            //处理第 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];
            }
        }
        //处理最后一行
        for (int i = numRows - 1; i < n; i += d) ret += s[i];
        return ret;
    }
};

38.外观数列

【题目】：38. 外观数列

【算法思路】

使用临时 string 容器计算变化后的字符串，再将结果赋值给原始字符串。解决问题的关键在于使用 to_string 接口，将 right - left 的出现次数转换为字符串。

【代码实现】

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

1419.数青蛙

【题目】：1419. 数青蛙

【算法思路】

题目要求青蛙必须 依序 输出字母 'c', 'r', 'o', 'a', 'k'。我们需要判断最少的青蛙数目。由于字母是按照固定顺序输出的，因此在遍历过程中，可以检查当前字母是否已经在上一次出现过。

为了记录这些出现过的字母，可以使用哈希容器。这里可以通过数组来模拟哈希表进行优化。将 1 抽象为一只青蛙，在哈希表中移动即可模拟蛙鸣声。通过多次模拟，可以发现一些规律来进一步优化解决方案。

任何位置不等于零，说明还没有叫完的，当其中一种青蛙叫完，遇到'C'表示这些青蛙第二次叫。

【代码实现】

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n);
        //模拟哈希表，字符下标，字符出现次数
        unordered_map<char, int> index;
        // [x,x 字符对应下标，通过字符获当前字符下标]
        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]++, hash[i - 1]--;
            }
        }
        for (int i = 0; i < n - 1; i++)
            if (hash[i] != 0) return -1;
        return hash[n - 1];
    }
};

【个人思考】

通过数组模拟哈希表，记录字符对应的次数。为了快速查找数据，我们使用 unordered_map<char, int> index;，其中字符作为键，下标作为值，表示字符出现的次数。这样，字符和下标通过 unordered_map 绑定，可以有效地更新和查询哈希表中的青蛙移动情况，利用连续下标表示字符的出现次数。