当前位置：首页 > news >正文

算法刷题｜模拟思想高频题全解（Java版）

news 2026/3/26 23:52:55

算法刷题｜模拟思想高频题全解（Java版）

在算法面试与笔试中，模拟是最直观、最容易上手的解题思想——题目怎么描述，代码就怎么实现。不需要复杂数据结构，不需要高深算法模板，只要严格还原题目流程，就能稳稳拿分。

一、什么是模拟算法？

模拟算法的核心：

严格按照题目要求，一步一步复现过程。

通用解题步骤：

读懂题意，梳理操作流程
确定遍历顺序与边界条件
逐一遍历，按规则处理元素
处理特殊情况（首尾、空值、越界）

适用场景：字符串处理、游戏场景、时间计算、数列生成、流程类题目。

二、经典模拟题（Java 实现）

1. 替换所有的问号（1576. Easy）

题目：将字符串中的?替换成小写字母，使结果没有连续重复字符。

思路：

遍历字符串，遇到?就从a-z尝试替换，只要不和左右字符相同即可。

class Solution { public String modifyString(String ss) { char[] s = ss.toCharArray(); int n = s.length; for (int i = 0; i < n; i++) { if (s[i] == '?') { // 从a到z试 for (char ch = 'a'; ch <= 'z'; ch++) { boolean leftOk = (i == 0) || (ch != s[i - 1]); boolean rightOk = (i == n - 1) || (ch != s[i + 1]); if (leftOk && rightOk) { s[i] = ch; break; } } } } return String.valueOf(s); } }

2. 提莫攻击（495. Easy）

题目：提莫攻击中毒 duration 秒，重复攻击会重置时间，求总中毒秒数。

思路：

相邻攻击时间差 ≥ duration：加完整时间
否则加时间差
最后一次攻击一定能持续完整 duration

class Solution { public int findPoisonedDuration(int[] timeSeries, int duration) { int res = 0; for (int i = 1; i < timeSeries.length; i++) { int diff = timeSeries[i] - timeSeries[i - 1]; res += Math.min(diff, duration); } // 最后一击 return res + duration; } }

3. N 字形变换（6. Medium）

题目：把字符串按指定行数排成 N 字形，再按行读取。

思路：

找周期规律：

周期长度 =2 * numRows - 2

第一行、最后一行：按周期取
中间行：每个周期取两个对称位置

class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s; int n = s.length(); int cycle = 2 * numRows - 2; StringBuilder sb = new StringBuilder(); // 第一行 for (int i = 0; i < n; i += cycle) { sb.append(s.charAt(i)); } // 中间行 for (int k = 1; k < numRows - 1; k++) { for (int i = k, j = cycle - k; i < n || j < n; i += cycle, j += cycle) { if (i < n) sb.append(s.charAt(i)); if (j < n) sb.append(s.charAt(j)); } } // 最后一行 for (int i = numRows - 1; i < n; i += cycle) { sb.append(s.charAt(i)); } return sb.toString(); } }

4. 外观数列（38. Medium）

题目：

1 → 11 → 21 → 1211 → 111221

每一项是对前一项的描述。

思路：

双指针统计连续相同字符：个数 + 字符。

class Solution { public String countAndSay(int n) { String res = "1"; // 迭代n-1次 for (int i = 1; i < n; i++) { StringBuilder tmp = new StringBuilder(); int len = res.length(); int left = 0; while (left < len) { int right = left; while (right < len && res.charAt(left) == res.charAt(right)) { right++; } tmp.append(right - left).append(res.charAt(left)); left = right; } res = tmp.toString(); } return res; } }

5. 数青蛙（1419. Medium）

题目：

字符串由croak混合组成，求最少需要多少只青蛙，无效返回 -1。

思路：

青蛙必须按顺序：c → r → o → a → k
遇到c：有叫完的青蛙就复用，没有就新增
遇到其他字符：必须有前驱，否则无效
最后非k阶段有剩余，说明不合法

class Solution { public int minNumberOfFrogs(String croakOfFrogs) { String croak = "croak"; int n = croak.length(); int[] cnt = new int[n]; // 建立字符到下标的映射 int[] index = new int[128]; for (int i = 0; i < n; i++) { index[croak.charAt(i)] = i; } for (char ch : croakOfFrogs.toCharArray()) { int i = index[ch]; if (i == 0) { // c if (cnt[4] > 0) cnt[4]--; cnt[0]++; } else { if (cnt[i - 1] == 0) return -1; cnt[i - 1]--; cnt[i]++; } } // 前面不能有剩余 for (int i = 0; i < 4; i++) { if (cnt[i] != 0) return -1; } return cnt[4]; } }