【优选算法】Simulation-Phoenix：模拟算法的重生涅槃
文章目录
本篇是优选算法之模拟算法，是一种依据问题给定的规则与逻辑，按步骤细致地重现事件的发展流程，进而获取最终结果的算法
1.概念解析
🚩什么是模拟算法？
简单来说就是照葫芦画瓢，题目说啥就照着写代码就行，所以很考察代码能力2.替换所有的问号
✏️题目描述：
✏️示例：
传送门：替换所有的问号
题解:
这题很简单，显然是先遍历一遍数组，然后在遍历的时候，如果遇到？就替换为与该位置前后都不相同的数，所以也要对要替换的数遍历一遍，直到发现合适的数
💻细节问题：
注意边界情况，没有两个相邻的数💻代码实现：
#include<iostream>#include<vector>usingnamespace std;classSolution{public: 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|| ch != s[i -1])&&(i == s.size()-1|| ch != s[i +1])){ s[i]= ch;break;}}}}return s;}};3.提莫攻击
✏️题目描述：
✏️示例：
传送门：提莫攻击
题解:
做模拟算法题的精髓就是要画图，只有图画明白了，才能找到规律，而不是凭空想象
所以根据规律发现相邻两数之差是突破点，如果相邻两数之差大于duration，那么不用重置中毒时间；如果相邻两数之差小于duration，那么要重置中毒时间
💻代码实现：
#include<iostream>#include<vector>usingnamespace std;classSolution{public:intfindPoisonedDuration(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;}};4.Z字形变换
✏️题目描述：
✏️示例：
传送门：Z字形变换
题解:
本题的意思是要你根据题目给出的Z字形字符串，将其从上到下，从左至右的方式以一个新字符串的方式返回，显然这是一个找规律性极强的题目，所以画图！画图！画图！
💻第一步：
首先我们将每个数的索引按照Z字形填入，我们是从第一行开始录入，所以可以发现第一行和最后一行都是一个等差数列，然后发现规律，公差是0~6之间元素的个数，所以得出d=2n-2
💻第二步：
接下来处理中间的行数，发现如图的1 ~ 7 ~ 13，5 ~ 11 ~ 17也是以6为公差，只不过是两个数两个数的差，所以得出规律（k，d-k）
💻细节问题：
注意for循环的判断条件为i < n || j < k，而不是&&，因为当一个越界之后，另一个可能还没越界判断完
💻代码实现：
#include<iostream>#include<vector>usingnamespace std;classSolution{public: string convert(string s,int numRows){if(numRows ==1){return s;} string ret;int n = s.size();int d =2* numRows -2;for(int i =0; i < n; i += d){ ret += s[i];}for(int k =1; k < numRows -1;++k){for(int i = k, j = d - k; i < n || j < k; i += d, j += d){if(i < n){ ret += s[i];}if(j < n){ ret += s[j];}}}for(int i = numRows -1; i < n; i += d){ ret += s[i];}return ret;}};5.外观序列
✏️题目描述：
✏️示例：
传送门：外观序列
题解:
其实题目意思就是对上一行的序列进行解释，比如第三行为21，那么第四行的意思就是一个2一个1
💻细节问题：
所以很明显这题要用双指针解决，因为要持续向后查找有几个相同的，直到不同为止
left和right都从0开始，然后right向后移动，直到该位置和前一个位置不相同，然后记录长度和数字，直接让left=right，开始下一段
💻代码实现：
#include<iostream>#include<string>usingnamespace std;classSolution{public: string countAndSay(int n){ string ret ="1";for(int i =1; i < n;++i){ string tmp;int len = ret.size();for(int left =0, right =0; right < len;){while(ret[left]== ret[right]){ right++;} tmp +=to_string(right - left)+ ret[left]; left = right;} ret = tmp;}return ret;}};6.数青蛙
✏️题目描述：
✏️示例：
传送门：数青蛙
题解:
要理解本题题意，就是一只青蛙要完整叫完croak，如果一只青蛙没叫完，那么就需要另一只青蛙来发出叫声
💻第一步：
首先，以如图所示为例子，第一个c，计入该位置为1，接下来到r，该位置变为1，上一个位置变为0，可以理解为一个1一直在移动，表示这个叫声遍历到哪里了，直到遍历到k为止
💻第二步：
注意在遍历过程中注意要像图中分类，对于字符c，若k位置不为0，那么表示有青蛙闲置，那么之前叫完的青蛙就可以再次叫；对于其他字符，要找该字符的前一个字符符不符合croak的顺序和字符，若不符合字符，直接返回-1
💻细节问题：
注意处理完所有字符时，要判断一下是否还有没叫完的叫声💻代码实现：
#include<iostream>#include<vector>#include<unordered_map>#include<string>usingnamespace std;classSolution{public:intminNumberOfFrogs(string croakOfFrogs){ string t ="croak";int n = t.size(); vector<int>hash(n); unordered_map<char,int> index;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];}};希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
