• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode -1436- Travel terminus

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Paths [I] = [cityAi, cityBi] indicates that the paths will go directly from cityAi to cityBi. Find the final destination of the tour, a city that does not have any route to any other city.

The problem data guarantees that the route diagram will form a circuit with no loops, so that there is exactly one travel destination.

 

Example 1:

Enter: Paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"] It starts at London and ends at Sao Paulo. The itinerary for this trip is "London" -> "New York" -> "Lima" -> "Sao Paulo".Copy the code

Example 2:

Input: paths = [[" B ", "C"], [" D ", "B"], [" C ", "A"]] output: "A" explanation: all possible routes are:  "D" -> "B" -> "C" -> "A". "B" -> "C" -> "A". "C" -> "A". "A". Obviously, the end of the trip is "A".Copy the code

Example 3:

Paths = [["A","Z"]]Copy the code

Tip:

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi ! = cityBi
  • All strings consist of uppercase and lowercase English letters and Spaces.

Idea 1: Hash

  • Store all the starting points into set
  • And then determine if there’s an endpoint that’s not in the starting set
Set<String> set = new HashSet<>();

        public String destCity(List<List<String>> paths) {
            for (List<String> path : paths
            ) {
                set.add(path.get(0));
            }
            for (List<String> path : paths
            ) {
                if(! set.contains(path.get(1))) {return path.get(1); }}return "";
        }
Copy the code
  • Time complexity O(n)
  • Space complexity O(n)