Google – Average Length of City Path
给n个城市，和n – 1条edge, 这些edges可以保证所有城市都两两互通，每条edge都有长度，求所有城市两两之间path的长度之和，再除以path的数量得到的平均数。
[Solution]
第一种解法就是brute force，O(n^2) time
第二种解法来自一亩三分地，可以在O(n)时间内解决问题。思路非常tricky，类似于Leetcode 310 Minimum Height Tree的解法。
因为题目明确给出了有n个node和n – 1条edges，看到这两个数字应该很本能的反应出这道题和tree拖不了关系。但是Brute Force的解法并没有利用到这个条件。而O(n)的解法正是利用构建Minimum Height Tree来解决问题。下面是算法思路：
(1)算degree
(2)逐层删leaf node来找root。就是Minimum Height Tree的算法。
(3)在删leaf node的过程中多做两件事：建tree和计算sub tree size(包括该节点本身)。如果在第(2)步有两个root，随便选一个作为root，另一个作为子节点就好。这里的主要目的是建Tree.
(4)如果总共有N个结点，当前结点v的sub tree size为K (包括v本身)，那么连接v和其parent的那条edge就会被遍历K * (N-K)次。
这是因为如果以v为分界把这个graph分为两部分，一部分有K个点，另一部分为N-K个点。因为每对Pair都需要走一遍，也就是左边的K个点中的任何一个都要去找右边的N-K个点。又因为树的特性，每对pair之间只可能有一条path，所以v到其parent之间的这条edge必定会被遍历K * (N-K)次。
(5)构建完tree，证明完(4)，剩下的只需要对tree做一个dfs traversal，就可以得到总的path sum。再除以n-1就可以得到答案了。
Read full article from Google – Average Length of City Path
No comments:
Post a Comment