CTF of Z2BNS
0%

旅行终点站

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 702 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

示例1：

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

示例2：

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

示例3：

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

提示：

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

思路：

每个paths[i]的第一个元素是出发站，第二个是终点站。旅行的终点站也就是没有通往其他城市的路线。也就是说只要找第二个位置出现过而在第一个位置没出现过的城市。

双层for循环遍历，对每一条路线的到达站遍历所有的线路是否作为过出发站。

c++代码：(执行用时24ms，击败92.48%，内存消耗10.1M，击败89.27%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        int n=paths.size();
        string result="";
        //对每一条路线的到达站进行遍历判断是否是终点站
        for(int i=0;i<n;++i){
            //默认为true，不是终点站再改为false
            bool flag=true;
            for(int j=0;j<n;++j){
                if(paths[i][1]==paths[j][0]){
                    //不是终点站
                    flag=false;
                    break;
                }
            }
            if(flag){
                result=paths[i][1];
                //只有一个旅行终点站，找到后终止循环
                break;
            }
        }
        return result;
    }
};
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

没有官方题解，不过我这个代码效率也挺高了，对双百最接近的一次，哈哈哈😁

------------- THE END! THANKS! -------------