旅途终点站的三种解法

旅途终点站的三种解法

1436. 旅行终点站

难度简单42

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市*。*

题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。

示例 1：

输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo" 
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：

输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A" 。

示例 3：

输入：paths = [["A","Z"]]
输出："Z"

提示：

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• 所有字符串均由大小写英文字母和空格字符组成。

个人所写

这道题并不难,虽然我也想了一小会儿(我脑子里的第一印象是hash表,但是我不知道怎么写),其实用暴力能够做出来,就是判断所到达的地点是不是在所有起点都没有相同的,只要没有,就说明这个到达的地点就是终点;

class Solution
{
public:string destCity(vector<vector<string>> &paths){int n = paths.size();for (int i = 0; i < n; i++){string temp1 = paths[i][1];int j;for (j = 0; j < n; j++){if (temp1 == paths[j][0]){break;}}if (j == n)return temp1;}return "";}
};

上面是暴力,虽然也需要想到这个方法.

我本来以为这种O(n ²)的时间复杂度不大好,

但是这种方法在所有题解中算是很高的,执行用时和内存消耗都击败的用户高达90%;

但是我再补充一下其他的题解,补充一下知识

他人题解

class Solution {
public:string destCity(vector<vector<string>>& paths) {unordered_map<string,int>  helper;for(auto  p:paths){helper[p[0]]+=1;helper[p[1]]+=0;}for(auto  h:helper){if(h.second==0){return h.first;}}return "";}
};

上面代码的做法和本人做法差不多,只不过用了散列表来承载,容量消耗比较大;

他的思想:对于那些出发点,都+=1;(从另一个层面想,对起点都初始化成了1)

而对那些到达点,都+=0,(对于终点都初始化成了0)

这样,如果到最后只有一个地点标记为0,那么就是到达点

(上面的代码解决了我用哈希表没能解决的问题,我个人想的是,将所有的起点和重点都用哈希表来存储,初始化为0,只要出现一个相同的,就直接+1.到最后遍历找答案的时候,会出现问题,因为最初起点和最终点都只有一个(也就是标记为0的点),你根本就不知道那个是终点===>但是上面的代码将所有的起点初始化成了1,将所有终点初始化成了0,这样最初起点和最终终点就分开了,这也是我将上面代码记录下来的原因);

第三种算法

把起点和终点做成两个集合，然后终点集减去起点集，剩下的一个元素就是结果(差集)==>我个人没学过这种求差集的,所以又在网上搜刮了一些资料,整理了一下

交集,并集,差集

对于使用这些函数的时候,一定要注意排序,网上很多资料都没有声明这一点(我也是出了错才发现的)

回到原题,显然,这种算法用在这里太不合时,因为差集需要三个集合才能创建出来,大大浪费了空间,同时对时间也有一定的影响;

总的来看,还是我的暴力比较好,不过之所以写其他的代码,也是为了扩展思维,能弥补自己的缺陷.毕竟在写题解的过程中还多学了差集并集交集的函数,怎么都不亏;