模拟算法习题篇

在这里插入图片描述

在算法中，模拟是一种通过计算机程序来模拟现实世界中的过程或系统行为的方法。它的核心思想是根据题目给定的规则和逻辑，按照步骤细致地重现事件的发展流程，从而获得最终结果。

解题时如何使用模拟算法：

理解题目规则：仔细分析题目给出的规则和逻辑，确保理解全面。
设计模拟流程：在动手写代码之前，先在草纸上画出模拟的流程图，明确每一步的操作。
模块化实现：将模拟过程分解为多个模块，分别实现，这样可以减少错误并便于调试。
处理特殊情况：注意边界条件和特殊情况的处理，这是模拟算法中容易出错的地方。
分块调试：在实现过程中，可以先单独测试每个模块，确保其正确性。

以下是一个简单的模拟算法题目及其解题思路：题目：一只长度不计的蠕虫位于n英寸深的井的底部。它每次向上爬u英寸，但休息时会滑落d英寸。求蠕虫爬出井口需要的最少爬行次数。

解题思路：

使用循环模拟蠕虫的爬行过程。
每次循环中，蠕虫向上爬u英寸，然后滑落d英寸。
当蠕虫的总爬行高度超过井的深度时，结束循环。

代码实现：

#include <cstdio>
int main() {
    int n, u, d; // 井的深度、每次爬升高度、每次滑落高度
    scanf("%d %d %d", &n, &u, &d);
    int height = 0, steps = 0;
    while (height < n) {
        height += u;
        steps++;
        if (height >= n) break; // 如果已经爬出井口，结束循环
        height -= d;
    }
    printf("%d\n", steps);
    return 0;
}

通过上述步骤和示例，可以看到模拟算法的核心在于“照葫芦画瓢”，按照题目要求逐步实现。

1.替换所有的问号

题目描述：

给你一个仅包含小写英文字母和 '?' 字符的字符串 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;
    }
};

2.提莫攻击

题目描述：

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

当提莫攻击艾希，艾希的中毒状态正好持续 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 按 非递减 顺序排列

算法思路：

计算相邻两个时间点的差值：

i. 如果差值大于等于中毒时间，说明上次中毒可以持续 duration 秒；

ii. 如果差值小于中毒时间，那么上次的中毒只能持续两者的差值。

最后的攻击也会持续duration 秒。

代码实现：


class Solution 
{
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) 
    {
        int ret=0;
        for(int i=1;i<timeSeries.size();i++)
        {
            int x=timeSeries[i]-timeSeries[i-1];
            if(x>=duration)
              ret+=duration;
            else
              ret+=x;
        }
        return ret+duration;
    }
};

3.Z字形变换

题目描述：

将一个给定字符串 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

算法思路：

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

1         2row-3    2row-1          4row-5  4row-3

2   2row-4          2row    4row-6          4row-2

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

第一行的数是：0, 2row - 2, 4row - 4；

第二行的数是：1, (2row - 2) - 1, (2row - 2) + 1, (4row - 4) - 1, (4row - 4) + 1；

第三行的数是：2, (2row - 2) - 2, (2row - 2) + 2, (4row - 4) - 2, (4row - 4) + 2；

第四行的数是：3, (2row - 2) + 3, (4row - 4) + 3。

可以观察到，第一行、第四行为差为 2row - 2 的等差数列；第二行、第三行除了第一个数取值为行数，每组下标为(2n - 1, 2n)的数围绕（2row - 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;
    }
};

4.外观数列

题目描述：

「外观数列」是一个数位字符串序列，由递归公式定义：

countAndSay(1) = "1"
countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

给定一个整数 n ，返回 外观数列 的第 n 个元素。

示例 1：

**输入：**n = 4

输出：“1211”

解释：

countAndSay(1) = “1”

countAndSay(2) = “1” 的行程长度编码 = “11”

countAndSay(3) = “11” 的行程长度编码 = “21”

countAndSay(4) = “21” 的行程长度编码 = “1211”

示例 2：

**输入：**n = 1

输出：“1”

解释：

这是基本情况。

提示：

1 <= n <= 30

算法思路：

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

代码实现：


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];// 将字符的数量和字符本身拼接到 tmp 中
                left=right;// 更新 left 指针到下一个新的字符位置
            }
            ret=tmp;// 将生成的新序列赋值给 ret，用于下一次迭代
        }
        return ret; // 返回最终生成的序列
    }
};

5.数青蛙

题目描述：

给你一个字符串 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’ 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符；如果没有，直接返回 -1 ；

当遇到 ‘c’ 这个字符的时候，我们去看看 ‘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;//[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[index[ch]]++;
            }
            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];
    }
};

最后，笔者要说的是模拟算法虽然在某些情况下可能显得繁琐，但它具有极高的通用性和直观性，能够解决许多难以直接用数学公式或复杂数据结构求解的问题。通过上述问题的分析和实现，我们可以看到模拟算法的核心在于理解题目规则、设计清晰的模拟流程、处理特殊情况。在实际应用中，模拟算法不仅可以帮助我们快速实现解决方案，还能在复杂问题中找到规律，为进一步优化提供思路。

总之，模拟算法是算法设计中的重要工具，掌握它能够帮助我们更好地应对各种复杂问题。
在这里插入图片描述