Thursday, November 26, 2015

Leetcode 310 - Minimum Height Trees


leetcode Minimum Height Trees - 细语呢喃
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4edges = [[1, 0], [1, 2], [1, 3]]
        0
        |
        1
       / \
      2   3
return [1]
Example 2:
Given n = 6edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
     0  1  2
      \ | /
        3
        |
        4
        |
        5
return [3, 4]
Hint:
  1. How many MHTs can a graph have at most?
Note:
(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
http://algobox.org/minimum-height-trees/
Our problem want us to find the minimum height trees and return their root labels. First we can think about a simple case — a path graph.
For a path graph of n nodes, find the minimum height trees is trivial. Just designate the middle point(s) as roots.
Despite its triviality, let design a algorithm to find them.
Suppose we don’t know n, nor do we have random access of the nodes. We have to traversal. It is very easy to get the idea of two pointers. One from each end and move at the same speed. When they meet or they are one step away, (depends on the parity of n), we have the roots we want.
This gives us a lot of useful ideas to crack our real problem.
For a tree we can do some thing similar. We start from every end, by end we mean vertex of degree 1 (aka leaves). We let the pointers move the same speed. When two pointers meet, we keep only one of them, until the last two pointers meet or one step away we then find the roots.
It is easy to see that the last two pointers are from the two ends of the longest path in the graph.
The actual implementation is similar to the BFS topological sort. Remove the leaves, update the degrees of inner vertexes. Then remove the new leaves. Doing so level by level until there are 2 or 1 nodes left. What’s left is our answer!
The time complexity and space complexity are both O(n).
Note that for a tree we always have V = nE = n-1
 Using List is faster than my solution using HashMap.
Whenever the Direct Access Table is possible I usually avoid Hash Table. It it better both in time and space.

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);

    List<Set<Integer>> adj = new ArrayList<>(n);
    for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    List<Integer> leaves = new ArrayList<>();
    for (int i = 0; i < n; ++i)
        if (adj.get(i).size() == 1) leaves.add(i);

    while (n > 2) {
        n -= leaves.size();
        List<Integer> newLeaves = new ArrayList<>();
        for (int i : leaves) {
            int j = adj.get(i).iterator().next();
            adj.get(j).remove(i);
            if (adj.get(j).size() == 1) newLeaves.add(j);
        }
        leaves = newLeaves;
    }
    return leaves;
}
http://buttercola.blogspot.com/2016/01/leetcode-minimum-height-trees.html
1. Note in the implementation, we use List<Set<Integer>> to represent a adj list. That is because the vertex Id ranges from 0 to n - 1, we can use the list index to represent the vertex Id. 
2. In the implementation, we don't really delete the leaf nodes, which will result in an O(n) time since the adjList is a list. Instead, we find the leaf nodes in each iteration and remove it in the neighbor list. Then we find out the new leaf nodes.
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
         
        // Corner case: there is a single node and no edge at all
        if (n == 1 && edges.length == 0) {
            result.add(0);
            return result;
        }
         
        // Step 1: construct the graph
        List<Set<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }
         
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            adjList.get(from).add(to);
            adjList.get(to).add(from);
        }
        // Remove leaf nodes
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (adjList.get(i).size() == 1) {
                leaves.add(i);
            }
        }
        while (n > 2) {
            // identify and remove all leaf nodes
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = adjList.get(leaf).iterator().next();
                adjList.get(neighbor).remove(leaf);
                 
                if (adjList.get(neighbor).size() == 1) {
                    newLeaves.add(neighbor);
                }
            }
             
            leaves = newLeaves;
        }
         
        return leaves;
    }
http://www.cnblogs.com/grandyang/p/5000291.html
这道题虽然是树的题目,但是跟其最接近的题目是Course Schedule 课程清单Course Schedule II 课程清单之二。由于LeetCode中的树的题目主要都是针对于二叉树的,而这道题虽说是树但其实本质是想考察图的知识,这道题刚开始在拿到的时候,我最先想到的解法是遍历的点,以每个点都当做根节点,算出高度,然后找出最小的,但是一时半会又写不出程序来,于是上网看看大家的解法,发现大家推崇的方法是一个类似剥洋葱的方法,就是一层一层的褪去叶节点,最后剩下的一个或两个节点就是我们要求的最小高度树的根节点,这种思路非常的巧妙,而且实现起来也不难,跟之前那到课程清单的题一样,我们需要建立一个图g,是一个二维数组,其中g[i]是一个一维数组,保存了i节点可以到达的所有节点。还需要一个一维数组d用来保存各个节点的入度信息,其中d[i]表示i节点的入度数。我们的目标是删除所有的叶节点,叶节点的入度为1,所以我们开始将所有入度为1的节点(叶节点)都存入到一个队列queue中,然后我们遍历每一个叶节点,通过图来找到和其相连的节点,将该节点的入度减1,如果该节点的入度减到1了,说明此节点也也变成一个叶节点了,加入队列中,再下一轮删除。那么我们删到什么时候呢,当节点数小于等于2时候停止,此时剩下的一个或两个节点就是我们要求的最小高度树的根节点啦
    vector<int> findMinHeightTrees(int n, vector<pair<int, int> >& edges) {
        if (n == 1) return {0};
        vector<int> res, d(n, 0);
        vector<vector<int> > g(n, vector<int>());
        queue<int> q;
        for (auto a : edges) {
            g[a.first].push_back(a.second);
            ++d[a.first];
            g[a.second].push_back(a.first);
            ++d[a.second];
        }
        for (int i = 0; i < n; ++i) {
            if (d[i] == 1) q.push(i);
        }
        while (n > 2) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                int t = q.front(); q.pop();
                --n;
                for (int i : g[t]) {
                    --d[i];
                    if (d[i] == 1) q.push(i);
                }
            }
        }
        while (!q.empty()) {
            res.push_back(q.front()); q.pop();
        }
        return res;
    }

基本思路是“逐层删去叶子节点,直到剩下根节点为止”

有点类似于拓扑排序

最终剩下的节点个数可能为1或者2

时间复杂度:O(n),其中n为顶点的个数。
答案一定是最长距离的中间结点位置上。
我们要的是中间结点,沿着树的外围每次把叶子结点砍掉,那么,最后剩下的不就是中间结点了么?
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n==1: return [0]
        digree = [0 for i in xrange(n)]
        g = [[] for i in xrange(n)]
        for x,y in edges:
            digree[x] += 1
            digree[y] += 1
            g[x].append(y) #add_edge
            g[y].append(x)
        leaves = [i for i in xrange(n) if digree[i]==1]
        nodes = n
        while nodes > 2:
            temp = []
            for i in leaves:
                digree[i] = 0
                nodes -= 1
                for j in g[i]:
                    digree[j] -= 1
                    if digree[j] == 1:
                        temp.append(j)
            leaves = temp
        return leaves
http://bookshadow.com/weblog/2015/11/26/leetcode-minimum-height-trees/
def findMinHeightTrees(self, n, edges): """ :type n: int :type edges: List[List[int]] :rtype: List[int] """ children = collections.defaultdict(set) for e in edges: children[e[0]].add(e[1]) children[e[1]].add(e[0]) vertices = set(children.keys()) while len(vertices) > 2: leaves = [x for x in children if len(children[x]) == 1] // previous solution better for x in leaves: for y in children[x]: children[y].remove(x) del children[x] vertices.remove(x) return list(vertices) if n != 1 else [0]
It's easy to know there are most two nodes to return, which are the medium nodes in the longest path in the tree. level travels, remove the leafs level by level
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    //check for the single node situation
    List<Integer> queue = new LinkedList<Integer>();
    if (n < 2) {
        queue.add(0);
        return queue;
    }
    //initiate map, indegree, and queue
    int count = n;
    int[] indegree = new int[n];
    Map<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
    for (int i = 0; i < count; i++) {
        map.put(i, new HashSet<Integer>());
    }
    for (int[] edge: edges) {
        map.get(edge[0]).add(edge[1]);
        map.get(edge[1]).add(edge[0]);
        indegree[edge[0]]++;
        indegree[edge[1]]++;
    }
    for (int i = 0; i < count; i++){
        if (indegree[i] == 1)
            queue.add(i);
    }
    //check from the outer layer to inner layer, stop when count == 1 or 2
    //which means we arrive at the center
    while (count > 2) {
        List<Integer> newqueue = new LinkedList<Integer>();
        for (int cur: queue) {
            count--;
            for (int next: map.get(cur)) {
                map.get(next).remove(cur);
                if (--indegree[next] == 1)
                    newqueue.add(next);
            }
        }
        queue = newqueue;
    }
    return queue;

}
https://leetcode.com/discuss/71738/easiest-75-ms-java-solution
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<Integer> leaves = new ArrayList<>();
    if(n <= 1) {leaves.add(0); return leaves;}

    // Construct adjencent graph
    Map<Integer, Set<Integer>> graph = new HashMap<>();   // use list<set<>>
    for(int i = 0; i < n; i++) graph.put(i, new HashSet<Integer>());
    for(int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }

    // Add leaves which have one leaf
    for(int i = 0; i < n; i++) {
        if(graph.get(i).size() == 1) leaves.add(i);
    }

    // Remove leaves level by level
    while(n > 2) {
        List<Integer> newLeaves = new ArrayList<>();
        for(int leaf : leaves) {
            for(int nb : graph.get(leaf)) {
                // Remove connection
                graph.get(leaf).remove(nb);
                graph.get(nb).remove(leaf);
                n--;
                if(graph.get(nb).size() == 1) {
                    newLeaves.add(nb);
                }
            }
        }
        leaves = newLeaves;
    }
    return leaves;
}
X. TODO
https://discuss.leetcode.com/topic/30956/two-o-n-solutions
Longest Path
It is easy to see that the root of an MHT has to be the middle point (or two middle points) of the longest path of the tree. Though multiple longest paths can appear in an unrooted tree, they must share the same middle point(s).
Computing the longest path of a unrooted tree can be done, in O(n) time, by tree dp, or simply 2 tree traversals (dfs or bfs). The following is some thought of the latter.
Randomly select a node x as the root, do a dfs/bfs to find the node y that has the longest distance from x. Then y must be one of the endpoints on some longest path. Let y the new root, and do another dfs/bfs. Find the node z that has the longest distance from y.
Now, the path from y to z is the longest one, and thus its middle point(s) is the answer.
int n;
List<Integer>[] e;

private void bfs(int start, int[] dist, int[] pre) {
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<>();
    queue.add(start);
    dist[start] = 0;
    visited[start] = true;
    pre[start] = -1;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : e[u])
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                queue.add(v);
                pre[v] = u;
            }
    }
}

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n <= 0) return new ArrayList<>();
    this.n = n;
    e = new List[n];
    for (int i = 0; i < n; i++)
        e[i] = new ArrayList<>();
    for (int[] pair : edges) {
        int u = pair[0];
        int v = pair[1];
        e[u].add(v);
        e[v].add(u);
    }

    int[] d1 = new int[n];
    int[] d2 = new int[n];
    int[] pre = new int[n];
    bfs(0, d1, pre);
    int u = 0;
    for (int i = 0; i < n; i++)
        if (d1[i] > d1[u]) u = i;

    bfs(u, d2, pre);
    int v = 0;
    for (int i = 0; i < n; i++)
        if (d2[i] > d2[v]) v = i;

    List<Integer> list = new ArrayList<>();
    while (v != -1) {
        list.add(v);
        v = pre[v];
    }

    if (list.size() % 2 == 1) return Arrays.asList(list.get(list.size() / 2));
    else return Arrays.asList(list.get(list.size() / 2 - 1), list.get(list.size() / 2));
}

Tree DP
Alternatively, one can solve this problem directly by tree dp. Let dp[i] be the height of the tree when the tree root is i. We compute dp[0] ... dp[n - 1] by tree dp in a dfs manner.
Arbitrarily pick a node, say node 0, as the root, and do a dfs. When we reach a node u, and let T be the subtree by removing all u's descendant (see the right figure below). We maintain a variable acc that keeps track of the length of the longest path in T with one endpoint being u. Then dp[u] = max(height[u], acc) Note, acc is 0 for the root of the tree.
             |                 |
             .                 .
            /|\               /|\
           * u *             * u *
            /|\
           / | \
          *  v  *
. denotes a single node, and * denotes a subtree (possibly empty).
Now it remains to calculate the new acc for any of u's child, v. It is easy to see that the new acc is the max of the following
  1. acc + 1 --- extend the previous path by edge uv;
  2. max(height[v'] + 2), where v != v' --- see below for an example.
             u
            /|
           / |
          v' v
          |
          .
          .
          .
          |
          .
    
In fact, the second case can be computed in O(1) time instead of spending a time proportional to the degree of u. Otherwise, the runtime can be quadratic when the degree of some node is Omega(n). The trick here is to maintain two heights of each node, the largest height (the conventional height), and the second largest height (the height of the node after removing the branch w.r.t. the largest height).
Therefore, after the dfs, all dp[i]'s are computed, and the problem can be answered trivially. 
int n;
List<Integer>[] e;
int[] height1;
int[] height2;
int[] dp;

private void dfs(int u, int parent) {
    height1[u] = height2[u] = -Integer.MIN_VALUE / 10;
    for (int v : e[u])
        if (v != parent) {
            dfs(v, u);
            int tmp = height1[v] + 1;
            if (tmp > height1[u]) {
                height2[u] = height1[u];
                height1[u] = tmp;
            } else if (tmp > height2[u]) {
                height2[u] = tmp;
            }
        }
    height1[u] = Math.max(height1[u], 0); // in case u is a leaf.
}

private void dfs(int u, int parent, int acc) {
    dp[u] = Math.max(height1[u], acc);
    for (int v : e[u])
        if (v != parent) {
            int newAcc = Math.max(acc + 1, (height1[v] + 1 == height1[u] ? height2[u] : height1[u]) + 1);
            dfs(v, u, newAcc);
        }
}

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n <= 0) return new ArrayList<>();
    if (n == 1) return Arrays.asList(0);

    this.n = n;
    e = new List[n];
    for (int i = 0; i < n; i++)
        e[i] = new ArrayList<>();
    for (int[] pair : edges) {
        int u = pair[0];
        int v = pair[1];
        e[u].add(v);
        e[v].add(u);
    }

    height1 = new int[n];
    height2 = new int[n];
    dp = new int[n];

    dfs(0, -1);
    dfs(0, -1, 0);

    int min = dp[0];
    for (int i : dp)
        if (i < min) min = i;

    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++)
        if (dp[i] == min) ans.add(i);
    return ans;
}
https://apolloydy.wordpress.com/2015/11/26/minimum-height-trees/
1 Find the longest path in the tree, start from node T1 to node T2; (first bfs find T1 and the second bfs find T2 and remember the parent path. O(n))

2 Find the middle node/nodes for T2 to T1 (Get from parent path, need to take care of odd even cases, O(n))

    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<int> res;
        if (n<=0) {
            return res;
        }
        if (n==1) {
            res.push_back(0);
            return res;
        }
        vector<unordered_set<int>> G(n);
        for (const pair<int,int> &edge: edges) {
            G[edge.first].insert(edge.second);
            G[edge.second].insert(edge.first);
        }
        queue<int> Q;
        for (int i=0; i<n; ++i) {
            // n>0 all tree node must have a degree >= 1;
            if (G[i].size() ==1) {
                Q.push(i);
            }
        }
        int remain = n;
        while (remain>2) {
            int size = Q.size();
            remain -= size;
            for (int j = 0; j<size; ++j) {
                // Q should never be zero for a valid tree input;
                int cur = Q.front();
                Q.pop();
                for (const int &next : G[cur]) {
                    G[next].erase(cur);
                    if (G[next].size() == 1) {
                        Q.push(next);
                    }
                }
            }
        }
        while (!Q.empty()) {
            res.push_back(Q.front());
            Q.pop();
        }
        return res;
    }
附上一开始TLE的版本
思路就是类似于RIP算法,通过相邻的结点更新当前结点距离。
比如说有x ,y 一条边(以x=>y举例,y=>x同样进行更新)
我们可以通过y到各个结点的距离dis[y]来更新,就是说,让x走y这条边,然后到其他结点的距离(比如i)是不是比当前不走y到i的距离小。
于是有:dis[x][i] = dis[i][x] = min(dis[i][x], dis[i][y] + 1)  (无向图对称性:dis[i][y] = dis[y][i] , dis[x][i] = dis[i][x])
最后找最小的即可。
总复杂度:O(n^2)
    def findMinHeightTrees(self, n, edges):
        INF = 0x7ffffffe
        dis = [[INF for j in xrange(n)] for i in xrange(n)]
        for i in xrange(n): dis[i][i] = 0
        g = [[0 for j in xrange(n)] for i in xrange(n)]
        for x,y in edges:
            g[x][y] = g[y][x] = 1
        for x,y in edges:
            dis[x][y] = dis[y][x] = 1
            for i in xrange(n):
                dis[y][i] = dis[i][y] = min(dis[i][y], dis[i][x] + 1)
                dis[x][i] = dis[i][x] = min(dis[i][x], dis[i][y] + 1)
        res  = []
        min_dis = INF
        for i in xrange(n):
            temp = max(dis[i])
            if temp < min_dis:
                res = []
                res.append(i)
                min_dis = temp
            elif temp == min_dis:
                res.append(i)
        return res
http://buttercola.blogspot.com/2016/01/leetcode-minimum-height-trees.html
A brute-force solution is we can construct the graph first, then for each vertex as a root of the tree, we calculate the height, and then compare the height with the minimum height we got so far. Update the minimum if necessary. Since getting the height of a tree takes O(n) time, and we need to traverse each vertex of the graph, the total time complexity is O(n^2). 
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new ArrayList<>();
        if (n <= 0 || edges == null || edges.length == 0) {
            return result;
        }
         
        // Step 1: construct the adjList
        Map<Integer, List<Integer>> adjList = new HashMap<>();
         
        for (int[] edge : edges) {
            // add forward edge
            int from = edge[0];
            int to = edge[1];
             
            if (!adjList.containsKey(from)) {
                List<Integer> neighbors = new ArrayList<>();
                neighbors.add(to);
                adjList.put(from, neighbors);
            } else {
                List<Integer> neighbors = adjList.get(from);
                neighbors.add(to);
                adjList.put(from, neighbors);
            }
             
            // Add the reverse edge
            if (!adjList.containsKey(to)) {
                List<Integer> neighbors = new ArrayList<>();
                neighbors.add(from);
                adjList.put(to, neighbors);
            } else {
                List<Integer> neighbors = adjList.get(to);
                neighbors.add(from);
                adjList.put(to, neighbors);
            }
        }
         
        // Step 2: iterate each vertex as the root and get the height
        boolean[] visited = new boolean[n];
        int minHeight = Integer.MAX_VALUE;
         
        for (int i = 0; i < n; i++) {
            int height = getHeightOfTree(i, adjList, visited);
            if (height < minHeight) {
                result.clear();
                result.add(i);
                minHeight = height;
            } else if (height == minHeight) {
                result.add(i);
            }
        }
         
        return result;
    }
     
    private int getHeightOfTree(int root, Map<Integer, List<Integer>> adjList,
                                boolean[] visited) {
        List<Integer> neighbors = adjList.get(root);
        visited[root] = true;
         
        int maxHeight = 0;
         
        for (Integer neighbor : neighbors) {
            if (!visited[neighbor]) {
                maxHeight = Math.max(maxHeight,
                  getHeightOfTree(neighbor, adjList, visited));
            }
        }
         
        visited[root] = false;
         
        return maxHeight + 1;
    }
Read full article from leetcode Minimum Height Trees - 细语呢喃

No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (652) to-do (599) Review (360) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Segment Tree (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts