2021-12-04：公交路线。给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路

福大大架构师每日一题

发布于 2021-12-09 12:35:14

29800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2021-12-04：公交路线。给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。期间仅可乘坐公交车。

求出最少乘坐的公交车数量。如果不可能到达终点车站，返回 -1 。

来自力扣815。

来自三七互娱。

答案2021-12-04：

以公交线做宽度优先遍历。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    routes := [][]int{{1, 2, 7}, {3, 6, 7}}
    source := 1
    target := 6
    ret := numBusesToDestination(routes, source, target)
    fmt.Println(ret)
}

func numBusesToDestination(routes [][]int, source, target int) int {
    if source == target {
        return 0
    }
    n := len(routes)
    // key : 车站
    // value : list -> 该车站拥有哪些线路！
    map0 := make(map[int][]int)
    for i := 0; i < n; i++ {
        for j := 0; j < len(routes[i]); j++ {
            if _, ok := map0[routes[i][j]]; !ok {
                map0[routes[i][j]] = make([]int, 0)
            }
            map0[routes[i][j]] = append(map0[routes[i][j]], i)
        }
    }
    queue := make([]int, 0)
    set := make([]bool, n)
    for _, route := range map0[source] {
        queue = append(queue, route)
        set[route] = true
    }
    len0 := 1
    for len(queue) > 0 {
        nextLevel := make([]int, 0)
        for _, route := range queue {
            bus := routes[route]
            for _, station := range bus {
                if station == target {
                    return len0
                }
                for _, nextRoute := range map0[station] {
                    if !set[nextRoute] {
                        nextLevel = append(nextLevel, nextRoute)
                        set[nextRoute] = true
                    }
                }
            }
        }
        queue = nextLevel
        len0++
    }
    return -1
}