【优选算法 | 模拟】探索模拟算法: 编程与问题分析的双重 考验

在本篇文章中，我们将深入解析模拟算法的原理。从基础概念到实际应用，带你了解如何通过模拟算法高效解决各种问题。无论你是刚接触算法的新手，还是希望提升编程能力的老手，模拟算法都是你提升问题解决能力的重要工具！

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志 我自踏雪至山巅

文章目录

• 1576.替换所有的问号
• 495.提莫攻击
• 6.Z 字形变换
• 38. 外观数列
• 1419. 数青蛙

1576.替换所有的问号

【题目】：1576. 替换所有的问号

classSolution{public: string modifyString(string s){int n = s.size();for(int i =0; i < n; i++){if(s[i]=='?'){for(int 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;}};

在判断 ch 与相邻字符时，除了正常情况下检查 ch != s[i - 1] 和 ch != s[i + 1]，还需要考虑边界条件。对于 i == 0，表示没有左边字符，应该只检查右边字符；对于 i == n - 1，表示没有右边字符，应该只检查左边字符。因此，条件可以改为：if((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1]))

495.提莫攻击

【题目】：495. 提莫攻击

【算法思路】

基本算法思想就是模拟，根据题目要求编写代码，注意当到最后一个位置需要单独加上中毒时间。

【代码实现】

classSolution{public:intfindPoisonedDuration(vector<int>& timeSeries,int duration){int n = timeSeries.size();//记录中毒时间int ret =0;for(int i =1; i < n; i++){int x = timeSeries[i]- timeSeries[i -1];if(x >= duration) ret += duration;else ret += x;}return ret + duration;}};

6.Z 字形变换

【题目】：6. Z 字形变换

【算法思路】

解法一：模拟

模拟过程中需要进行周期性计算，因此直接按照需求进行循环，最后遍历二维数组。由于矩阵需要一定数量的列来进行周期性计算，为了简化运算，直接使用了n列，即使有些列可能不会用到，也不影响结果。这样会导致空间复杂度为O(len * n)，时间复杂度为O(len * n)。根据结果，99%的优化方案是通过寻找规律来减少不必要的计算。

解法二：找规律，优化模拟

通过分析同行元素的位置信息，得到公差。关键在于通过找规律，利用元素的位置关系，结合矩阵结构推导出公式，用于字符串的处理。

【代码实现】

classSolution{public: string convert(string s,int numRows){int n = s.size();//计算公差int d =2* numRows -2;if(numRows ==1)return s; string ret;//处理第一行for(int i =0; i < n; i += d) ret += s[i];for(int k =1; k < numRows -1; k++)//枚举1~n-2 行{//处理第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];}}//处理最后一行for(int i = numRows -1; i < n; i += d) ret += s[i];return ret;}};

38. 外观数列

【题目】：38. 外观数列

【算法思路】

使用临时string容器计算变化后的字符串，再将结果赋值给原始字符串。解决问题的关键在于使用to_string接口，将right - left的出现次数转换为字符串。

【代码实现】

classSolution{public: string countAndSay(int n){ string s ="1";for(int i =1; i < n; i++){ string ret;int len = s.size();for(int left =0, right =0; right < len;){while(right < len && s[left]== s[right]) right++; ret +=to_string(right - left)+ s[left]; left = right;} s = ret;}return s;}};

1419. 数青蛙

【题目】：1419. 数青蛙

【算法思路】

题目要求青蛙必须 依序 输出字母 ‘c’, ’r’, ’o’, ’a’, ’k’。我们需要判断最少的青蛙数目。由于字母是按照固定顺序输出的，因此在遍历过程中，可以检查当前字母是否已经在上一次出现过。

为了记录这些出现过的字母，可以使用哈希容器。这里可以通过数组来模拟哈希表进行优化。将1抽象为一只青蛙，在哈希表中移动即可模拟蛙鸣声。通过多次模拟，可以发现一些规律来进一步优化解决方案。

任何位置不等于零，说明还没有叫完的，当其中一种青蛙叫完，遇到’C’表示这些青蛙第二次叫。

【代码实现】

classSolution{public:intminNumberOfFrogs(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[0]++;}else{int i = index[ch];if(hash[i -1]==0)return-1; hash[i]++,hash[i -1]--;}}for(int i =0; i < n -1; i++)if(hash[i]!=0)return-1;return hash[n -1];}};

【个人思考】

通过数组模拟哈希表，记录字符对应的次数。为了快速查找数据，我们使用 unordered_map<char, int> index;，其中字符作为键，下标作为值，表示字符出现的次数。这样，字符和下标通过 unordered_map 绑定，可以有效地更新和查询哈希表中的青蛙移动情况，利用连续下标表示字符的出现次数

快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！