算法沉淀——模拟（leetcode真题剖析）

模拟算法是一种通过模拟问题的描述或场景来解决问题的算法。这种算法的核心思想是按照问题描述的规则，逐步模拟问题的发展过程，从而得到问题的解决方案。通常，模拟算法涉及到对问题的具体步骤进行逐一模拟，而不依赖于数学公式或高级的数据结构。

在模拟算法中，通常需要考虑到问题的初始状态、模拟的步骤、状态的变化规律以及终止条件。这种算法的实现可以使用编程语言来逐一执行模拟的步骤，通常需要一些控制结构、循环和条件语句来进行模拟。

虽然模拟算法可能在某些情况下效率较低，但它们通常具有直观、清晰、易于理解的特点，适用于一些实际问题的建模和求解。

01.替换所有的问号

题目链接：https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你 不能 修改非 '?' 字符。

题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

提示：

• 1 <= s.length <= 100
• s 仅包含小写英文字母和 '?' 字符

思路

这里我们使用最朴素的模拟，从前往后遍历整个字符串，找到问号之后，就⽤ a ~ z 的每⼀个字符去尝试替换即可。

代码

class Solution {
   
public:
    string modifyString(string s) {
   
        int n=s.size();
        for(int i=0;i<n;++i){
   
            if(s[i]=='?'){
   
                for(char ch='a';ch<='z';++ch){
   
                    if((i==0||ch!=s[i-1])&&(i==n-1||ch!=s[i+1])){
   
                        s[i]=ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

02.提莫攻击

题目链接：https://leetcode.cn/problems/teemo-attacking/

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的 总 秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

提示：

• 1 <= timeSeries.length <= 104
• 0 <= timeSeries[i], duration <= 107
• timeSeries 按 非递减 顺序排列

思路

这里这道题最简单的思路就是我们从头到尾遍历进行模拟，通过观察我们不难发现当前位置减去前一个位置，如果差值大于中毒时长，那就加上中毒时长，如果小于，那就加上差值，最后再加上最后一次的正常中毒时长即可

代码

class Solution {
   
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
   
        int n = timeSeries.size();  // 获取时间序列的长度
        int sum = duration;         // 初始化总持续时间为一个初始的毒药持续时间

        // 循环遍历时间序列
        for (int i = 1; i < n; ++i) {
   
            // 计算当前时间点与上一个时间点之间的时间差，并取较小值与毒药持续时间相加
            sum += min(abs(timeSeries[i] - timeSeries[i - 1]), duration);
        }

        return sum;  // 返回总持续时间
    }
};

解释：

• n 是时间序列的长度。
• sum 初始化为毒药的持续时间，因为最后一个时间点之间没有时间差。
• 在循环中，计算当前时间点与上一个时间点之间的时间差，取该差值与毒药持续时间的较小值，然后加到总持续时间 sum 上。

03.Z字形变换

题目链接：https://leetcode.cn/problems/zigzag-conversion/

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A" 

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

思路

我们最容易想到的模拟方式就是用一个二维数组按照规律进行存取，但是这样时间复杂度太高了，我们可以通过画图的方式看看能不能找到规律直接在字符串中进行提取。

代码

class Solution {
   
public:
    string convert(string s, int numRows) {
   
        if (numRows == 1) return s;  // 如果 numRows 为1，直接返回原字符串
        string ret;  // 用于保存结果的字符串
        int d = 2 * numRows - 2;  // 计算每个 Z 字形的周期长度
        int n = s.size();  // 字符串的长度

        // 遍历每个 Z 字形的第一行
        for (int i = 0; i < n; i += d) {
   
            ret += s[i];
        }

        // 遍历每个 Z 字形的中间行
        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];
            }
        }

        // 遍历每个 Z 字形的最后一行
        for (int i = numRows - 1; i < n; i += d) {
   
            ret += s[i];
        }

        return ret;  // 返回结果字符串
    }
};

解释：

• 如果 numRows 为1，直接返回原字符串，否则会陷入死循环。
• d 计算每个 Z 字形的周期长度，即一个完整的上下走一遍的长度。
• 遍历每个 Z 字形的第一行，将对应字符加入结果字符串 ret。
• 遍历每个 Z 字形的中间行，根据 Z 字形的周期，将对应字符加入结果字符串。
• 遍历每个 Z 字形的最后一行，将对应字符加入结果字符串。

04.外观数列

题目链接：https://leetcode.cn/problems/count-and-say/

给定一个正整数 n ，输出外观数列的第 n 项。

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

你可以将其视作是由递归公式定义的数字字符串序列：

• countAndSay(1) = "1"
• countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示：

• 1 <= n <= 30

思路

这里我们按照需求逐个进行计算即可

代码

class Solution {
   
public:
    string countAndSay(int n) {
   
        string ret = "1";  // 初始值为 "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 为新生成的字符串
            ret = tmp;
        }

        return ret;
    }
};

05.数青蛙

题目链接：https://leetcode.cn/problems/minimum-number-of-frogs-croaking/

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。

示例 1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次

示例 2：

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。

提示：

• 1 <= croakOfFrogs.length <= 105
• 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

思路

其实这里我们可以使用哈希存储来模拟这五个字符的出入及完整性，我们在遇到字符r o a k四个字符时，若该字符前驱字符存在，前驱字符–，当前字符++，若不存在，说明字符串不合法，遇到字符c时，若哈希表最后一个字符存在，最后一个字符–，当前字符++，这样我们可以保证最少的青蛙数，若不存在，当前字符直接++即可，最后遍历完字符串，只有k的映射值存在才合法，若前面的字符仍有计数，说明字符串不完整。我们还可以使用长度为5的数组来做相对映射，这样可以减少空间的使用，比起使用容器的读写效率都要更高，缺点就是代码稍长。

代码

class Solution {
   
public:
    int minNumberOfFrogs(string croakOfFrogs) {
   
       int hash[5]={
   0};
       int n=croakOfFrogs.size();
       for(int i=0;i<n;i++){
   
           if(croakOfFrogs[i]=='c'){
   
               if(hash[4]>0){
   
                   hash[4]--;
                   hash[0]++;
               }
               else hash[0]++;
           }
           else if(croakOfFrogs[i]=='r'){
   
               if(hash[0]>0){
   
                   hash[0]--;
                   hash[1]++;
               }else return -1;
           }
           else if(croakOfFrogs[i]=='o'){
   
               if(hash[1]>0){
   
                   hash[1]--;
                   hash[2]++;
               }else return -1;
           }
           else if(croakOfFrogs[i]=='a'){
   
               if(hash[2]>0){
   
                   hash[2]--;
                   hash[3]++;
               }else return -1;
           }
           else if(croakOfFrogs[i]=='k'){
   
               if(hash[3]>0){
   
                   hash[3]--;
                   hash[4]++;
               }else return -1;
           }
           else return -1;
       }
       if(hash[0]||hash[1]||hash[2]||hash[3]) return -1;
       return hash[4]; 
    }
};