【LeetCode】1436.旅行終点Destination City(Python)
テーマの説明
旅行の路線図をあげます.路線図の中の旅行用の行列
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
与えられたのは方向図がありますか?旅行の終点駅を探してください.
問題の解き方
セット
第一の感覚はトポロジーの順序ですが、今週のEasy問題は簡単です.
旅行の終点駅は一つしかありません.
ですから、どの駅が出ていないかを見つければいいです.一つの駅だけが出発点に現れません.
ですから、すべての駅を統計してみます.もし出発点に一つの駅が現れなかったら、この駅は最終的な旅行終点駅です.
Pythonコードは以下の通りです.
class Solution(object):
def destCity(self, paths):
"""
:type paths: List[List[str]]
:rtype: str
"""
starts = set()
ends = set()
for path in paths:
starts.add(path[0])
ends.add(path[1])
for end in ends:
if end not in starts:
return end
return ""
負の雪の明かりのろうそくのが書いてブログを書くことに注意することを歓迎して、leetcodeは書いて800余り書いて、すべて詳しく書きました!日付
2020年5月3日——天気が暑くて、瞬間的に夏になります.