Java 模拟算法实战
模拟算法的核心在于严格按照题目描述进行步骤操作。这类问题通常逻辑直观，但容易在边界条件和细节处理上出错。下面通过五道经典题目，梳理一下模拟算法的常见套路和注意事项。
替换所有的问号
题目核心
将字符串中的 ? 替换为小写字母，要求替换后的字符不能与相邻字符重复。
思路解析
遍历字符串，遇到 ? 时尝试从 a 到 z 寻找一个不与左右邻居冲突的字符。这里有两个关键点：一是边界情况（首尾字符），二是确保找到的字符唯一且合法。
class Solution {
public String modifyString(String s) {
int n = s.length();
char[] chars = s.toCharArray();
for (int i = 0; i < n; i++) {
if (chars[i] == '?') {
// 尝试 a-z 找到合适的字符
for (char ch = 'a'; ch <= 'z'; ch++) {
// 检查左邻居和右邻居
boolean leftOk = (i == 0 || chars[i - 1] != ch);
boolean rightOk = (i == n - 1 || chars[i + 1] != ch);
if (leftOk && rightOk) {
chars[i] = ch;
break;
}
}
}
}
return new String(chars);
}
}
- 时间复杂度：O(n)，每个位置最多尝试 26 次。
- 空间复杂度：O(n)，用于存储字符数组。
提莫攻击
题目核心 计算中毒总时长。技能有持续时间，如果新技能在旧技能结束前释放，则重叠部分只算一次。
思路解析 关键在于判断两次攻击的时间间隔。如果间隔大于等于持续时间，说明上次攻击完全生效；否则，上次攻击被中断，实际贡献时间为间隔差值。最后别忘了加上最后一次攻击的完整持续时间。
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
if (timeSeries.length == 0) return 0;
int totalDuration = 0;
for (int i = 1; i < timeSeries.length; i++) {
int diff = timeSeries[i] - timeSeries[i - 1];
// 取间隔和持续时间的较小值
totalDuration += Math.min(diff, duration);
}
// 加上最后一次攻击的完整持续时间
return totalDuration + duration;
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
Z 字形变换
题目核心 将字符串按 Z 字形排列后，按行读取生成新字符串。
思路解析
直接模拟二维矩阵会消耗过多空间。观察规律发现，字符是按周期循环的。周期长度为 2 * numRows - 2。第一行和最后一行每隔一个周期出现一次，中间行每个周期会出现两次（一次向下，一次向上）。
注意当行数小于 2 时，直接返回原字符串即可。
class Solution {
public String convert(String s, int numRows) {
if (numRows < 2) return s;
int n = s.length();
int cycleLen = 2 * numRows - 2;
StringBuilder sb = new StringBuilder();
// 第一行
for (int i = 0; i < n; i += cycleLen) {
sb.append(s.charAt(i));
}
// 中间行
for (int k = 1; k < numRows - 1; k++) {
for (int i = k, j = cycleLen - k; i < n || j < n; i += cycleLen, j += cycleLen) {
if (i < n) sb.append(s.charAt(i));
if (j < n) sb.append(s.charAt(j));
}
}
// 最后一行
for (int i = numRows - 1; i < n; i += cycleLen) {
sb.append(s.charAt(i));
}
return sb.toString();
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
外观数列
题目核心 第 n 行是对第 n-1 行的描述（读法）。例如 "1" -> "11" -> "21"。
思路解析 这是一个典型的迭代过程。使用双指针扫描当前字符串，统计连续相同字符的个数，然后拼接'个数 + 字符'得到下一行。直到达到第 n 行。
class Solution {
public String countAndSay(int n) {
String current = "1";
for (int i = 1; i < n; i++) {
StringBuilder next = new StringBuilder();
int len = current.length();
int left = 0, right = 0;
while (right < len) {
// 移动右指针直到字符不同
while (right < len && current.charAt(left) == current.charAt(right)) {
right++;
}
// 记录个数和字符
next.append(right - left).append(current.charAt(left));
left = right;
}
current = next.toString();
}
return current;
}
}
数青蛙
题目核心 给定一串 "croak" 混合字符串，求最少需要多少只青蛙才能完成这些叫声。如果字符串不合法（如缺少前驱字符或结尾不完整），返回 -1。
思路解析 这可以看作是一个状态机问题。每只青蛙的状态由它当前叫出的字母决定。我们需要维护五种状态的数量。遍历字符串时，根据当前字符更新状态计数。关键点是：
- 遇到 'c' 时，优先复用已经叫完 'k' 的青蛙（减少总数），如果没有则增加新青蛙。
- 遇到其他字符时，必须保证前驱状态存在，否则非法。
- 遍历结束后，所有非 'k' 状态的计数必须为 0。
这里提供两种实现方式，一种是显式变量控制，另一种是用数组模拟哈希表，后者更通用。
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
if (croakOfFrogs.length() % 5 != 0) return -1;
// 使用数组模拟状态计数，对应 c, r, o, a, k
int[] count = new int[5];
int frogs = 0;
int maxFrogs = 0;
for (char ch : croakOfFrogs.toCharArray()) {
int index = getCharIndex(ch);
if (index == 0) {
// 开始叫，青蛙数量 +1
count[0]++;
frogs++;
maxFrogs = Math.max(maxFrogs, frogs);
} else {
// 检查前驱是否存在
if (count[index - 1] == 0) return -1;
count[index - 1]--;
count[index]++;
if (index == 4) {
// 叫完，青蛙数量 -1
frogs--;
}
}
}
// 检查是否所有青蛙都叫完了
return frogs == 0 ? maxFrogs : -1;
}
private int getCharIndex(char ch) {
switch (ch) {
case 'c': return 0;
case 'r': return 1;
case 'o': return 2;
case 'a': return 3;
case 'k': return 4;
default: return -1;
}
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)（固定大小的数组）