Question

1436. 旅行终点站

English Version

题目描述

给你一份旅游线路图，该线路图中的旅行线路用数组 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
• 所有字符串均由大小写英文字母和空格字符组成。

解法

方法一：哈希表

将所有起点存入哈希表中，然后遍历所有终点，找出没出现在哈希表中的终点，即为答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是线路数。

class Solution:
  def destCity(self, paths: List[List[str]]) -> str:
    s = {a for a, _ in paths}
    return next(b for _, b in paths if b not in s)

class Solution {
  public String destCity(List<List<String>> paths) {
    Set<String> s = new HashSet<>();
    for (var p : paths) {
      s.add(p.get(0));
    }
    for (var p : paths) {
      if (!s.contains(p.get(1))) {
        return p.get(1);
      }
    }
    return "";
  }
}

class Solution {
public:
  string destCity(vector<vector<string>>& paths) {
    unordered_set<string> s;
    for (auto& p : paths) {
      s.insert(p[0]);
    }
    for (auto& p : paths) {
      if (!s.count(p[1])) {
        return p[1];
      }
    }
    return "";
  }
};

func destCity(paths [][]string) string {
  s := map[string]bool{}
  for _, p := range paths {
    s[p[0]] = true
  }
  for _, p := range paths {
    if !s[p[1]] {
      return p[1]
    }
  }
  return ""
}

function destCity(paths: string[][]): string {
  const set = new Set(paths.map(([a]) => a));
  for (const [_, b] of paths) {
    if (!set.has(b)) {
      return b;
    }
  }
  return '';
}

use std::collections::HashSet;
impl Solution {
  pub fn dest_city(paths: Vec<Vec<String>>) -> String {
    let set = paths
      .iter()
      .map(|v| &v[0])
      .collect::<HashSet<&String>>();
    for path in paths.iter() {
      if !set.contains(&path[1]) {
        return path[1].clone();
      }
    }
    String::new()
  }
}

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function (paths) {
  const s = new Set();
  for (const [a, _] of paths) {
    s.add(a);
  }
  for (const [_, b] of paths) {
    if (!s.has(b)) {
      return b;
    }
  }
  return '';
};

char* destCity(char*** paths, int pathsSize, int* pathsColSize) {
  for (int i = 0; i < pathsSize; i++) {
    int flag = 1;
    for (int j = 0; j < pathsSize; j++) {
      if (strcmp(paths[i][1], paths[j][0]) == 0) {
        flag = 0;
        break;
      }
    }
    if (flag) {
      return paths[i][1];
    }
  }
  return NULL;
}