每日力扣练习 - 1436. 旅行终点站

迈不过友情╰ 2022-12-10 04:00 114阅读 0赞

### 文章目录 ###

*   *  1、题目描述
     *  2、解题代码
     *  3、简要分析

## 1、题目描述 ##

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

## 2、解题代码 ##

class Solution {
        public String destCity(List<List<String>> paths) {
            List<String> one = paths.get(0);
            String some = one.get(1);
            while(true) {
                boolean boo = false;
                for(List<String> list : paths) {
                    if(some.equals(list.get(0))) {
                        boo = true;
                        some = list.get(1);
                        break;
                    }
                }
    
                if(!boo){
                    break;
                }
            }
            return some;
        }
    }

## 3、简要分析 ##

简单说下我想到的思路，就是随便拿出来一个list的第二个元素，跟剩余其他的list的第一个元素去比较。

如果有比较的结果，那么用新值替换刚才的值，再次和其他值进行比较。

如果没有比较到相同的值，那么这个值就是答案。

看到有人说了一种更好的方案，**不存在于起点的终点就是答案**。

class Solution { 
        public String destCity(List<List<String>> paths) { 
            // List<String> one = paths.get(0);
            // String some = one.get(1);
            // while(true) { 
            // boolean boo = false;
            // for(List<String> list : paths) { 
            // if(some.equals(list.get(0))) { 
            // boo = true;
            // some = list.get(1);
            // break;
            // }
            // }
    
            // if(!boo){ 
            // break;
            // }
            // }
            // return some;
    
            //不存在于起点的终点就是答案
            Map<String,String> qidian = new HashMap<>();
            for(List<String> list : paths) { 
                qidian.put(list.get(0),"true");
            }
            //现在qidian里面有全部的起点
            for(List<String> list : paths) { 
                if(qidian.get(list.get(1)) == null) { 
                    return list.get(1);
                }
            }
    
            return "end";
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1448078cb72449c5ab33307fce8c563e.png