【优选算法篇】：模拟算法的力量--解决复杂问题的新视角

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：优选算法篇–CSDN博客

一.模拟算法

模拟算法是通过计算机程序模仿现实世界中的系统或过程的方法。它首先根据要模拟的对象建立数学模型或逻辑模型，然后设置初始状态，并按照设定的规则和逻辑逐步推进模拟过程。模拟可以关注离散事件的发生和处理（如交通流量模拟），也可以模拟随时间连续变化的系统（如化学反应模拟）。模拟算法在科学研究、工程领域、商业和经济等多个领域有广泛应用，如预测交通拥堵、模拟城市发展和游戏开发中的物理运动等。通过模拟，我们可以对系统的行为进行分析，为决策提供依据。

简单的来说，其实就是根据题中要求模拟实现整个过程，通常会借助其他的算法来加以解决，下面通过几道例题来讲解什么是模拟算法。

二.例题

1.替换所有的问号

题目：

算法原理：

本道题比较简单，直接根据提议要求模拟实现即可。

第一层for循环表示遍历整个字符串，第二个for循环表示遇到要替换的问号是，从字符a开始，一直到字符z，选择一个符合要求的替换问号。相邻的两个字符不能重复。

代码实现：

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

    return s;
}

2.提莫攻击

题目：

算法原理：

本道题模拟实现也比较简单，具体过程就是，直接计算数组中的前后两个元素的差值，如果差值大于等于中毒时间，说明是先过了整个中毒时间之后再中下一次毒；如果差值小于中毒时间，说明上一次的中毒时间还没有过完，就从新更新中毒时间，这里的差值就是中毒时间。

依次计算每一个差值然后累加，这里有一个注意点，就是最后一个元素因为没有办法计算差值，所以在最后返回结果时要再多加一个中毒时间，因为最后一次是完整的一个中毒时间。

代码实现：

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.外观数列

题目：

算法原理：

代码实现：

string countAndSay(int n){
    string ret = "1";
    string tmp;

    //循环次数是n-1次
    for (int i = 1; i < n;i++){
        //双指针找到相同的子串
        for (int left = 0, right = 0; right < ret.size();){
            while(right<ret.size()&&ret[left]==ret[right]){
                right++;
            }
            //先插入相同字串的长度
            tmp += to_string(right - left);
            //再插入数字
            tmp += ret[left];
            //更新左指针
            left = right;
        }
        ret = tmp;
        tmp.clear();
    }
    return ret;
}

4.Z字形变换

题目：

算法原理：

虽然题目中说是Z字形变换，但实际上更像是N字形变换，建议直接看成N字形。

代码实现：

string convert(string s, int numRows){
    if(numRows==1){
        return s;
    }
    string ret;
    int k = 0;
    int d = 2 * numRows - 2;
    //第一行
    while(k*d<s.size()){
        ret += s[0 + k * d];
        k++;
    }

    //中间行
    int i = 1;
    while(i<=numRows-2){
        k = 0;
        int j = d - i;
        while(i+k*d<s.size()||j+k*d<s.size()){
            ret += s[i + k * d];
            if(j+k*d<s.size()){
                ret += s[j + k * d];
            }
            k++;
        }
        i++;
    }

    //最后一行
    k = 0;
    while(numRows-1+k*d<s.size()){
        ret += s[numRows - 1 + k * d];
        k++;
    }

    return ret;
}

5.数青蛙

题目：

算法原理：

代码实现：

int minNumberOfFrogs(string croakOfFrogs){
    string s="croak";
    unordered_map<char, pair<int,int>> hash;
    //将字符串croak中的每个字符存放到哈希表中，其中要建立映射关系，每个字符存放上一个的字符的下标以及个数
    //注意第一个字符存放的是最后一个字符的下标
    for (int i = 0; i < s.size();i++){
        if(i==0){
            hash[s[i]].first = s.size() - 1;
        }
        else{
            hash[s[i]].first = i - 1;
        }
    }

    for (auto ch : croakOfFrogs){
        if(hash[s[hash[ch].first]].second){
            hash[s[hash[ch].first]].second--;
            hash[ch].second++;
        }
        else{
            if(ch=='c'){
                hash[ch].second++;
            }
            else{
                return -1;
            }
        }
    }
    
    //最后遍历整个哈希表，除了最后一个，如果出现非零元素，直接返回-1
    for (int i = 0;i<s.size()-1;i++){
        if(hash[s[i]].second){
            return -1;
        }
    }
    
    //返回哈希表中最后一个字符的个数
    return hash[s[s.size() - 1]].second;
}

以上就是关于模拟算法的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！