Leetcode -815- Bus route

This is the sixth day of my participation in Gwen Challenge

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

You are given an array routes representing a series of bus routes, where each routes[I] represents a bus route on which the i-th bus will cycle. For example, routes[0] = [1, 5, 7] means that the 0 bus will always follow the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 ->... Such station routes are driven. Now from source station (not on the bus at the beginning), you're going to Target Station. Bus only. Find the minimum number of buses. If it is impossible to reach the terminal station, return -1. Example 1: input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6 output: 2 explanation: the optimal policy is to take the first bus to station 7 and then transfer to the second bus to station 6. Example 2: input: routes = [[7, 12],,5,15 [4], [6], [15] 3,,12,13 [9]], the source = 15, target = 12 output: 1 tip: 1 <= routes[I]. Length <= 105 Routes [I] Sum (routes[I]. Length) <= 105 0 <= Routes [I][j] < 106 0 <= source, target < 106 Related Topics breadth first search array hash table 👍 146 👎 0Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: BFS

• Because this problem only needs to consider the number of bus routes selected, not the route of the station, so it can use breadth first, the first traversed must be the shortest
• When considering the solution, there are the following questions:
  • Since we were not on the bus at the beginning and were on platform 1, we need to consider whether routes[0] includes platform 1. Of course, this is only a precondition and does not affect the follow-up problem solving process. Without losing generality, we assume that the first route must include the starting platform
• Firstly, confirm the link relationship and store all lines and the platforms contained in the lines into map. Key is the line index and value is the set composed of platforms
• Then all maps are traversed in turn, and deque is stored as the trailing node of BFS traversal when there is a line containing source platform
• Define another map to store the step transferred to the current line with key as the current line index and value as step
• The next step is normal BFS parsing
• The thing to notice here is that there are two boundary cases
  • The beginning and the end are on the same line, and it goes straight back to 0, although I think this boundary conflicts with the problem that the beginning is not on the bus
  • All lines have no starting station

public int numBusesToDestination(int[][] routes, int source, int target) {

            // Establish the inclusion relationship for all lines
            Map<Integer, Set<Integer>> map = new HashMap<>();
            for (int i = 0; i < routes.length; i++) {
                Set<Integer> set = new HashSet<>();
                for (int j = 0; j < routes[i].length; j++) {
                    set.add(routes[i][j]);
                }
                map.put(i, set);
            }

            // Storage line index
            Deque<Integer> deque = new LinkedList<>();
            // Record the number of lines to the current site
            Map<Integer, Integer> res = new HashMap<>();
            // Set the initial platform
            for (Integer i : map.keySet()) {
                if (map.get(i).contains(source)) {
                    deque.add(i);
                    res.put(i, 1); }}//corner case
            if (deque.isEmpty()){
                return -1;
            }
            if (target==source){
                return 0;
            }
            while(! deque.isEmpty()) {int temp = deque.poll();
                int step = res.get(temp);
                for (int i : map.get(temp)) {
                    if (i == target) {
                        return step;
                    }
                    for (int line : map.keySet()) {
                        // All lines containing the current node are added to the deque to continue breadth-first traversal
                        if (res.containsKey(line)) {
                            continue;
                        }
                        if (map.get(line).contains(i)) {
                            deque.add(line);
                            res.put(line, step + 1); }}}}return -1;

        }
Copy the code

Time complexity O(
$\sum_{0}^{n}routes+n^2$)

N is the number of lines, and the sum formula is the number and number of platforms on each line