某程序员：面试被挂的原因竟然是，搜了女仆。。
老鬼约 4 分钟最近刷到一则超级有趣的面试经历，真是让我忍不住笑出声。
故事的主角是一位技术能力和沟通能力都没问题的候选人，他准备面试本来一切顺利。结果呢，面试官在共享屏幕时，发现了一个令人有点“惊讶”的场景——候选人的浏览记录里居然搜了“女仆xxx”！😂
这下，技术再好、沟通再顺畅，面试官都不禁皱了皱眉头。你说这也太尴尬了吧！技术面试本来是为了展示你的专业能力，结果却因为浏览记录的小插曲被挂掉，真是让人哭笑不得。
很多网友调侃：“面试官是不是在做后台监控？连浏览历史都能翻出来。”不过，话说回来，虽然面试官这么做有点“过分”，但也提醒了我们，在面试这种关键时刻，任何小细节都可能决定成败。面试前，记得把浏览器历史清理干净，避免再有“惊喜”出现。【备注:文末可领最新资料】。
算法题：公交路线
今天咱们聊点儿技术，话题是：公交路线
问题是这样的：给定一个城市的公交路线图，每条线路上的站点是一个节点，线路之间的转车站点是图中的边，问题的目标是：给定两个站点，求从一个站点到另一个站点的最短路径，可能需要转车。乍一看，这是一个典型的最短路径问题，还是带有转车限制的。
首先，我们来考虑下如何用图来建模这个问题。公交路线图不外乎就是多个线路的集合，每个线路包含一组站点，而不同的线路之间会在某些站点交汇。这里最简单的做法是将每个公交站点当作图中的一个节点，每条公交线路的每个站点之间存在边，代表它们是直接相连的。
这个问题的核心其实就是图的广度优先搜索（BFS）。因为我们要求的是最短路径，而BFS天然适合无权图的最短路径搜索。我们用队列来存储每一步的状态，逐层向外扩展，直到找到目标站点为止。
代码实现的步骤大致是这样的：
import java.util.*;public class BusRoute {
public int numBusesToDestination(int[][] routes, int source, int target) {
if (source == target) return 0;
// map to store the stations and which routes they are in
Map<Integer, List<Integer>> stationToRoutes = new HashMap<>();
for (int i = 0; i < routes.length; i++) {
for (int station : routes[i]) {
stationToRoutes.putIfAbsent(station, new ArrayList<>());
stationToRoutes.get(station).add(i);
}
}
// queue for BFS, each element is [station, busCount]
Queue<int[]> queue = new LinkedList<>();
boolean[] visitedStations = new boolean[1000001]; // to mark visited stations
boolean[] visitedRoutes = new boolean[routes.length]; // to mark visited routes
queue.offer(new int[]{source, 0}); // start from the source station
visitedStations[source] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int station = current[0];
int busCount = current[1];
// Visit all the routes that the current station is part of
for (int routeIndex : stationToRoutes.get(station)) {
if (visitedRoutes[routeIndex]) continue; // Skip visited routes
visitedRoutes[routeIndex] = true;
// Add all stations in the current bus route to the queue
for (int nextStation : routes[routeIndex]) {
if (nextStation == target) return busCount + 1; // Found the target station
if (!visitedStations[nextStation]) {
visitedStations[nextStation] = true;
queue.offer(new int[]{nextStation, busCount + 1});
}
}
}
}
return -1; // If we can't find a path
}
public static void main(String[] args) {
BusRoute br = new BusRoute();
int[][] routes = {
{1, 2, 7},
{3, 6, 7},
{3, 8, 9},
{4, 5, 9}
};
System.out.println(br.numBusesToDestination(routes, 1, 9)); // Expected output: 3
}
}
在这段代码中，我做了以下几个要点的设计：
站点和线路的映射关系：首先，得有一个映射，记录每个站点都有哪些线路。这样，我们就能快速地知道一个站点是否在某条线路上。
BFS 搜索：我们用队列来执行广度优先搜索，每一步我们检查从当前站点出发，能否通过某条公交线路直接到达另一个站点。每次找到新的站点时，我们会把它加入队列，并标记为已经访问过。
转车的处理：一个关键点是我们不仅需要知道站点，还得知道每条线路已经走过了。因为每次换线路都相当于“转车”，我们不能重复乘坐同一条线路，所以需要一个
visitedRoutes数组来标记每条线路是否已经用过。返回最短路径：每次找到目标站点，我们就返回当前的转车次数（即公交车数量）。如果没找到目标，说明无法到达，返回-1。
总结一下，这个公交路线的算法问题通过BFS非常自然地映射了一个多路径的最短路径问题。通过合理的图建模和队列操作，我们能够高效地找到最短的换乘次数，解决了实际生活中很多人烦恼的“公交换乘”问题。是不是觉得挺有意思的？公交车问题都能拿来做算法题，人生都能找到路径，咱们程序员还怕啥算法题呢？
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。