Google – Average Length of City Path

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就可以得到答案了。

class Solution2 {

  int sum = 0;

  int n;

  public int averagePathLength(int n, int[][] graph) {

    if (n <= 1) {

      return 0;

    }

     

    this.n = n;

     

    // get degree of every node

    Map<Integer, Integer> degree = new HashMap<>();

    for (int i = 0; i < n; i++) {

      for (int j = 0; j < n; j++) {

        if (graph[i][j] != 0) {

          degree.put(i, degree.getOrDefault(i, 0) + 1);

          degree.put(j, degree.getOrDefault(j, 0) + 1);

        }

      }

    }

     

    // Build the tree

    TNode root = buildTree(degree, graph);

     

    // dfs traversal to get the path sum

    dfs(root);

     

    return sum / (n - 1);

  }

   

  private void dfs(TNode root) {

    if (root == null) {

      return null;

    }

     

    for (TNode child : root.children) {

      sum += child.size * (n - child.size) * graph[root.val][child.val];

      dfs(child);

    }

  }

   

  private TNode buildTree(Map<Integer, Integer> degree, int[][] graph) {

     

    Map<Integer, TNode> nodeMap = new HashMap<>();

    for (int i = 0; i < n; i++) {

      nodeMap.put(i, new TNode(i));

    }

     

    Queue<Integer> queue = new LinkedList<>();

    for (int v : degree) {

      if (degree.get(v) == 1) {

        queue.add(v);

        nodeMap.get(v).size += 1;

      }

    }

    for (int v : queue) {

      degree.remove(v);

    }

     

    while (true) {

      int size = queue.size();

      for (int i = 0; i < size; i++) {

        int curr = queue.poll();

        int currSize = nodeMap.get(curr).size;

         

        for (int adj = 0; adj < n; adj++) {

          if (graph[curr][adj] != 0) {

            nodeMap.get(adj).children.add(curr);

            nodeMap.get(adj).size += currSize;

             

            degree.put(adj, degree.get(adj) - 1);

            if (degree.get(adj) == 1) {

              queue.offer(adj);

            }

          }

        }

      }

       

      for (int v : queue) {

        degree.remove(v);

      }

       

      if (degree.isEmpty()) {

        break;

      }

    }

     

     

    if (queue.size() > 1) {

      int root1 = queue.poll();

      int root2 = queue.poll();

      nodeMap.get(root1).children.add(root2);

      nodeMap.get(root1).size += nodeMap.get(root2).size;

      return nodeMap.get(root1);

    }

     

    return nodeMap.get(queue.poll());

  }

  

 

  private class TNode {

    int val;

    List<TNode> children;

    int size;

     

    TNode(int val) {

      this.val = val;

      this.children = new ArrayList<>();

    }

  }

}

http://www.1point3acres.com/bbs/thread-139392-1-1.html
Read full article from Google – Average Length of City Path