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

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

在这里插入图片描述

文章目录

一.模拟算法
二.例题
- 1.替换所有的问号
- 2.提莫攻击
- 3.外观数列
- 4.Z字形变换
- 5.数青蛙

一.模拟算法

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

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

二.例题

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;}}}//最后遍历整个哈希表，除了最后一个，如果出现非零元素，直接返回-1for (int i = 0;i<s.size()-1;i++){if(hash[s[i]].second){return -1;}}//返回哈希表中最后一个字符的个数return hash[s[s.size() - 1]].second;
}