模拟算法精选：五道经典题目深度解析
039 替换所有的问号
题目描述：
给定一个字符串 s，将其中的所有问号 ? 替换为小写英文字母。要求替换后不能出现连续重复的字符。
解题思路
采用纯模拟策略。遍历字符串，遇到问号时，尝试用 a~z 中的字符进行填充。关键在于检查该位置的前后字符，确保新填入的字符不与相邻字符重复。由于只有三个字符（前、后、自身）需要避让，而字母表有 26 个，必然存在至少一个合法字符。
代码实现
class Solution {
public:
string modifyString(string s) {
for (int i = 0; i < s.size(); i++) {
if (s[i] == '?') {
// 尝试 a-z 替换
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;
}
};
提示： 实际编码时注意边界条件，特别是首尾字符的判断，避免数组越界。
040 提莫攻击
题目描述：
在《英雄联盟》中，提莫的攻击会让目标中毒。给定攻击时间序列 timeSeries 和中毒持续时间 duration，计算总中毒时间。
解题思路
核心在于处理重叠区间。比较相邻两次攻击的时间差：
- 若时间差大于等于
duration，说明上次中毒已完全结束，累加完整时长。 - 若时间差小于
duration，说明中毒被刷新，只累加时间差部分。 最后别忘了加上最后一次攻击的完整持续时间。
代码实现
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int ret = 0;
int n = timeSeries.size();
for (int i = 1; i < n; i++) {
int x = timeSeries[i] - timeSeries[i - 1];
if (x >= duration) {
ret += duration;
} else {
ret += x;
}
}
// 最后一次攻击必定贡献完整的 duration
return ret + duration;
}
};
041 Z 字形变换
题目描述：
将字符串按指定行数 numRows 呈 Z 字形排列，然后按行读取生成新字符串。
解题思路
观察规律可知，字符排列具有周期性，周期长度 T = 2 * numRows - 2。
- 首行与末行：字符间距固定为
T。 - 中间行：每两个字符一组，分别位于当前周期的正向和反向路径上，间距交替变化。
通过数学公式直接定位每一行的字符索引，无需构建二维矩阵，空间复杂度更优。
代码实现
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ret;
int d = 2 * numRows - 2;
int n = s.size();
// 1. 处理第一行
for (int i = 0; i < n; i += d) ret += s[i];
// 2. 处理中间行
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];
}
}
// 3. 处理最后一行
for (int i = numRows - 1; i < n; i += d) ret += s[i];
return ret;
}
};
042 外观数列
题目描述：
返回外观数列的第 n 项。每一项是对前一项的描述，例如 "1" -> "11" -> "21"。
解题思路
本质是迭代统计连续相同字符的个数。使用双指针 left 和 right 扫描当前字符串，当字符不同时，记录个数并拼接字符，作为下一轮输入。
代码实现
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 left = 0, right = 0; right < len;) {
while (right < len && ret[left] == ret[right]) right++;
tmp += to_string(right - left) + ret[left];
left = right;
}
ret = tmp;
}
return ret;
}
};
043 数青蛙
题目描述：
给定字符串 croakOfFrogs，由多个 "croak" 混合而成，求最少需要多少只青蛙才能发出这些叫声。
解题思路
模拟青蛙叫声的状态流转。每个青蛙处于 c -> r -> o -> a -> k 的不同阶段。
- 遇到
c：若有刚叫完k的青蛙可用则复用，否则新增一只。 - 遇到其他字符：检查前驱状态是否存在，不存在则非法。
- 最终检查所有青蛙是否都完成了叫声（即没有卡在中间状态的青蛙）。
代码实现
class Solution {
public:
int minNumberOfFrogs(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];
}
};
总结： 这五道题均围绕模拟过程展开，关键在于准确理解题意中的状态变化规则，并妥善处理边界情况。
