LeetCode 815. 公交路线

Categories:

题目描述
思路分析
1. 解法一：按线路 BFS（推荐）
相似题目

题目描述

✅ 815. 公交路线

思路分析

解法一：按线路 BFS（推荐）

核心思路：

把每条公交线路视为节点，若两条线路有公共站点则可换乘。

从包含 source 的线路出发，BFS 到包含 target 的线路。

用 stop -> routes 反向索引加速查找相邻线路。

复杂度分析：

时间复杂度：O(E)，其中 E 为线路与站点关系数量。

空间复杂度：O(E)。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }

        Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                stopToRoutes.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
            }
        }

        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] visitedRoute = new boolean[routes.length];
        Set<Integer> visitedStop = new HashSet<>();

        for (int route : stopToRoutes.getOrDefault(source, List.of())) {
            queue.offer(route);
            visitedRoute[route] = true;
        }

        int buses = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int route = queue.poll();
                for (int stop : routes[route]) {
                    if (stop == target) {
                        return buses;
                    }

                    if (!visitedStop.add(stop)) {
                        continue;
                    }

                    for (int next : stopToRoutes.getOrDefault(stop, List.of())) {
                        if (!visitedRoute[next]) {
                            visitedRoute[next] = true;
                            queue.offer(next);
                        }
                    }
                }
            }
            buses++;
        }

        return -1;
    }
}

func numBusesToDestination(routes [][]int, source int, target int) int {
	if source == target {
		return 0
	}

	stopToRoutes := make(map[int][]int)
	for i := 0; i < len(routes); i++ {
		for _, stop := range routes[i] {
			stopToRoutes[stop] = append(stopToRoutes[stop], i)
		}
	}

	queue := make([]int, 0)
	visitedRoute := make([]bool, len(routes))
	visitedStop := make(map[int]bool)

	for _, route := range stopToRoutes[source] {
		queue = append(queue, route)
		visitedRoute[route] = true
	}

	buses := 1
	head := 0
	for head < len(queue) {
		size := len(queue) - head
		for i := 0; i < size; i++ {
			route := queue[head]
			head++
			for _, stop := range routes[route] {
				if stop == target {
					return buses
				}

				if visitedStop[stop] {
					continue
				}
				visitedStop[stop] = true

				for _, next := range stopToRoutes[stop] {
					if !visitedRoute[next] {
						visitedRoute[next] = true
						queue = append(queue, next)
					}
				}
			}
		}
		buses++
	}

	return -1
}

相似题目

题目	难度	考察点
127. 单词接龙	困难	BFS
752. 打开转盘锁	中等	BFS
433. 最小基因变化	中等	BFS
847. 访问所有节点的最短路径	困难	状态 BFS
994. 腐烂的橘子	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/96122260