leetcode815_go_公交路线

题目

给你一个数组 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
}