“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”


Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.


Title description:

Paths [I] = [cityAi, cityBi] indicates that the paths will go directly from cityAi to cityBi. Please find the end of the tour, i.e. a city without any routes to other cities *. *

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

Answer:

C + + :

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        map<string,int> str_num;
        for(auto &x:paths){
            if(str_num[x[0= =]]0)str_num[x[0]] =- 1;
            else if(str_num[x[0= =]]1) str_num[x[0]] =2;

            if(str_num[x[1= =]]0)str_num[x[1]] =1;
            else if(str_num[x[1= =]]- 1) str_num[x[1]] =2;
            //cout<<str_num[x[0]]<<"**"<<str_num[x[1]]<<endl;
        }

        string ans;
        for(auto pos=str_num.begin(a); pos! =str_num.end(a); ++pos){if(pos->second==1){
                ans=pos->first;
                break; }}returnans; }};Copy the code

JavaScript:

For a path [I] = [cityAi, cityBi], if the city appears in cityAi, it must lead to cityBi; And the terminal must be in cityBi. So just find something in cityBi that doesn’t appear in cityAi

Concrete implementation:

  1. Put all the starting points into the collectionset
  2. You go through all the ends, if you’re not in the set, you’re at the end
const destCity = paths= > {
    const set = new Set(a);const len = paths.length;
    for (let i = 0; i < len; i++) {
        // Put all the starting points into the collection
        set.add(paths[i][0]);
    }
    for (let i = 0; i < len; i++) {
        // Go through all the endpoints
        if(! set.has(paths[i][1])) return paths[i][1]; }};Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤