2021-12-04：公交路線。給你一個(gè)數(shù)組 routes ，表示一系列公交線路，其中每個(gè) routes[i] 表示一條公交線路，第 i 輛公交車(chē)將會(huì)在上面循環(huán)行駛。
例如，路線 routes[0] = [1, 5, 7] 表示第 0 輛公交車(chē)會(huì)一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 這樣得車(chē)站路線行駛。
現(xiàn)在從 source 車(chē)站出發(fā)（初始時(shí)不在公交車(chē)上），要前往 target 車(chē)站。 期間僅可乘坐公交車(chē)。
求出 蕞少乘坐得公交車(chē)數(shù)量 。如果不可能到達(dá)終點(diǎn)車(chē)站，返回 -1 。
來(lái)自力扣815。
來(lái)自三七互娛。
答案2021-12-04：
以公交線做寬度優(yōu)先遍歷。
代碼用golang編寫(xiě)。代碼如下：
package mainimport "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 : 車(chē)站 // value : list -> 該車(chē)站擁有哪些線路！ 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}
執(zhí)行結(jié)果如下：
***
[左神java代碼](gitee/moonfdd/coding-for-great-offer/blob/main/src/class36/Code12_BusRoutes.java)
