https://leetcode.com/problems/bus-routes/
Time Complexity: O(m*n) m: # of buses, n: # of routes
Space complexity: O(m*n + m)
The first part loop on routes and record stop to routes mapping in
The second part is general bfs. Take a stop from queue and find all connected route.
The set
We can also use a set to record all routes visted , or just clear a route after visit.
https://leetcode.com/articles/bus-routes/
Solution #1 以bus route为⼀个node, 构建graph O(n * n * l) time, n为route的数量量，l为route的平均长度
We have a list of bus routes. Each
routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.
We start at bus stop
S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.Example: Input: routes = [[1, 2, 7], [3, 6, 7]] S = 1 T = 6 Output: 2 Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Note:
1 <= routes.length <= 500.1 <= routes[i].length <= 500.0 <= routes[i][j] < 10 ^ 6
Space complexity: O(m*n + m)
解法：BFS，先对原来的二维数组进行处理，二维数组的每一行代表这辆公交车能到达的站点，用HashMap记录某站点有哪个公交经过。这样处理完以后就知道每一个站点都有哪个公交车经过了。然后用一个queue记录当前站点，对于当前站点的所有经过的公交循环，每个公交又有自己的下一个站点。可以想象成一个图，每一个公交站点 被多少个公交经过,也就是意味着是个中转站,可以连通到另外一个公交上, 因为题目求的是经过公交的数量而不关心经过公交站点的数量，所以在BFS的时候以公交(也就是routes的下标)来扩展。
Solution#2, 可以用stop当作node构建graph，与上面是相同复杂度
ref: https://leetcode.com/problems/bus-routes/discuss/122712/Simple-Java-Solution-using-BFS?page=1
Node是stop，neighbour是bus routes，visited里面存的也是bus route
https://segmentfault.com/a/1190000017229110ref: https://leetcode.com/problems/bus-routes/discuss/122712/Simple-Java-Solution-using-BFS?page=1
Node是stop，neighbour是bus routes，visited里面存的也是bus route
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T) return 0;
//pre-processing: save <stop, List<buses>> for BFS
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < routes.length; i++) {
for (int stop: routes[i]) {
if (!map.containsKey(stop)) map.put(stop, new ArrayList<>());
map.get(stop).add(i);
}
}
if (!map.containsKey(S) || !map.containsKey(T)) return -1;
Set<Integer> visited = new HashSet<>(); //to store visited routes
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(S);
int transitions = 0;
while (!queue.isEmpty()) {
int size = queue.size();
transitions++;
for (int i = 0; i < size; i++) {
int curStop = queue.poll();
List<Integer> buses = map.get(curStop);
for (int bus: buses) {
if (visited.contains(bus)) continue;
visited.add(bus);
for (int stop: routes[bus]) {
if (stop == T) return transitions;
else queue.offer(stop);
}
}
}
}
return -1;
}The first part loop on routes and record stop to routes mapping in
to_route.The second part is general bfs. Take a stop from queue and find all connected route.
The set
seen record all stops visted and we won't check a stop for twice.We can also use a set to record all routes visted , or just clear a route after visit.
public int numBusesToDestination(int[][] routes, int S, int T) {
HashMap<Integer, HashSet<Integer>> to_routes = new HashMap<>();
for (int i = 0; i < routes.length; ++i)
for (int j : routes[i]) {
if (!to_routes.containsKey(j)) to_routes.put(j, new HashSet<Integer>());
to_routes.get(j).add(i);
}
Queue<Point> bfs = new ArrayDeque();
bfs.offer(new Point(S, 0));
HashSet<Integer> seen = new HashSet<>();
seen.add(S);
while (!bfs.isEmpty()) {
int stop = bfs.peek().x, bus = bfs.peek().y;
bfs.poll();
if (stop == T) return bus;
for (int route_i : to_routes.get(stop))
for (int next_stop : routes[route_i])
if (!seen.contains(next_stop)) {
seen.add(next_stop);
bfs.offer(new Point(next_stop, bus + 1));
}
}
return -1;
}
For each of the bus stop, we maintain all the buses (bus routes) that go through it. To do that, we use a HashMap, where bus stop number is the key and all the buses (bus routes) that go through it are added to an ArrayList.
We use BFS, where we process elements in a level-wise manner. We add the Start bus stop in the queue. Next, when we enter the while loop, we add all the bus stops that are reachable by all the bus routes that go via the Start. Thus, if we have the input as [[1, 2, 7], [3, 6, 7]] and Start as 6, then upon processing bus stop 6, we would add bus stops 3 and 7.
With this approach, all the bus stops at a given level, are "equal distance" from the start node, in terms of number of buses that need to be changed.
With this approach, all the bus stops at a given level, are "equal distance" from the start node, in terms of number of buses that need to be changed.
To avoid loops, we also maintain a HashSet that stores the buses that we have already visited.
Note that while in this approach, we use each stop for doing BFS, one could also consider each bus (route) also for BFS.
public int numBusesToDestination(int[][] routes, int S, int T) {
HashSet<Integer> visited = new HashSet<>();
Queue<Integer> q = new LinkedList<>();
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
int ret = 0;
if (S==T) return 0;
for(int i = 0; i < routes.length; i++){
for(int j = 0; j < routes[i].length; j++){
ArrayList<Integer> buses = map.getOrDefault(routes[i][j], new ArrayList<>());
buses.add(i);
map.put(routes[i][j], buses);
}
}
q.offer(S);
while (!q.isEmpty()) {
int len = q.size();
ret++;
for (int i = 0; i < len; i++) {
int cur = q.poll();
ArrayList<Integer> buses = map.get(cur);
for (int bus: buses) {
if (visited.contains(bus)) continue;
visited.add(bus);
for (int j = 0; j < routes[bus].length; j++) {
if (routes[bus][j] == T) return ret;
q.offer(routes[bus][j]);
}
}
}
}
return -1;
}https://leetcode.com/articles/bus-routes/
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T)
return 0;
int N = routes.length;
List<List<Integer>> graph = new ArrayList();
for (int i = 0; i < N; ++i) {
Arrays.sort(routes[i]);
graph.add(new ArrayList());
}
Set<Integer> seen = new HashSet();
Set<Integer> targets = new HashSet();
Queue<Point> queue = new ArrayDeque();
// Build the graph. Two buses are connected if
// they share at least one bus stop.
for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
if (intersect(routes[i], routes[j])) {
graph.get(i).add(j);
graph.get(j).add(i);
}
// Initialize seen, queue, targets.
// seen represents whether a node has ever been enqueued to queue.
// queue handles our breadth first search.
// targets is the set of goal states we have.
for (int i = 0; i < N; ++i) {
if (Arrays.binarySearch(routes[i], S) >= 0) {
seen.add(i);
queue.offer(new Point(i, 0));
}
if (Arrays.binarySearch(routes[i], T) >= 0)
targets.add(i);
}
while (!queue.isEmpty()) {
Point info = queue.poll();
int node = info.x, depth = info.y;
if (targets.contains(node))
return depth + 1;
for (Integer nei : graph.get(node)) {
if (!seen.contains(nei)) {
seen.add(nei);
queue.offer(new Point(nei, depth + 1));
}
}
}
return -1;
}
public boolean intersect(int[] A, int[] B) {
int i = 0, j = 0;
while (i < A.length && j < B.length) {
if (A[i] == B[j])
return true;
if (A[i] < B[j])
i++;
else
j++;
}
return false;
}
Solution #1 以bus route为⼀个node, 构建graph O(n * n * l) time, n为route的数量量，l为route的平均长度
public int numBusesToDestination(int[][] routes, int s, int t) { if (s == t) return 0; Map<Integer, Cluster> graph = new HashMap<>(); Queue<Integer> source = mergeRoutes(graph, routes, s); Set<Integer> visited = new HashSet<>(); int len = 1; while (!source.isEmpty()) { int size = source.size(); while (size > 0) { int top = source.poll(); size--; if (visited.contains(top)) continue; visited.add(top); Cluster topC = graph.get(top); if (topC.elems.contains(t)) return len; for (int c : topC.neighbours) { source.add(c); } } len++; } return -1; } private Queue<Integer> mergeRoutes(Map<Integer, Cluster> graph, int[][] routes, int s) { Queue<Integer> source = new LinkedList<>(); for (int i = 0; i < routes.length; i++) { Cluster c = new Cluster(i, routes[i]); graph.put(i, c); for (int elem : routes[i]) { if (elem == s) source.add(i); for (Map.Entry<Integer, Cluster> entry : graph.entrySet()) { if (entry.getValue().elems.contains(elem)) { entry.getValue().neighbours.add(i); c.neighbours.add(entry.getValue().index); } } } } return source; } class Cluster{ public int index; public Set<Integer> elems; public Set<Integer> neighbours; public Cluster(int index, int[] route) { this.index = index; elems = new HashSet<>(); for (int i : route) { elems.add(i); } neighbours = new HashSet<>(); } }