2021-12-04：公交路线。给你一个数组 routes ，表示一系列公交线路，其中每个 routesi 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes0 = 1, 5, 7 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
来自力扣815。
来自三七互娱。
答案2021-12-04：
以公交线做宽度优先遍历。
代码用golang编写。代码如下：
代码语言：txt复制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
}执行结果如下：
图片左神java代码
