leetcode1436：旅行终点站（destination-city）

carloscn commented 1 year ago

问题描述

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

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/destination-city

carloscn commented 1 year ago

问题分析

把所有的字符串都拼接成为一个字符串，唯一且index在奇数位的就是终点。

pub fn dest_city(paths: Vec<Vec<String>>) -> String
{
    if paths.len() < 1 {
        return "".to_string();
    }

    let mut ret:String = String::new();
    let mut con_paths:Vec<String> = vec![];

    for city in &paths {
        con_paths.push(city[0].clone());
        con_paths.push(city[1].clone());
    }

    let mut dest_city_list:Vec<String> = con_paths.clone();
    let mut single_list:Vec<String> = vec![];
    dest_city_list.sort();

    for e in &dest_city_list {
        if single_list.is_empty() {
            single_list.push(e.clone());
            continue;
        }
        if single_list[single_list.len() - 1] != *e {
            single_list.push(e.clone());
        } else {
            single_list.pop();
        }
    }

    if single_list.len() == 1 {
        ret = single_list[0].clone();
        return ret;
    }

    for city in single_list {
        if con_paths.iter()
                    .position(|r| *r == city).unwrap() & 0x1 == 1 {
            ret = city;
            return ret;
        }
    }

    return ret;
}

carloscn commented 1 year ago

code

https://review.gerrithub.io/c/carloscn/structstudy/+/554175 https://github.com/carloscn/structstudy/commit/288cef06e073d4b511ff4332b7683d43d78b3bf3

carloscn / structstudy