当前位置：首页 > article >正文

【LeetCode】每日一题 2024_9_17 公交路线（BFS）

article 2024/9/20 22:18:46

前言

每天和你一起刷 LeetCode 每日一题~

LeetCode 启动！

题目：公交路线

代码与解题思路

func numBusesToDestination(routes [][]int, source int, target int) int {
    // 用类似迪杰斯特拉的思路，把线路搜索一遍，然后取：最少乘坐的公交车数量
    // key 代表车站，value 代表能到该车站的公交车列表
    bus := map[int][]int{} // 先建图
    for i, v := range routes {
        for _, x := range v {
            bus[x] = append(bus[x], i)
        }
    }

    // 记录起点到每个站的最短路，key 为车站编号，value 是起点到该车站的最短路
    // 初始车站 source，自己到自己的距离为 0
    dis := map[int]int{source: 0}
    q := []int{source} // 我这里选择用 bfs 遍历
    for len(q) > 0 {
        x := q[0] // x 为当前车站
        q = q[1:]
        disX := dis[x] // 起点到 x 车站的最短路
        for _, i := range bus[x] { // 遍历所有能到 x 车站的公交车 i
            for _, y := range routes[i] { // 遍历公交车 i 经过的所有车站
                if _, ok := dis[y]; !ok { // 该车站 y 没被访问过
                    dis[y] = disX + 1 // 从 x 站上车，在 y 站下车，起点到 y 站需要的公交数量 + 1
                    q = append(q, y) // 入队，下次从 y 站开始出发
                }
            }
            routes[i] = nil // 公交车 i 已经遍历过了
        }
    }
    if v, ok := dis[target]; ok { // 如果能走到 target
        return v
    }
    return -1 // 不能走到 target 站
}