leetCode/1436.旅行终点站.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>1436. 旅行终点站</title>
  </head>
  <body>
    <script>
      // https://leetcode.cn/problems/destination-city/

      // 给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。
      // 题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。
      // 提示：
      // 1 <= paths.length <= 100
      // paths[i].length == 2
      // 1 <= cityAi.length, cityBi.length <= 10
      // cityAi != cityBi
      // 所有字符串均由大小写英文字母和空格字符组成。

      /**
       * @param {string[][]} paths
       * @return {string}
       */
      var destCity = function (paths) {};

      // --- answer-1 ---

      // 题目中说明只有一条线路 那么形如列表我们从任一节点出发 直到尾结点
      var destCity = function (paths = [[]]) {
        // 使用map构建链
        const map = paths.reduce((map, cur) => {
          map.set(cur[0], cur[1]);
          return map;
        }, new Map());
        let start = paths[0][0];
        while (map.has(start)) {
          start = map.get(start);
        }
        return start;
      };

      // --- answer-1 ---

      // --- answer-2 ---

      // --- answer-2 ---

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

      var paths = [
        ['B', 'C'],
        ['D', 'B'],
        ['C', 'A']
      ];
      var result = 'A';
      // 解释：所有可能的线路是：

      var paths = [['A', 'Z']];
      var result = 'Z';

      console.log('paths = ', paths);
      console.log('result = ', result);
      console.log('destCity = ', destCity(paths));
    </script>
  </body>
</html>