815.公交路线

链接：815.公交路线
难度：Hard
标签：广度优先搜索、数组、哈希表
简介：求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

题解 1 - typescript

• 编辑时间：2021-06-28
• 执行用时：268ms
• 内存消耗：71.6MB
• 编程语言：typescript
• 解法介绍：广度优先搜索，储存站点信息和公交换站信息。

function numBusesToDestination(routes: number[][], source: number, target: number): number {
  if (source === target) return 0;
  const stationMap = new Map<number, Set<number>>();
  for (let routeIndex = 0, routeLen = routes.length; routeIndex < routeLen; routeIndex++) {
    const route = routes[routeIndex];
    for (
      let stationIndex = 0, stationLen = route.length;
      stationIndex < stationLen;
      stationIndex++
    ) {
      const station = route[stationIndex];
      let set = stationMap.get(station);
      if (!set) stationMap.set(station, (set = new Set()));
      set.add(routeIndex);
    }
  }
  const busMap = new Map<number, Set<number>>();
  for (const busList of stationMap.values()) {
    if (busList.size === 1) continue;
    for (const bus of busList) {
      let set = busMap.get(bus);
      if (!set) busMap.set(bus, (set = new Set()));
      for (const nextBus of busList) if (nextBus !== bus) set.add(nextBus);
    }
  }
  const FIRST_BUS = stationMap.get(source)!;
  const LAST_BUS = stationMap.get(target)!;
  if (!FIRST_BUS || !LAST_BUS || FIRST_BUS.size === 0 || LAST_BUS.size === 0) return -1;
  for (const bus of FIRST_BUS) if (LAST_BUS.has(bus)) return 1;
  let ans = Infinity;
  const stepMap = new Map<number, number>();
  for (const bus of FIRST_BUS) stepMap.set(bus, 1);
  const queue: number[] = [...FIRST_BUS];
  while (queue.length !== 0) {
    const bus = queue.shift()!;
    const step = stepMap.get(bus)!;
    if (LAST_BUS.has(bus)) {
      ans = Math.min(ans, step);
      continue;
    }
    const nextBusList = busMap.get(bus)!;
    for (const nextBus of nextBusList ?? []) {
      if (!stepMap.has(nextBus)) queue.push(nextBus);
      stepMap.set(nextBus, Math.min(stepMap.get(nextBus) ?? Infinity, step + 1));
    }
  }
  return ans === Infinity ? -1 : ans;
}

题解 2 - python

• 编辑时间：2024-09-17
• 执行用时：193ms
• 内存消耗：51.18MB
• 编程语言：python
• 解法介绍：利用set存储数据，bfs时对遍历过的值进行O1的删除。

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        n = len(routes)
        routeMap = {i: set(routes[i]) for i in range(n)}
        busMap = defaultdict(set)
        for i in range(n):
            for v in routes[i]:
                busMap[v].add(i)
        q = deque([source])
        size = 1
        step = 0
        while q:
            cur = q.popleft()
            if cur == target: return step
            while busMap[cur]:
                next_bus = busMap[cur].pop()
                while routeMap[next_bus]:
                    next_pos = routeMap[next_bus].pop()
                    q.append(next_pos)
            size -= 1
            if size == 0:
                size = len(q)
                step += 1
        return -1