企业官网建设流程全解析

刷题打卡进入第七天，今天没有继续堆基础数据结构题，而是开始碰搜索类问题，主要练了一道 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]; Queue<int[]> 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 乘 1000，visited 数组占用约 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)，提交时忘了删，直接导致格式错误。第二个排查点是是否有多余的空格或者空行。第三个排查点是数组下标是否可能越界，特别是 n=1 或 m=1 这种极小的迷宫，我的方向数组会尝试访问邻居，必须有边界判断。第四个排查点是最短路径初始化是否正确，如果起始步数设成 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 前后这个阶段，不妨也给自己留一点复盘时间，比盲目往下刷更重要。