“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:
- Put all the starting points into the collection
set
- 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 ❤