LCA居然有constant time and linear space的解法 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - LCA居然有constant time and linear space的解法

相关主题
● LCA写得想吐	● 讨论一下LCA的最好算法
● 一道rocket f 电面题	● CLRS上重点章节例题习题
● 问一道算法题(zz)	● 一道CS面试题
● 微软电面题	● 问一道 facebook 面试题
● 确认一下RMQ/LCA那道老题	● 问一个G家面试题
● Least Common Ancester算法最优解	● 问个数组相关的题
● 请问关于lowest common ancestor的问题。	● 如何判断一个tree是另外一个tree的subtree？
● 请问如何求binary tree的lowest common ancestor	● [合集] 微软：求一个数列中最长单调上升子列，要求O(nlogn)时间

相关话题的讨论汇总
话题: 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版参与讨论

相关主题
● [合集] 微软：求一个数列中最长单调上升子列，要求O(nlogn)时间	● 确认一下RMQ/LCA那道老题
● 问个array in place operation的题目	● Least Common Ancester算法最优解
● worst case O(nlogn) quicksort?	● 请问关于lowest common ancestor的问题。
● 问一道题（5）	● 请问如何求binary tree的lowest common ancestor
● LCA写得想吐	● 讨论一下LCA的最好算法
● 一道rocket f 电面题	● CLRS上重点章节例题习题
● 问一道算法题(zz)	● 一道CS面试题
● 微软电面题	● 问一道 facebook 面试题

相关话题的讨论汇总
话题: lca话题: constant话题: linear话题: 解法话题: space

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)