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

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

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

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

文章目录

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

1576.替换所有的问号

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

class Solution {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. 提莫攻击

【算法思路】

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

【代码实现】

class Solution {public: int findPoisonedDuration(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%的优化方案是通过寻找规律来减少不必要的计算。

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

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

【代码实现】

class Solution {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的出现次数转换为字符串。

【代码实现】

class Solution {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’表示这些青蛙第二次叫。

【代码实现】

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[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 index;，其中字符作为键，下标作为值，表示字符出现的次数。这样，字符和下标通过 unordered_map 绑定，可以有效地更新和查询哈希表中的青蛙移动情况，利用连续下标表示字符的出现次数

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