博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode题解(1724):检查边长度限制的路径是否存在II(Python)
阅读量:1902 次
发布时间:2019-04-26

本文共 3255 字,大约阅读时间需要 10 分钟。

题目:(困难)

标签:并查集、图、二进制拆分

解法 时间复杂度 空间复杂度 执行用时
Ans 1 (Python) 构造 = O ( ( N + M ) l o g ( N + M ) ) O((N+M)log(N+M)) O((N+M)log(N+M)) ; 操作 = O ( l o g ( N + M ) ) O(log(N+M)) O(log(N+M)) O ( N + M ) O(N+M) O(N+M) 1660ms (66.67%)
Ans 2 (Python)
Ans 3 (Python)

解法一:

class DistanceLimitedPathsExist:    def __init__(self, n: int, edges: List[List[int]]):        # ---------- 数据预处理 ----------        # 计算结点总数:将所有的结点视为叶结点,将所有的边也视为内部结点        # 叶结点(结点)的ID从0开始,内部结点(边)的ID从n开始        m = n + len(edges)        # 依据边的权重升序排序边        edges.sort(key=lambda x: x[2])        def get_top(ii):            """获取当前结点的最远祖先节点"""            if ancestor[ii] != ii:                ancestor[ii] = get_top(ancestor[ii])            return ancestor[ii]        # 记录每一条边的距离:self.edges[i]=dis        # 计算每一个结点的父亲结点:father[i]        # 计算每一个结点的最优祖先节点:ancestor[i]        self.edges = {
} father = [-1] * m ancestor = [i for i in range(m)] for i, (u, v, dis) in enumerate(edges): self.edges[i + n] = dis # 记录当前边的距离 father[get_top(u)] = father[get_top(v)] = i + n # 更新两个结点的最远祖先节点的父亲结点 ancestor[get_top(u)] = ancestor[get_top(v)] = i + n # 更新两个结点的最远祖先节点的最远祖先结点 # ---------- 计算递增上爬法的祖先结点 ---------- # self.jumps[i][j] = 第i个结点的第2^j个祖先结点 self.jumps = [[v] if v != -1 else [] for v in father] for _ in range(15): # 更新父结点信息:每次将父结点更新为父结点的父结点(第二次更新即为父结点的祖父节点,以此类推) have_father = False for i in range(m): if father[i] != -1: father[i] = father[father[i]] have_father = True else: father[i] = -1 if not have_father: break # 将记录更新的父结点:分别其上的第1个结点、第2个结点、第4个结点…… for i in range(m): if father[i] != -1: self.jumps[i].append(father[i]) def query(self, p: int, q: int, limit: int) -> bool: # ---------- 将p和q中更深的结点爬到和另一个结点相同的深度 ---------- # 当p和q在相同的深度时,则有:len(self.jumps[p]) == len(self.jumps[q]) depth_p, depth_q = self._get_depth(p), self._get_depth(q) if depth_p < depth_q: depth_p, depth_q, p, q = depth_q, depth_p, q, p p = self._jump_up(p, depth_p - depth_q) while self.jumps[p] and p != q: # 从上到下寻找第一个不一样的祖先节点:公共祖先节点一定在不一样的祖先节点的上面 for i in range(len(self.jumps[p]) - 1, -1, -1): if self.jumps[p][i] != self.jumps[q][i]: p, q = self.jumps[p][i], self.jumps[q][i] break else: # 如果所有祖先节点都一样,那么他们的父结点就是最近的公共祖先节点 p, q = self.jumps[p][0], self.jumps[q][0] break return p == q and max(self.edges[p], self.edges[q]) < limit def _get_depth(self, node): """计算结点深度:O(logN)""" step = 0 while self.jumps[node]: step += 1 << (len(self.jumps[node]) - 1) node = self.jumps[node][-1] return step def _jump_up(self, node, step): """将结点node向上移动step次:O(logS)""" while step: jump = step.bit_length() - 1 step -= 1 << jump if jump >= len(self.jumps[node]): return -1 node = self.jumps[node][jump] return node

转载地址:http://ixkcf.baihongyu.com/

你可能感兴趣的文章
第10章 Archiving
查看>>
第11章 Basic Core Data
查看>>
第12章 Nib Files and NSWindowController
查看>>
第13章 User Defaults
查看>>
第14章 Using Notifications
查看>>
第17章 custom views
查看>>
第18章 Images and Mouse Events
查看>>
第19~20章 Keyboard Events & Drawing Text with Attributes
查看>>
第21章 Pasteboards and Nil-Targeted Actions
查看>>
第22章 Categories
查看>>
第24章 NSTimer
查看>>
第26章 Creating NSFormatters
查看>>
第29章 View Swapping
查看>>
iphone开发学习资源
查看>>
第2章 Model View Controller
查看>>
“老外学中文“-开发进度
查看>>
我的mac pro,今后我们要一起加油啦!
查看>>
Huffman编码
查看>>
多台上网设备出现上网卡问题
查看>>
独立游戏市场营销策略:社交营销篇
查看>>