刷题打卡进入第七天今天没有继续堆基础数据结构题而是开始碰搜索类问题主要练了一道 BFS 迷宫最短路径和一道字符串压缩热身题。DHU 机试的题型这几年其实相对稳定字符串处理、模拟、图论搜索都是高频区我在前六天分别过了数组、链表、排序、二分、栈和队列到 Day7 刚好可以把手里的队列知识落到 BFS 上算是把前面攒的底子用起来。身边不少朋友也在刷华为 OD 机试题我发现那些题目和高校机试的重叠度挺高很多套路可以互相迁移。这篇就把 Day7 的完整过程写下来包括题目、代码、踩坑和排查思路给也在准备机试的人一个可直接参考的样本。1. 为什么把第7天留给BFS搜索1.1 机试高频题型分布先说明一下以下是我从历年考生经验帖和公开题库里整理的题型分布观察不代表官方考纲。单个学校机试的题目数量通常不大一般 3 到 5 道题时间从 90 分钟到 150 分钟不等。高频题型集中在以下几类字符串处理、数组与模拟、排序与查找、基础 DP、图与搜索。图与搜索的出场率不低但很多人在准备阶段容易低估。原因很简单数组和字符串的题不管会不会写至少能憋出点代码图的 BFS/DFS 一旦思路卡住整道题可能直接空着。经历过机试的人应该都有体会最可惜的不是不会做而是明明练过类似题考场上一紧张把队列初始化写错了白丢一道题的分。1.2 前六天铺垫了什么我前六天的安排是这样Day1 数组去重与双指针Day2 字符串反转与回文判断Day3 链表反转与环形链表Day4 快速排序与归并排序Day5 二分查找与边界处理Day6 栈和队列的基础应用。到 Day6 结束的时候队列的入队出队已经练熟了也理解先进先出的特性。Day7 接着把队列用到图上正好是知识链的延伸栈能推导 DFS 的递归写法队列能推导 BFS 的层级遍历写法。如果前面没有先练栈和队列直接上手 BFS 会有一点抽象这也是我把搜索安排在第七天的原因。基础顺序这件事在刷题计划里比想象中更重要。2. 热身题字符串压缩的边界陷阱2.1 题目描述与输入输出约定先来一道字符串题热身题目描述是这样的输入一行字符串只含大小写字母长度不超过 10000。对字符串进行压缩规则是把连续出现的相同字符替换成“字符 连续出现次数”。例如输入aabcccccaaa输出a2b1c5a3。如果压缩后的字符串长度不小于原字符串长度则输出原字符串。输入可能包含多行每一行代表一个测试用例要求对每行输出一个结果。这里有个容易被忽略的细节题目说的是“不小于”不是“大于”所以压缩后长度与原字符串相等时也应该输出原字符串。这个边界如果不注意样例全过提交却会挂掉。2.2 一遍遍历的解法与代码思路很简单单次循环扫描字符串维护一个计数变量。每到一个字符先和前一个字符比较相同就计数加一不同就把前一个字符和它的次数拼到结果里然后重置计数。我给出一个 Java 实现import java.util.Scanner; public class StringCompress { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextLine()) { String s sc.nextLine(); if (s.isEmpty()) { System.out.println(); continue; } StringBuilder sb new StringBuilder(); int count 1; for (int i 1; i s.length(); i) { if (i s.length() s.charAt(i) s.charAt(i - 1)) { count; } else { sb.append(s.charAt(i - 1)).append(count); count 1; } } String compressed sb.toString(); System.out.println(compressed.length() s.length() ? compressed : s); } sc.close(); } }循环里i s.length()这个写法容易引起疑惑我解释一下当i s.length()时说明扫描到字符串末尾之后这时候会执行 else 分支把最后一组连续字符拼接到结果里。这样就不用在循环外面再单独补一次拼接代码结构上更统一。如果按i s.length()写最后还需要额外处理尾部字符反而容易漏。2.3 压缩类题目的三个高发坑第一个坑是区分字符和数字。压缩结果里既要有字符又要有次数拼接时如果不用StringBuilder而用字符串直接在长度 10000 的用例下性能会非常难看虽然机试一般不卡这点但积累起来会让多组输入变慢。第二个坑是我前面提到的“不小于”边界。压缩后长度等于原长度时题目要求输出原字符串很多人用的是compressed.length() s.length()判断但这里应该严格按题目来等于时也要保留原串否则会输出一个没变短的结果逻辑上就不对。第三个坑是空行处理。多行输入时如果某一行是空字符串没做过判空处理的话代码会直接异常或者输出一个空串之后继续跑虽然不影响后续用例但在本地自测和判题系统里都可能影响最终输出格式。判题系统一般是逐行比对输出空行多一个少一个都算错误。3. 主菜最小步数迷宫的BFS标准写法3.1 题目样例与判题预期热身题做完主菜上场。题目是这样给定一个n行m列的迷宫0表示可通行1表示墙壁。起点在左上角(0, 0)终点在右下角(n-1, m-1)。每一步可以向上、下、左、右四个方向移动一格不能走出边界不能走到墙壁上。要求输出从起点到终点的最少步数如果无法到达则输出-1。第一行输入两个整数n和m接下来n行每行有m个整数数字之间用空格隔开。输入可能包含多组迷宫需要处理到文件结束。我拿一个样例测试3 3 0 0 0 0 1 0 1 0 0手动走一下从(0,0)到(0,1)再到(0,2)向下到(1,2)再向下到(2,2)一共 4 步所以输出应该是4。这个样例覆盖了绕墙走的情况如果直接用贪心或者盲目深搜不一定能最快找到最短路径。3.2 BFS为什么天然适合求最短步数DFS 也能找到一条路径但不保证最短。原因是 DFS 会沿着一条路一直走到底走到死路才回头找到的第一条路径完全取决于搜索顺序可能是绕远路。BFS 不一样它是一层一层往外扩展的每一层代表“从起点走 step 步能到达的所有位置”当第一次扩散到终点时必然是用最少步数到达的。理解这一点要抓住 BFS 的层级特性。队列里同时存在多个节点时它们代表的是同一层或者相邻层的待扩展状态。每处理完一整层步数加一。正是这种严格按层推进的方式让 BFS 第一次访问到目标节点时就能给出最短路。这个结论对应了无权图求最短路的经典方法迷宫每个格子移动一步的代价相同所以直接用 BFS。3.3 完整Java实现非递归、队列控制我给出的 Java 实现如下import java.util.*; public class MazeMinSteps { static int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNext()) { int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } System.out.println(bfs(grid, n, m)); } sc.close(); } static int bfs(int[][] grid, int n, int m) { if (grid[0][0] 1 || grid[n - 1][m - 1] 1) { return -1; } boolean[][] visited new boolean[n][m]; Queueint[] queue new LinkedList(); queue.offer(new int[]{0, 0}); visited[0][0] true; int steps 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { int[] cur queue.poll(); int r cur[0]; int c cur[1]; if (r n - 1 c m - 1) { return steps; } for (int[] d : dirs) { int nr r d[0]; int nc c d[1]; if (nr 0 nr n nc 0 nc m grid[nr][nc] 0 !visited[nr][nc]) { visited[nr][nc] true; queue.offer(new int[]{nr, nc}); } } } steps; } return -1; } }有两个点需要特别说明。一是这里用int[]存坐标简单直接机试场景够用如果追求性能可以定义内部类或者用两个队列分别存行和列但代码可读性会差一些。二是出队的时候判断是否到达终点配合入队时标记 visited是正确的标准写法。后面踩坑部分我会详细讲为什么不能在出队时才标记 visited。这里再补充一个变体如果题目要求输出路径而不只是步数就需要加一个pre数组记录每个格子的前驱格子等 BFS 结束后从终点倒推回起点。Day7 我暂时只做了求步数版本路径版本留给后面练两种题的差别其实就是多一张“前驱表”。3.4 复杂度分析与内存估算时间复杂度是 O(nm)因为每个格子最多入队一次、出队一次。空间复杂度是 O(nm)主要消耗在 visited 数组、队列以及二维迷宫数组本身。用boolean[][]的 visited 比int[][]更省内存因为 boolean 在大多数 Java 虚拟机里占 1 个字节而 int 占 4 个字节。如果迷宫规模是 1000 乘 1000visited 数组占用约 1MB队列里最多可能同时存在数百个节点内存方面完全不会有压力。真正需要担心的是另一种情况如果写成了每个位置重复入队队列大小可能膨胀到上万个甚至更多内存就不可控了。机试环境一般内存限制 256MB正常 BFS 不会爆但不规范的 visited 标记真的可能踩到内存超限。4. 机试本地模拟和在线判题的环境差异4.1 多组输入输出处理很多机试题不会只给一组输入判题系统往往在一个输入文件里塞多组测试数据。例如迷宫的输入第一组数据读完以后紧跟着可能还有第二组 n、m 和迷宫矩阵。如果只处理一组数据本地手测样例可以过提交到判题系统就只能得部分分甚至零分。处理多组数据的方式就是典型的 while 循环加 hasNext 判断。Java 的Scanner.hasNext()会阻塞等待输入如果判题系统的输入文件没有结束它会继续读取读到文件末尾时返回 false循环退出。这里有个容易忽略的小细节hasNextInt()和hasNext()的混用要谨慎如果用hasNextLine()去判断一个以整数开头的输入流可能会因为行末换行符的问题导致逻辑出错。最好先明确输入格式是“空格分隔”还是“行分隔”再决定用哪种方法。4.2 Scanner、BufferedReader与输出缓存Scanner 的优点是 API 简单适合快速写代码缺点是底层解析慢。如果是 10 万级以上的数据量Scanner 会明显拖后腿。稳妥的方案是用 BufferedReader 一次性读入再用split( )分割或者用StreamTokenizer。不过机试大多数题目数据量不会特别夸张Scanner 是足够用的我个人的建议是先用 Scanner 保证写得快如果题目明显需要处理大数据量再换 BufferedReader。输出方面最忌讳的是在循环里频繁调用System.out.println。每次输出都是一次 IO 操作成百上千次循环累积起来可能多耗时几十毫秒甚至更多。正确做法是把所有结果拼到一个 StringBuilder 里用换行符分隔最后统一输出一次。虽然很多机试题不卡这点时间但养成这个习惯不会亏而且代码也更好看。还有一个比较隐蔽的点Scanner 和 System.in 搭配时千万不要在循环里关闭 Scanner否则后续输入读不到不说有些判题环境还会报错。只需要在程序最后关闭即可或者干脆不关让 JVM 自己处理。5. 今日踩坑实录与排查技巧5.1 死循环与内存膨胀visited标记时机Day7 最典型的坑出现在 BFS 的 visited 标记时机上。我第一次写 BFS 的时候习惯在从队列里取出节点后才标记 visited写出来大概是这样的错误版本int[] cur queue.poll(); visited[cur[0]][cur[1]] true; // 处理四个方向...表面看起来没问题但仔细想一下同一个格子可能被多个邻居同时加入队列。例如格子 A 和格子 B 相邻它们都能到达格子 C如果没有在入队 C 的时候立刻标记 visited那么 A 和 B 出队扩展时都会把 C 入队一次。如果 C 周围还有其他节点这个重复入队会像滚雪球一样扩散。队列里出现大量重复元素轻则效率下降重则内存溢出。正确做法是在入队的时候立刻标记 visited。代码里我已经这样写了visited[nr][nc] true; queue.offer(new int[]{nr, nc});两层操作挨在一起保证每个格子只入队一次。这是 BFS 最基本的纪律也是很多人在考场上会犯的错我当时就在这里卡了半个多小时。5.2 起点终点本身就是墙第二个坑是边界条件的遗漏。如果grid[0][0] 1或者grid[n-1][m-1] 1起点或终点根本不可达直接返回 -1 即可。如果不加这个判断BFS 可能会在起点就返回 0或者在队列为空后返回 -1。多数时候结果碰巧是对的但有一种情况会出错如果终点是墙但起点周围存在路径能绕到终点附近BFS 会一直扩展很久最后才返回 -1浪费大量时间。所以我在 bfs 方法开头先把这两个特殊点判断掉。这种提前剪枝的思路不仅适用于迷宫题很多搜索题都可以在搜索开始前处理掉显然非法的情况减少不必要的计算。5.3 “本地对交上去错”的四个排查点刷题的人都遇到过本地运行结果正常提交到判题系统却报错的怪事。结合今天的题目我把最常见的四个排查点整理出来。第一个排查点是输入输出格式是否完全一致。比如迷宫题要求输出数字有人会顺手打印调试信息例如System.out.println(steps steps)提交时忘了删直接导致格式错误。第二个排查点是是否有多余的空格或者空行。第三个排查点是数组下标是否可能越界特别是 n1 或 m1 这种极小的迷宫我的方向数组会尝试访问邻居必须有边界判断。第四个排查点是最短路径初始化是否正确如果起始步数设成 1会把本来就该是 0 步的用例算成 1这类问题在只有起点和终点重合的用例上特别容易暴露。排查的时候不要凭感觉直接在本地造几个极端用例测一下最稳妥。比如迷宫只有 1 行 1 列、起点终点分开但完全被墙围住、全部都是平地等。这些测试数据能把大多数隐藏的问题揪出来。6. 结合Day7总结几点机试应试心得6.1 先写朴素解法再优化机试和平时刷题的最大区别是时间压力。考场上最怕的不是题目难而是想太多导致迟迟不动笔。我的策略是先写一个能过的朴素解法哪怕复杂度不是最优先保证有分。等通过了基础用例再考虑优化。以今天的迷宫题为例BFS 本身就是标准解法谈不上优化空间但有些题可以先暴力枚举再用前缀和、双指针等手段优化。先保底再进阶这是应试的基本节奏。很多同学纠结于一道题的“最优解”结果一道题磨了四十分钟后面的题全部没时间写。机试是按通过用例给分的用朴素写法拿 80 分比用优雅写法但没跑通拿 0 分要划算得多。6.2 自测用例怎么设计自测用例的设计直接决定你能发现多少 bug。光用题目样例测试是远远不够的还是要专门造边界用例。以字符串压缩为例至少得测全相同字符的字符串例如aaaaaa压缩结果是a6肯定比原串短还要测abcd压缩结果a1b1c1d1长度 8 比原串长应该输出abcd。这两个用例能把拼接逻辑和长度比较逻辑都覆盖到。如果题目数据范围给了上限就照着上限造一个大数据量用例看看会不会超时。机试常见的隐藏雷点是算法复杂度达标但常数因子太大Java 的 Scanner 加 String 拼接如果碰到 10 万长度的字符串差距会体现得很明显。自测大数据的目的不是让自己安心而是提前发现性能和内存问题。6.3 后续Day8到Day14安排Day7 结束之后我给自己排了接下来一周的计划。Day8 练 DFS重点是和 BFS 的对比以及 DFS 在回溯类题目里的应用Day9 练二叉树的前中后序遍历用递归和非递归两种方式写Day10 练二叉树的层序遍历和深度计算Day11 练简单的动态规划主要是斐波那契、爬楼梯这种入门题Day12 练经典背包问题的初始化与状态转移Day13 练字符串匹配和字符串转整数这种细节密集题Day14 做一次完整的模拟测试强迫自己在 120 分钟内独立完成 4 道题检验这一轮刷题的效果。这样安排是刻意把搜索、树、动态规划这三个硬骨头分散开避免连续几天都在啃同一类问题导致思维僵化。机试题型再多追根溯源就是基础数据结构和基础算法排列组合把每个基础点练扎实比题海战术更稳。我个人这几天的体感是刷题到了第七天其实会进入一个疲惫期前几天的新鲜感消失了难题开始变多容易产生“自己是不是不适合机试”的错觉。不用被这种感觉吓住正常现象。解法写多了以后看到“迷宫最短路径”这种描述脑子里会自动跳出 BFS 的模板这就是量变到质变的过程。我一般会在状态不好的时候刻意放慢节奏少刷一道题没关系但要把已经做过的题复盘透。如果你也在准备机试Day7 前后这个阶段不妨也给自己留一点复盘时间比盲目往下刷更重要。