页面加载中…
34 道经典题打通 ACM 机试六大考点，难度封顶中等，不踩断崖
考研复试机试多为 ACM 模式——需自行处理输入输出，不像 LeetCode 只填函数体。题型集中在模拟/枚举/排序/基础数据结构/简单图与 DP，难度鲜有困难题。本路径用 LeetCode 经典题按「机试考点」逐层覆盖：从数组模拟、字符串处理、手写排序与二分，到栈/链表/队列基础，再到树与图的 BFS/DFS，最后收口于高频 DP 套路。全路径 34 题，难度严格控制在简单→中等，帮你在复试前把机试必考模块逐一过关。
适合：408/复试机试、需要练输入输出与模拟的考研党
机试最常考「按题意逐步模拟」，本质是遍历 + 条件判断。快慢指针处理原地删改、双向扫描矩阵边界，是模拟题的两个高频骨架；掌握之后几乎任意「对数组做某操作」的题都能落地。
快慢指针原地覆盖：慢指针记写入位，快指针扫全表，遇到目标值跳过，其余覆盖——原地删除类模拟题的最小模板。
与上题同用快慢指针，但零不是目标值而是「要留在末尾的元素」；先把非零全部前移，再从慢指针位补零，对比上题理解「写入位」的通用性。
快慢指针是线性覆盖，本题改用「原地标记」：把 nums[nums[i]-1] 取反标脏，一遍扫描找出仍正数的下标即为缺失值，O(n) 时间 O(1) 额外空间。
原地标记利用值域，轮转数组无额外信息可借；经典做法是「全体反转 → 前 k 反转 → 后 n-k 反转」三次翻转，对比原地标记理解两种原地操作思路。
轮转是线性操作，螺旋矩阵是二维模拟：维护四条边界，每圈按右→下→左→上收缩——考研「按规律填表」的通用框架。
螺旋矩阵考边界模拟，最大子数组考局部最优积累：当前前缀和为负则重置，局部最大实时更新全局最大，Kadane 算法是考研 DP 模拟题最常见简化形式。
机试字符串题主要考「字符统计 + 遍历判断」，核心手法是哈希计数和双指针对比。掌握「从两端向中间夹」与「频次数组统计」后，回文判断、异位词检验、公共前缀、数字解析四类高频字符串题全部能套模板。
字符串双指针入门：左右指针跳过非字母数字后对比，核心是「两端向中间夹」，忽略大小写与非字母——几乎所有回文类题的判断骨架。
回文是同一字符串两端对比，公共前缀是多个字符串纵向对比：以第一个字符串为基准，逐列扫描每一行是否匹配，列失配即截断返回。
公共前缀按列纵向扫，异位词检验按频次横向统计：26 位频次数组加减抵消后全零即等价——字符统计类题的最小数据结构。
异位词只需统计频次是否相等，第一个唯一字符还要记位置：同样用 26 位频次数组，第二遍扫找首个频次为 1 的字符，两遍扫描写法是考研常见模式。
前几题是字符比较，本题是数字模拟：逐位取余拼接反转，难点是溢出判断需在最终拼接前而非后检测——整数处理题的溢出哨兵写法。
整数反转靠取余提位，atoi 靠字符扫描提位（ch-'0'）；两题都需溢出检测，区别是 atoi 还要跳空白、处理符号位，状态机思路是复杂字符串解析的通用框架。
考研机试常要求「手写排序」，ACM 模式下插入/快速排序是高频实现点。同样重要的是「二分查找三种边界写法」：查精确值/查左边界/查右边界在不同场景下结论不同，本里程碑把四种排序和三种二分一并打通。
插入排序入门：内层指针向左移位直到找到插入点，理解「已排序区间不断右扩」的循环不变量——手写排序的认知基础。
插入排序是 O(n²) 移位，快排用 partition 一分为二：pivot 左小右大，递归子区间——理解 pivot 选取对最坏情况的影响。
快排是原地分区，归并需要额外空间；本题从尾到头合并两个已排序数组——从后向前的双指针避免覆盖，是归并逻辑的最小实现。
归并是线性扫，二分是折半跳：左闭右闭区间写法中 while(lo<=hi) + mid=(lo+hi)/2 是基础模板，正确理解循环不变量比死记边界更重要。
标准二分找精确值，插入位置找「第一个 ≥ target 的下标」：right 收到 mid-1 后 lo 即答案——左边界写法与精确查找写法的关键区别。
插入位置只要左边界，本题同时要左右边界：跑两次二分，一次找第一个 >= target，一次找第一个 > target 后减一；双边界是考研排列组合题的常用工具。
栈与链表是 ACM 机试必考数据结构，考法集中在括号匹配、表达式求值、链表遍历与指针重连。本里程碑从「结构模拟」切入：用栈模拟队列、用快慢指针检测环、反转链表调整 next 指针，打牢链式结构基本功。
栈的经典应用：左括号入栈，右括号取栈顶比对；遍历结束栈为空则合法。这是「后进先出」语义最直白的体现，所有括号/嵌套匹配题的原型。
括号匹配只用一个栈，本题用两个栈模拟队列：输入栈接收 push，输出栈为空时一次性倒入——「延迟搬运」策略让均摊复杂度达到 O(1)。
用栈模拟队列是结构转换，逆波兰表达式是经典栈应用：遇数字入栈，遇运算符弹出两个数计算后回压——掌握此题可直接手写简单表达式求值。
链表反转靠原地调整 next：三指针 prev/curr/next 向右推进，每步把 curr.next 改指 prev——所有链表改指针题的基础手法。
反转是单链遍历，合并要同时移动两个指针：哑节点 dummy 统一头节点处理，比较当前值后接较小的节点——双链合并在归并排序链表版中直接复用。
合并用双指针同向移动，环检测改为快慢指针：快指针每次走两步，有环则终会追上慢指针；Floyd 判环是机试图论之前必掌握的链表压轴题。
二叉树递归框架与图的 BFS/DFS 共享同一套「访问 + 扩展」逻辑，只是树有父子方向约束、图需要 visited 集合防重访。本里程碑先在树上练递归三问，再迁移到图的多源 BFS 与 DFS 连通性计数，两类题型一起融会贯通。
递归三问入门：返回深度、参数是当前节点、单层取左右最大值加一——return max(left,right)+1 是所有树形属性题的原型。
最大深度比同侧，对称比镜像：把单节点递归改成双节点同步递归，参数从一个节点变成「左外 vs 右外、左内 vs 右内」两对，理解递归参数如何编码比较语义。
对称用 DFS，层序换 BFS：while 外层控层数、for 内层取当层 size——此双层循环是所有层序变体的通用模板。
层序横向扩展，路径和回到 DFS 向下传余量：每层减去节点值，到叶子余量为零即成——前序「携带状态下行」对比后序「回传结果上行」。
树天然防环，图要 visited 防重访；每找到未访问的 '1' 计数加一，DFS 把整块岛屿标记——连通分量计数的模板题。
岛屿是单源 DFS 标记，本题改多源 BFS：所有烂橘子同时入队按轮次扩散，统计最少分钟数——多源 BFS 是机试图论的高频考点。
考研机试 DP 集中在「一维递推 + 二维路径 + 背包」三类，绝少出难题。本里程碑用五题逐步建立 DP 思维：先从最简单的状态转移出发，进阶到背包和 LCS，覆盖机试 80% DP 出题范围。
DP 最小原型：dp[i] = dp[i-1]+dp[i-2]，滚动变量压到 O(1)——「状态只依赖有限前驱」后，所有线性 DP 都是此框架的变体。
爬楼梯无限制，打家劫舍加「不相邻约束」：dp[i]=max(dp[i-1], dp[i-2]+nums[i])——对比上题理解约束如何修改转移方程。
一维线性 DP 推广到二维：dp[i][j]=dp[i-1][j]+dp[i][j-1]，只能右/下故无后效性——二维边界初始化是机试高频易错点。
不同路径计方案数，本题求最小值：dp[i][j]=min(上,左)+grid[i][j]——同一框架「计数」换「最值」的对比。
路径 DP 按坐标推进，LIS 按序列状态：dp[i] 表示以 nums[i] 结尾的最长递增子序列，O(n²) 双重循环是机试的可接受复杂度。