最小公共区域

Submission

运行时间: 41 ms

内存: 19.2 MB

class Solution:
    def findSmallestRegion(self, regions: List[List[str]], r1: str, r2: str) -> str:
        q, p = set(), {i: j for j, *r in regions for i in r}    #其中i为区域，j为对应的直接父节点，通过(j, *r)分离出数组的第一个元素和后续元素。
        while r1 in p:
            q.add(r1)
            r1 = p[r1]
        while r2 in p:
            if r2 in q:
                return r2
            r2 = p[r2]
        return r2

Explain

本题目的是找到两个区域r1和r2的最小公共区域。首先，根据regions列表建立一个字典p，键为区域名，值为该区域的直接父区域。然后，从r1开始，逐级向上追溯其父区域，并将遇到的每个区域存储在集合q中。之后，从r2开始向上追溯其父区域，直到找到第一个同时存在于集合q中的区域，即为最小公共区域。如果r2的所有父区域都不在集合q中，则返回最顶层的父区域r2。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findSmallestRegion(self, regions: List[List[str]], r1: str, r2: str) -> str:
        q, p = set(), {i: j for j, *r in regions for i in r}    # 创建存储每个区域的父区域的字典
        while r1 in p:  # 从r1向上追溯其父区域
            q.add(r1)  # 将r1及其父区域加入集合q
            r1 = p[r1]  # 更新r1为其父区域
        while r2 in p:  # 从r2向上追溯其父区域
            if r2 in q:  # 如果r2已存在于集合q中，说明找到了最小公共区域
                return r2
            r2 = p[r2]  # 更新r2为其父区域
        return r2  # 如果没有找到公共区域，返回最顶层的父区域r2

Explore

在代码中，使用了一个字典推导式`{i: j for j, *r in regions for i in r}`来构建父区域字典。这种写法利用了Python的解包特性，其中`j`是每个列表的第一个元素，代表父区域，而`*r`是剩余的元素，代表所有子区域。字典推导式中的`for i in r`确保了每个子区域`i`都会被映射到其对应的父区域`j`。因此，这种方法能够确保即使父区域有多个子区域，字典也能正确地映射每个子区域到其父区域。

代码确实没有显式处理r1或r2为顶级区域的情况。在这个算法中，如果r1或r2是顶级区域，它们将不会在字典`p`中作为键出现，因此`while r1 in p`或`while r2 in p`的循环将不会执行。这意味着，如果r1或r2是顶级区域，它们将直接被视为潜在的最小公共区域。因此，可以认为是有一个隐含的假设，即r1和r2通常不是顶级区域，否则算法会直接返回顶级区域本身作为结果。

如果在追踪过程中，r1或r2的某个父区域在字典`p`中没有映射，意味着已经到达了顶级区域，因为顶级区域没有更高的父区域。在代码中，一旦`r1`或`r2`不在字典`p`中，相应的循环就会结束。对于r2，如果在它的追踪过程中未找到与r1共同的区域，最终它会返回当前的r2值，可能是顶级区域。这种处理方式暗示了到达顶级区域后，没有更高的父区域可以追踪，因此返回当前的区域作为最小公共区域。