前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 1436. 旅行终点站

LeetCode 1436. 旅行终点站

原创
作者头像
freesan44
修改2021-09-07 18:12:53
2950
修改2021-09-07 18:12:53
举报
文章被收录于专栏:freesan44freesan44

题目

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

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

代码语言:txt
复制
示例 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

pathsi.length == 2

1 <= cityAi.length, cityBi.length <= 10

cityAi != cityBi

所有字符串均由大小写英文字母和空格字符组成。

解题思路

代码语言:txt
复制
class Solution:

    def destCity(self, paths: List[List[str]]) -> str:

        # 用字典形式存储地点

        resDict = dict()

        for iList in paths:

            #如果地点存在,就删除【因为本来就是对数存在】,不存在就添加,并记录是起点还是终点

            for index,val in enumerate(iList):

                if val in resDict:

                    del resDict[val]

                else:

                    resDict[val] = index

        for key,val in resDict.items():

            #val== 1为终点位置

            if val == 1:

                return key









if \_\_name\_\_ == '\_\_main\_\_':

    paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]

    ret = Solution().destCity(paths)

    print(ret)

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 解题思路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档