模拟算法专题：替换问号、提莫攻击、Z 字形变换、外观数列与数青蛙

041 Z 字形变换

题目描述： 将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列。

3.1 算法思路：模拟 + 找规律

3.1.1 表格：row = 4 时各行的数字序列

3.1.2 表格：用周期 T = 2row - 2 表示的数字规律

不难发现，数据是以 2row-2 为一个周期进行规律变换的。 第一行、第四行为差为 2row-2 的等差数列；第二行、第三行除了第一个数取值为行数，每组下标围绕周期的倍数左右取值。

3.2 算法实现

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        string ret;
        int d = 2 * numRows - 2, 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 外观数列

题目描述： 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。例如：

1. 1
2. 11
3. 21
4. 1211 ...

4.1 解法思路：模拟

所谓【外观数列】，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。

4.2 算法实现

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" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 "croak" 。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

5.1 解法：状态机模拟

模拟青蛙的叫声。

• 当遇到 'r', 'o', 'a', 'k' 这四个字符的时候，我们要去看看每一个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符；如果没有，直接返回 -1；
• 当遇到 'c' 这个字符的时候，我们去看看 'k' 这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去喊 'c' 这个字符；如果没有的话，就重新搞一个青蛙。

5.2 算法实现

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