首页
论坛
未名存档
话题女王
小圈子
马甲追踪
版面排名
流量曲线
水枪排名
发帖量曲线
发帖版面饼图
发帖时间柱图
关于本站
帮助
boards
本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字
访问原贴
JobHunting版
- LCA居然有constant time and linear space的解法
相关主题
●
LCA写得想吐
●
一道rocket f 电面题
●
问一道算法题(zz)
●
微软电面题
●
确认一下RMQ/LCA那道老题
●
Least Common Ancester算法最优解
●
请问关于lowest common ancestor的问题。
●
请问如何求binary tree的lowest common ancestor
●
讨论一下LCA的最好算法
●
CLRS上重点章节例题习题
相关话题的讨论汇总
话题: lca
话题: constant
话题: linear
话题: 解法
话题: space
进入JobHunting版参与讨论
1
(共1页)
z*******o
发帖数: 4773
1
还没看懂.
刷无止境啊.....
r*****s
发帖数: 1815
2
Tarjan。需要先知道所有查询才行
基本思想就是利用dfs时候的中间状态,当前访问的节点如果和一个查询相关,且相关
联的另外一个节点如果已经被访问,则dfs路径上最近的那个灰色祖先(灰色即子树未
被完全遍历的节点)即为其公共祖先
需要并查集才能O(n)
r*****s
发帖数: 1815
3
而在线算法预处理是O(NlogN)的,先用LCA -> RMQ
再RMQ O(1)查询
都要预处理。。
: Tarjan。需要先知道所有查询才行
: 基本思想就是利用dfs时候的中间状态,当前访问的节点如果和一个查询相关,
且相关
: 联的另外一个节点如果已经被访问,则dfs路径上最近的那个灰色祖先(灰色即
子树未
: 被完全遍历的节点)即为其公共祖先
: 需要并查集才能O(n)
【在 r*****s 的大作中提到】
: Tarjan。需要先知道所有查询才行
: 基本思想就是利用dfs时候的中间状态,当前访问的节点如果和一个查询相关,且相关
: 联的另外一个节点如果已经被访问,则dfs路径上最近的那个灰色祖先(灰色即子树未
: 被完全遍历的节点)即为其公共祖先
: 需要并查集才能O(n)
1
(共1页)
进入JobHunting版参与讨论
相关主题
●
CLRS上重点章节例题习题
●
一道CS面试题
●
问一道 facebook 面试题
●
问一个G家面试题
●
问个数组相关的题
●
如何判断一个tree是另外一个tree的subtree?
●
[合集] 微软:求一个数列中最长单调上升子列,要求O(nlogn)时间
●
问个array in place operation的题目
●
worst case O(nlogn) quicksort?
●
问一道题(5)
相关话题的讨论汇总
话题: lca
话题: constant
话题: linear
话题: 解法
话题: space