给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7]
表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6 输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 输出：-1
提示：1 <= routes.length <= 500.
1 <= routes[i].length <= 105
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
解题思路分析1、广度优先搜索；时间复杂度O(n^3)，空间复杂度O(n)
func numBusesToDestination(routes [][]int, source int, target int) int {
if source == target {
return 0
}
n := len(routes)
m := make(map[int][]int) // 该公交车经过第几条线路的数组
for i := 0; i < n; i {
for j := 0; j < len(routes[i]); j {
node := routes[i][j]
m[node] = append(m[node], i)
}
}
count := 1
queue := make([]int, 0)
queue = append(queue, source)
visited := make(map[int]bool) // 第几条线路访问情况
for len(queue) > 0 {
length := len(queue)
for i := 0; i < length; i {
node := queue[i]
for j := 0; j < len(m[node]); j {
if visited[m[node][j]] == false {
visited[m[node][j]] = true
for k := 0; k < len(routes[m[node][j]]); k {
if routes[m[node][j]][k] == target {
return count
}
queue = append(queue, routes[m[node][j]][k])
}
}
}
}
count
queue = queue[length:]
}
return -1
}
2、广度优先搜索；时间复杂度O(n^2)，空间复杂度O(n^2)
func numBusesToDestination(routes [][]int, source int, target int) int {
if source == target {
return 0
}
n := len(routes)
m := make(map[int][]int) // 该公交车经过第几条线路的数组
dis := make([]int, n) // source到第i条线路的距离
arr := make([][]bool, n)
for i := 0; i < n; i {
arr[i] = make([]bool, n)
dis[i] = -1
}
for i := 0; i < n; i {
for j := 0; j < len(routes[i]); j {
node := routes[i][j]
m[node] = append(m[node], i)
for _, v := range m[node] {
arr[i][v] = true
arr[v][i] = true
}
}
}
queue := make([]int, 0)
for _, v := range m[source] {
dis[v] = 1
queue = append(queue, v)
}
for len(queue) > 0 { // 广度优先计算source所在公交站台，到其它站台的最小距离
node := queue[0]
queue = queue[1:]
for i := 0; i < n; i {
if arr[node][i] == true && dis[i] == -1 { // node可以到i，且i未访问过
dis[i] = dis[node] 1
queue = append(queue, i)
}
}
}
res := math.MaxInt32 // 最短路径
for i := 0; i < len(m[target]); i { // 遍历多终点，找最小
v := m[target][i]
if dis[v] != -1 && dis[v] < res {
res = dis[v]
}
}
if res < math.MaxInt32 {
return res
}
return -1
}总结
Hard题目，使用广度优先搜索解法，2种解法思路有些不同
