Finding the Root of a Tree (Finding the Common Destination)
- Time:2020-09-09 14:04:20
- Class:Weblog
- Read:38
You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.
It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.
Example 1:
Input: paths = [[“London”,”New York”],[“New York”,”Lima”],[“Lima”,”Sao Paulo”]]
Output: “Sao Paulo”
Explanation: Starting at “London” city you will reach “Sao Paulo” city which is the destination city. Your trip consist of: “London” -> “New York” -> “Lima” -> “Sao Paulo”.Example 2:
Input: paths = [[“B”,”C”],[“D”,”B”],[“C”,”A”]]
Output: “A”
Explanation: All possible trips are:
“D” – “B” – “C” – “A”.
“B” – “C” – “A”.
“C” – “A”.
“A”.
Clearly the destination city is “A”.Example 3:
Input: paths = [[“A”,”Z”]]
Output: “Z”Constraints:
1 <= paths.length <= 100
paths[i].length == 2
1 <= cityAi.length, cityBi.length <= 10
cityAi != cityBi
All strings consist of lowercase and uppercase English letters and the space character.Hints:
Start in any city and use the path to move to the next city.
Eventually, you will reach a city with no path outgoing, this is the destination city.
Finding the Root of the Tree
Finding the common destination is equivalent as finding the root of (common ancestor) of the tree. The given input contains a list of a line segment that we can use to construct the tree. Then, we start from any of the node, iteratively traversing until we can’t go further, which is guaranteed to be the root.
The following C++ uses a hash map to store the paths between nodes. The complexity is O(N). In the best case, it only needs to go through the paths once, and in the worst case, twice (the longest path).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: string destCity(vector<vector<string>>& paths) { unordered_map<string, string> data; for (const auto &n: paths) { data[n[0]] = n[1]; } string city = paths[0][0]; while (data.find(city) != data.end()) { city = data[city]; } return city; } }; |
class Solution { public: string destCity(vector<vector<string>>& paths) { unordered_map<string, string> data; for (const auto &n: paths) { data[n[0]] = n[1]; } string city = paths[0][0]; while (data.find(city) != data.end()) { city = data[city]; } return city; } };
Another algorithm is to push all the nodes into a set e.g. unordered_set. And the second time, we remove the start from the set, and remaining node in the set must be the destination.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: string destCity(vector<vector<string>>& paths) { unordered_set<string> cities; for (const auto &n: paths) { cities.insert(n[0]); cities.insert(n[1]); } for (const auto &n: paths) { cities.erase(n[0]); } return *begin(cities); } }; |
class Solution { public: string destCity(vector<vector<string>>& paths) { unordered_set<string> cities; for (const auto &n: paths) { cities.insert(n[0]); cities.insert(n[1]); } for (const auto &n: paths) { cities.erase(n[0]); } return *begin(cities); } };
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:Bruteforce/BackTracking Algorithm to Split Array into Fibonacci
How to Avoid Paying Too Much Fee when Cashing out Bitcoin via Wi
The Common Kodi Errors and Use of Free VPN for Linux
Java Pattern: Use Atomic Boolean to Return Single Usage Object
Significance of HTML and CSS in Mobile App Development
How to Reverse Words in a String using Modern Programming Langua
The Python Function to Retrieve the Producer Reward for Witness
Function to Compute the Average Salary Excluding the Minimum and
Efficient Algorithms to Compute The kth Factor of a Natural Numb
Can We Make Arithmetic Progression From Sequence of Numbers?
- Comment list
-
- Comment add