什么是模拟算法模拟算法顾名思义就是按照题目描述的规则一步一步地用代码“扮演”或“重演”整个过程最终得到结果。它通常没有特别高深的数学公式或复杂的算法推导核心难点在于理清逻辑、处理边界、将自然语言描述的流程准确翻译成代码。就像拍电影一样题目是剧本你的代码就是演员必须严格按照剧本一步步演下去。在算法竞赛和面试中模拟题往往被视为“基础题”或“细节题”它不考验你背诵了多少高级模板而是考验你的代码实现能力和逻辑严密性。题目一:替换所有的问号class Solution { public: string modifyString(string s) { int n s.size(); for (int i 0; i n; i) { if (s[i] ?) { for (char 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; } };遍历整个字符串使用一个for循环从左到右扫描字符串中的每一个字符。判断是否为?如果当前字符不是?直接跳过题目要求不能修改非?字符。如果是?开始贪心寻找替换字母让一个变量ch从a遍历到z。对于每一个ch检查它是否与左邻居和右邻居相同。左邻居检查如果当前不是第一个字符i 0则要求ch ! s[i-1]如果是第一个字符左边没有邻居直接满足条件。右邻居检查如果当前不是最后一个字符i n - 1则要求ch ! s[i1]如果是最后一个字符右边没有邻居直接满足条件。如果ch同时满足了左右邻居的条件说明找到了一个合法的字母将其填入s[i]并立刻break跳出内层循环继续处理下一个?。返回结果遍历结束后原字符串s已经被修改完毕直接返回s。题目二提莫攻击class Solution { public: int findPoisonedDuration(vectorint timeSeries, int duration) { int ret0; for(int i1;itimeSeries.size();i) { int tmptimeSeries[i]-timeSeries[i-1]; if(tmpduration) retduration; else rettmp; } return retduration; } };核心思想是累加每次攻击的“有效持续时间”最后再加上最后一次攻击的完整duration。int ret0;初始化总中毒时间为 0。for(int i1; itimeSeries.size(); i)从第二次攻击开始遍历。int tmp timeSeries[i] - timeSeries[i-1];计算当前攻击与上一次攻击的时间间隔。核心判断逻辑if(tmp duration) ret duration;如果时间间隔大于等于中毒持续时间说明上一次中毒已经结束本次攻击贡献了完整的duration秒。else ret tmp;如果时间间隔小于中毒持续时间说明上一次中毒还没结束就被刷新了上一次攻击实际只贡献了tmp秒的有效中毒时间。return ret duration;循环只计算了前n-1次攻击的贡献最后一次攻击必定会带来完整的duration秒中毒时间所以最后加上去。题目三Z字形变换class Solution { public: string convert(string s, int numRows) { if (numRows 1) return s; string ret; int d 2 * numRows - 2, n s.size(); // 第一行 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 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; } };核心思路解析这种解法的关键是找到每一行字符在原字符串s中的下标规律。计算周期d:int d 2 * numRows - 2;这是 Z 字形一个完整周期从第一行往下走到最后一行再走回第一行上方所包含的字符数量。例如numRows 3周期d 2 * 3 - 2 4。其下标走向是0 - 1 - 2 - 1 - 0确实是 4 步一个循环。下面我以numRows 4为例为你详细拆解每一行的规律。当numRows 4时周期d 2 * 4 - 2 6。Z 字形的排列和对应的下标如下第0行: 0 6 12 第1行: 1 5 7 11 13 第2行: 2 4 8 10 14 第3行: 3 9 151. 第一行第 0 行的规律序列0, 6, 12, ...规律每个周期只有一个字符。步长每次下标直接增加一个周期长度d。公式下标为0, 0d, 02d, ...。即从0开始每次加d。2. 最后一行第 numRows-1 行这里是第 3 行的规律序列3, 9, 15, ...规律和第一行一样每个周期也只有一个字符出现在 Z 字形的折返点。步长每次下标增加一个周期长度d。公式下标为numRows-1, numRows-1d, numRows-12d, ...。即从numRows-1开始每次加d。3. 中间行第 1 行到第 numRows-2 行的规律 —— 最复杂的部分中间行是这道题的难点因为每一行在一个周期内会出现两个字符除了第一行和最后一行只有一个。以第 1 行为例序列1, 5, 7, 11, 13, ...分组看(1, 5), (7, 11), (13, ...)每个括号是一个周期内的两个字符。规律第一个字符的下标是1, 7, 13...。它是从当前行号1开始每次增加周期d即 1 6 7。第二个字符的下标是5, 11, ...。它是从5开始每次增加周期d即 5 6 11。那么第二个字符的起始下标5是怎么来的呢5 d - 当前行号 6 - 1 5。以第 2 行为例序列2, 4, 8, 10, 14, ...分组看(2, 4), (8, 10), (14, ...)规律第一个字符下标从当前行号2开始每次加d2 6 8。第二个字符下标从d - 当前行号 6 - 2 4开始每次加d4 6 10。总结中间行的通用公式对于任意一个中间行k1 k numRows - 2在一个周期内它对应两个下标第一个下标i k第二个下标j d - k进入下一个周期这两个下标都加上di i dj j d代码实现对应的逻辑for(int k 1; k numRows - 1; k) // 枚举中间的每一行 k { // i 就是上面说的第一个下标j 是第二个下标 // i 每次加 dj 也每次加 d 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]; // 再加上这一周期第二个字符 } }题目四外观数列class Solution { public: string countAndSay(int n) { string ret 1; for(int i 1; i n; i) { string tmp; int len ret.size(); for(int left0,right0;rightlen;) { while(right len ret[left]ret[right]) right; tmpto_string(right-left) ret[left]; leftright; } rettmp; } return ret; } };核心思路解析外层循环控制迭代次数string ret 1; for(int i 1; i n; i)因为题目已知countAndSay(1) 1所以ret初始化为1。我们需要从第 2 项开始计算一直计算到第n项因此循环执行n - 1次。内层双指针统计连续字符int len ret.size(); for(int left 0, right 0; right len; ) { while(right len ret[left] ret[right]) right; tmp to_string(right - left) ret[left]; left right; }这是这段代码最核心、最优雅的部分。left和right指针初始都指向当前字符串的开头。while循环right指针不断向右移动直到遇到与ret[left]不同的字符或者到达字符串末尾。此时right - left就是这组连续相同字符的个数。拼接结果使用to_string(right - left)将个数转换为字符串再加上字符本身ret[left]拼接到临时字符串tmp中。这正是“报数”的规则。移动left将left移动到right的位置开始统计下一组连续字符。更新结果ret tmp;内层循环结束后tmp存储了当前项的“报数”结果将其赋值给ret以便进行下一次迭代。题目五数青蛙class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { string t croak; int n t.size(); vectorint hash(n); unordered_mapchar, 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 - 1]--; hash[i]; } } for (int i 0; i n - 1; i) if (hash[i] ! 0) return -1; return hash[n - 1]; } };核心思路解析这道题的难点在于同一时间可以有多只青蛙在叫我们需要判断当前的字符应该接在哪只青蛙的后面从而最小化青蛙的总数。代码通过维护一个“状态数组”完美解决了这个问题。状态定义哈希表hashstring t croak; vectorint hash(n); // n 5 unordered_mapchar, int index; // 记录 c,r,o,a,k 对应的下标 0~4hash[i]表示当前正处于第i个发声阶段即刚刚叫完t[i]这个字母的青蛙数量。hash[0]刚叫完 c 的青蛙数量hash[1]刚叫完 r 的青蛙数量...hash[4]刚叫完 k即完成一次鸣叫的青蛙数量遍历字符串进行状态转移for(auto ch : croakOfFrogs) { ... }情况 A遇到字符c新一轮鸣叫的开始if(ch c) { if(hash[n - 1] ! 0) hash[n - 1]--; // 关键优化复用已经叫完的青蛙 hash[0]; }当遇到c时说明有一只青蛙要开始叫了。此时有两种选择找一只已经叫完hash[4] 0的青蛙让它接着叫。这叫“复用”能节省青蛙总数。如果没有空闲的青蛙就只能增加一只新青蛙hash[0]。您的代码优先选择复用if(hash[4] ! 0) hash[4]--;然后再hash[0]。这行代码等价于把一只完成状态的青蛙变成了准备开始的状态。情况 B遇到其他字符r, o, a, kelse { int i index[ch]; if(hash[i - 1] 0) return -1; // 非法情况没有青蛙处于前一个阶段 hash[i - 1]--; hash[i]; }例如遇到r它必须由一只刚叫完chash[0]的青蛙来发出。如果hash[0] 0说明前面没有青蛙叫过c字符串非法直接返回-1。否则将一只青蛙从状态i-1转移到状态i。最终合法性检查for(int i 0; i n - 1; i) if(hash[i] ! 0) return -1; return hash[n - 1];遍历结束后除了状态 4叫完k之外其他状态hash[0]到hash[3]必须全部为 0否则说明有青蛙“卡”在了半路叫声不完整例如cro或croakc这种缺少后续字母的情况。最后返回hash[4]即处于完成状态的青蛙数量也就是所需的最少青蛙总数。模拟算法的常见类型根据模拟对象的不同常见的模拟题可以分为以下几类1. 状态机模拟如数青蛙 这是模拟算法中最经典、也最考验逻辑的一类。特征系统中的元素会在不同状态之间转移例如青蛙从“没叫” - “叫了c” - “叫了r” ... - “叫完k”。解题套路定义状态记录每种状态的数量。代码体现用hash[0]到hash[4]记录处于不同发声阶段的青蛙数量。遍历字符串时遇到字符就进行状态转移hash[i-1]--; hash[i];。遇到c时优先复用叫完的青蛙状态4转移到状态0。2. 过程/规则模拟如外观数列 特征按照明确的规则不断迭代生成新的结果。解题套路双指针 / 遍历统计。代码体现利用left和right双指针模拟“报数”的过程统计连续相同字符的个数然后拼接成新的字符串循环往复。3. 图形/路径模拟如Z字形变换特征在二维网格或特定路径上移动或者按照特定几何规律排列字符。解题套路方法一纯模拟开一个二维数组用变量控制方向如flag 1向下flag -1向右上一步步填字符。方法二找规律优化跳过模拟过程直接推导出每一行字符下标的数学公式周期d 2*numRows-2按行直接读取。这属于“降维打击”将模拟题做成了数学找规律题。4. 时间轴/生命值模拟如提莫攻击 特征涉及时间推移、状态持续、状态刷新等。解题套路计算区间覆盖 / 累加增量。代码体现通过比较两次攻击的时间差tmp和持续时间duration来决定是累加duration还是累加tmp。这也是模拟的一种但使用了贪心的局部计算优化。识别信号以下是几种最典型的、需要使用模拟算法的场景1. 题目描述了明确的“游戏规则”或“物理过程”当题目像是在描述一个游戏、一个物理现象或一个操作流程时通常就是模拟题。特征题目会详细告诉你每一步该怎么做状态如何改变。例子提莫攻击。题目明确描述了“中毒持续 duration 秒如果期间再次攻击中毒时间重置”。你需要模拟这个过程计算总的中毒时间。判断标准如果你能在纸上按照题目描述一步一步画出状态变化图那么基本就可以用模拟算法。2. 题目涉及“状态机”或“多阶段状态转移”当某个事物需要按照固定顺序从一个状态转移到下一个状态时非常适合用模拟特别是状态计数法。特征存在固定的阶段序列必须按顺序完成。例子数青蛙。青蛙必须依次叫出c - r - o - a - k。你需要模拟每只青蛙当前处于哪个阶段。我们不需要真的去模拟每一只具体的青蛙而是通过记录“处于每个阶段的青蛙数量”来完成状态转移的模拟。判断标准题目中有“必须按顺序”、“前一个状态完成后才能进入下一个状态”等字眼。3. 题目要求“按特定规律生成/构造”结果当题目要求你按照某种迭代规则生成一系列数据或者构造一个满足特定条件的字符串/数组时。特征有明确的生成公式或构造规则需要循环迭代。例子外观数列规则是“对上一项进行报数”。你需要模拟这个“统计连续字符并拼接”的过程迭代 n-1 次。替换所有的问号规则是“替换 ? 且不能与左右相同”。你需要模拟这个“尝试替换”的过程。判断标准题目要求你“生成第 n 项”或“构造一个满足条件的字符串”。4. 题目涉及“二维网格”或“路径移动”当题目要求你在一个矩阵、网格中按照特定方向移动或者按照特定几何规律排列元素时。特征有空间位置的变化通常需要控制方向变量如上下左右。例子Z字形变换。如果你选择最直观的解法就是开一个二维数组用一个变量控制方向向下走碰到底部就向右上走一步步把字符填进去最后按行读取。这就是典型的路径模拟。判断标准题目描述了一个在二维空间中的运动轨迹或排列方式。