模拟算法实战：5 道经典题目解析
模拟算法的核心在于还原问题的实际运行过程。通过遍历、状态跟踪或规律推导，将抽象逻辑转化为具体代码。以下精选五道典型题目，涵盖字符串处理、区间计算及状态机模型。
039 替换所有的问号
题目描述：
给定一个字符串 s，其中包含小写字母和问号 ?。要求将所有问号替换为小写字母，使得最终字符串中不存在连续重复的字符。
解题思路
采用贪心策略。从左到右遍历字符串，遇到 ? 时，尝试用 'a' 到 'z' 中的字符进行替换。判断条件只需确保当前字符不与前一个和后一个字符相同即可。由于字母表有 26 个字符，而最多只有两个邻居需要避开，因此总能找到合适的字符（通常 'a', 'b', 'c' 中必有一个可用）。
代码实现
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;
}
};
工程师手记： 这里不需要真的遍历所有 26 个字母，实际上只要试三个字符就足够覆盖所有情况，但为了逻辑清晰，遍历全量也是 O(26*N)，复杂度可接受。关键是边界条件的判断，首尾字符没有邻居，需单独处理。
040 提莫攻击
题目描述：
提莫在时间轴上发起攻击，每次攻击使目标中毒 duration 秒。给定攻击时间序列 timeSeries 和中毒持续时间 duration，计算总中毒时间。
解题思路
这是一个典型的区间合并问题。我们关注相邻两次攻击的时间差：
- 如果时间差大于等于
duration，说明上次中毒效果已完全结束，累加完整时长。 - 如果时间差小于
duration，说明下次攻击在前次中毒结束前开始，此时只累加时间差部分，避免重复计算重叠区域。 最后别忘了加上最后一次攻击的完整duration。
代码实现
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
if (timeSeries.empty()) return 0;
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 字形排列，然后按行读取生成新字符串。
解题思路
观察 Z 字形排列的规律，可以发现数据呈现周期性变化。周期长度 T = 2 * numRows - 2。
- 第一行和最后一行：字符索引间隔固定为
T。 - 中间行：每两个字符一组，分别位于当前周期的第
k位和第T-k位。
利用这个数学规律，我们可以直接通过下标访问原字符串，无需构建二维数组，从而优化空间复杂度。
代码实现
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，返回外观数列的第 n 项。该数列由上一项的描述生成。
解题思路
这本质上是一个字符串迭代过程。对于每一项，我们需要统计连续相同字符的个数，并将'个数 + 字符'拼接成下一项。
例如：1 -> 11 (1 个 1) -> 21 (2 个 1) -> 1211 (1 个 2, 1 个 1)。
使用双指针 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，表示多只青蛙发出的叫声混合。求最少需要多少只青蛙才能发出这些叫声。
解题思路
青蛙的叫声顺序是固定的 c -> r -> o -> a -> k。我们可以维护一个哈希表（或数组），记录当前处于每个阶段的青蛙数量。
- 当遇到
'c'：如果有刚叫完'k'的青蛙，复用它；否则新增一只青蛙。 - 当遇到其他字符：必须存在对应的前驱字符状态的青蛙，将其状态后移一位。
- 遍历结束后，所有青蛙都应回到
'k'状态，否则输入非法。
代码实现
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
string t = "croak";
int n = t.size();
vector<int> hash(n, 0); // 记录各阶段青蛙数量
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];
}
};
以上五道题虽然场景不同，但核心都在于对流程的精确模拟。掌握这类题目的关键在于拆解状态变化，找到循环或递推的规律，从而写出简洁高效的代码。
