Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Topic describes

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". Source: the power button (LeetCode) link: https://leetcode-cn.com/problems/destination-city copyright shall belong to the collar of the network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • Today’s algorithm of the day is a travel route problem, which gives the starting point and end point of the path. The data in the problem ensures that the route map will form a route without circulation, so there is exactly one travel destination. This is the key to solve the problem. We use hashMap to store all the starting points, and the data that is not in it is the data of the end point. The code is as follows:

Through the code

class Solution {
    public String destCity(List<List<String>> paths) {
        String ans = "";
        Set<String> beginCity = new HashSet<>();
        for (List<String> path : paths) {
            beginCity.add(path.get(0));
        }
        for (List<String> path : paths) {
            if (beginCity.contains(path.get(1))) {
                continue;
            } else {
                ans = path.get(1);
                break; }}returnans; }}Copy the code

conclusion

  • This code is O(n) in time and O(n) in space
  • Adhere to the algorithm of the day, come on!