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

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;
            }
        }
        // 最后一次中毒的时间是要把中毒时间全部算上的
        return ret + duration;
    }
};

041 Z 字形变换

力扣链接： 6. Z 字形变换

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

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

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

找规律，用 row 代替行数，row = 4 时画出的 N 字形如下：

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

不难发现，数据是以 2row-2 为一个周期进行规律变换的。将所有数替换成用周期来表示的变量：

可以观察到，第一行、第四行为差为 2row-2 的等差数列；第二行、第三行除了第一个数取值为行数，每组下标为 (2n - 1 , 2n) 的数围绕（2row - 2）的倍数左右取值。

以此规律，我们可以写出迭代算法。

3.2 算法实现

class Solution {
public:
    string convert(string s, int numRows) {
        // 处理边界情况
        if (numRows == 1) return s;
        // 公差 d == 0
        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 外观数列

力扣链接： 38. 外观数列

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

4.1 解法思路：模拟

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

4.2 算法实现

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for (int i = 1; i < n; i++) // 解释 n - 1 次 ret 即可
        {
            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]; // to_string：个数转换
                left = right;
            }
            ret = tmp;
        }
        return ret;
    }
};

043 数青蛙

力扣链接： 1419. 数青蛙

题目描述： 给你一个字符串 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; // [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 - 1]--, hash[i]++; // 前驱--，当前++
            }
        }
        for (int i = 0; i < n - 1; i++)
            if (hash[i] != 0) return -1;
        return hash[n - 1];
    }
};