X

LEETCODE 1257. Smallest Common Region 解题思路分析

题目大意:

最小公共区域

给你一些区域列表 regions,每个列表的第一个区域都包含这个列表内所有其他区域。

很自然地,如果区域 X 包含区域 Y,那么区域 X 比区域 Y 大。

给定两个区域 region1 和 region2,找到同时包含这两个区域的 最小 区域。

如果区域列表中 r1 包含 r2 和 r3,那么数据保证 r2 不会包含 r3。

数据同样保证最小公共区域一定存在。

示例1:

输入:
 regions = [["Earth","North America","South America"],
 ["North America","United States","Canada"],
 ["United States","New York","Boston"],
 ["Canada","Ontario","Quebec"],
 ["South America","Brazil"]],
 region1 = "Quebec",
 region2 = "New York"
输出:"North America"

提示:

  • 2 <= regions.length <= 10^4
  • region1 != region2
  • 所有字符串只包含英文字母和空格,且最多只有 20 个字母。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1257

解题思路分析:

本题可以理解成一棵树,每个列表的第一个区域为根节点,其余的为第一个区域的子节点,遍历完所有区域列表后,一颗完整的树也就描画出来了。我们定义一个Map来表示树的结构,key为节点名称(某个区域),value是当前节点的父节点。

构建好树形结构之后,我们需要找到2个节点的最小共通父节点,之前做过类似的题目,找共通父节点的思路并不难,简单来说,就是从当前2节点向最顶的父节点画线,由于是树形结构,因此,从子节点到最顶部的根节点一定只存在唯一的路线,路线上每一个节点都是当前节点的父节点。2个子节点就存在2条路线,这2条路线的相交点即是最小共通父节点。

解题时,我们可以不断记录从当前2节点向顶部移动时经过的每一个节点,当某个节点重复出现时,即是答案。

实现代码:

public String findSmallestRegion(List<List<String>> regions,
                                String region1, String region2) {
    // 描画树形结构,key是当前节点,value为父节点
    Map<String, String> map = new HashMap<>();
    for(List<String> region:regions){
        // 首元素为父节点
        String first=region.get(0);
        for(int i=1;i<region.size();i++){
            // 当前列表中每个元素的父节点为列表首元素
            map.put(region.get(i),first);
        }
    }
    // 记录访问过的父节点
    Set<String> set = new HashSet<>();
    // 从两个子节点开始向最顶部移动,找到第一个相交点
    while(region1!=null || region2!=null){
        if(region1 != null){
            // 如果已经访问过region1,这是一个相交点,直接返回
            if(set.contains(region1)) return region1;
            // 将当前节点加入列表
            set.add(region1);
            // 将当前节点更新为其父节点,继续向上移动  
            region1=map.get(region1);
        }
        if(region2 != null){
            // 如果已经访问过region2,这是一个相交点,直接返回
            if(set.contains(region2)) return region2;
            // 将当前节点加入列表
            set.add(region2);
            // 将当前节点更新为其父节点,继续向上移动  
            region2=map.get(region2);
        }
    }
    return null;
}

本题解法运行时间为9ms。

Runtime: 9 ms, faster than 98.45% of Java online submissions forSmallest Common Region.

Memory Usage: 46.6 MB, less than 100.00% of Java online submissions for Smallest Common Region.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1257-smallest-common-region-解题思路分析/
Categories: leetcode
kwantong: