面经分享｜公交线路最少换乘：BFS 建模 + 五个 follow-up

这是这次 VO 第二轮的算法题，和 LeetCode 上的公交路线题同一类。题本身不高深，但建模思路、复杂度口径、边界和 follow-up 都能拉开差距。
题目
给定 source、destination 和一个 routes 列表。每个 routes[i] 是一条公交线路经过的所有站点。两条线路经过同一个站点就可以换乘。求从 source 到 destination 最少要乘几辆公交车。

• 起点 source 为 10，终点 destination 为 70
• Route 0 经过 10、20、30
• Route 1 经过 25、30、40、50
• Route 2 经过 50、60、70
• Route 3 经过 20、80

最优走法：Route 0（10→30）→ 在 30 换 Route 1（30→50）→ 在 50 换 Route 2（50→70），答案 3。
思路：把"线路"当节点
最容易想到的是把站点当图节点，但题目问的是"公交车数量"，而不是"站点数量"。所以更自然的建模是：每换乘到一条新线路，就多坐一辆车，把线路当节点，共享站点当边，然后用 BFS 按层求最短。
步骤：

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
ount) 扩展成额外记录 parent 和 transfer。找到 destination 后：

• 从最后一条线路开始；
• 沿 parent 一路向前追溯；
• 同时记录换乘站；
• 最后 reverse。
几点体会

• 先说建模，再写代码。把"线路当节点"讲清楚，面试官才能跟上你的思路。
• 复杂度要主动定义 N。这题的复杂度很容易因为口径不同而被追问。
• edge case 自己先说出来。面试官通常会觉得这是加分项。
• follow-up 基本都围绕"最少性证明"和"路径还原"，提前想好就行。

建模先讲清楚这点太真实了，bus routes 一上来就写代码的基本都栽在 follow-up。想问下最少性证明那块是当场现证的吗，面试官追得深不深？还有复杂度口径，你最后定的 N 是 routes 数量还是总站点数？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

team?