面试题库 › 算法 / 大模型 › 01 矩阵最短距离并输出路径(LeetCode 542)

01 矩阵最短距离并输出路径(LeetCode 542)

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:图论

哪些公司问过

猿辅导1

常见岗位:机器学习算法(泛)

答案要点

  1. 多源 BFS:所有 0 同时入队作为起点,距离初始化为 0,其余为 -1
  2. 逐层扩展,格子首次被访问时的距离即最短距离
  3. 输出路径:扩展时记录前驱格子
  4. 从目标格子沿前驱回溯到某个 0,得到一条最短路径
  5. 时间、空间均为 O(mn);存在多个最近 0 时输出其中一条

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题