LeetCode 337 - House Robber III


LeetCode 198 - House Robber
LeetCode 213 - House Robber II
LeetCode 337 - House Robber III

https://www.hrwhisper.me/leetcode-house-robber-iii/
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
     3
    / \
   2   3
    \   \ 
     3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
     3
    / \
   4   5
  / \   \ 
 1   3   1
Maximum amount of money the thief can rob = 4 + 5 = 9.

题意：给定一颗二叉树，求能获取的权值最大和（相邻的不能同时取）
思路: 树形dp
显然有：
  • rob_root = max(rob_L + rob_R , no_rob_L + no_nob_R + root.val)
  • no_rob_root = rob_L + rob_R

X. DFS + cache
这道题是之前那两道House Robber II和House Robber的拓展，这个小偷又偷出新花样了，沿着二叉树开始偷，碉堡了，题目中给的例子看似好像是要每隔一个偷一次，但实际上不一定只隔一个，比如如下这个例子：
复制代码
        4
       /
      1
     /
    2
   /
  3
复制代码
如果隔一个偷，那么是4+2=6，其实最优解应为4+3=7，隔了两个，所以说纯粹是怎么多怎么来，那么这种问题是很典型的递归问题，我们可以利用回溯法来做，因为当前的计算需要依赖之前的结果，那么我们对于某一个节点，如果其左子节点存在，我们通过递归调用函数，算出不包含左子节点返回的值，同理，如果右子节点存在，算出不包含右子节点返回的值，那么此节点的最大值可能有两种情况，一种是该节点值加上不包含左子节点和右子节点的返回值之和，另一种是左右子节点返回值之和不包含当期节点值，取两者的较大值返回即可，但是这种方法无法通过OJ，超时了，所以我们必须优化这种方法，这种方法重复计算了很多地方，比如要完成一个节点的计算，就得一直找左右子节点计算，我们可以把已经算过的节点用哈希表保存起来，以后递归调用的时候，现在哈希表里找，如果存在直接返回，如果不存在，等计算出来后，保存到哈希表中再返回，这样方便以后再调用
https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem
Step I -- Think naively
At first glance, the problem exhibits the feature of "optimal substructure": if we want to "rob" maximum amount of money from current binary tree (rooted at "root"), we surely hope that we can do the same to its left and right subtrees.
So going along this line, let's define the function rob(root) which will return the maximum amount of money that we can rob for the binary tree rooted at "root"; the key now is to construct the solution to the original problem from solutions to its subproblems, i.e., how to get rob(root)from rob(root.left), rob(root.right), ... etc.
Apparently the analyses above suggest a recursive solution. And for recursion, it's always worthwhile to figure out the following two properties:
  1. Termination condition: when do we know the answer to rob(root) without any calculation? Of course when the tree is empty -- we've got nothing to rob so the amount of money is zero.
  2. Recurrence relation: i.e., how to get rob(root) from rob(root.left), rob(root.right), ... etc. From the point of view of the tree root, there are only two scenarios at the end: "root" is robbed or is not. If it is, due to the constraint that "we cannot rob any two directly-linked houses", the next level of subtrees that are available would be the four "grandchild-subtrees" (root.left.left, root.left.right, root.right.left, root.right.right). However if root is not robbed, the next level of available subtrees would just be the two "child-subtrees" (root.left, root.right). We only need to choose the scenario which yields the larger amount of money.
public int rob(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    int val = 0;
    
    if (root.left != null) {
        val += rob(root.left.left) + rob(root.left.right);
    }
    
    if (root.right != null) {
        val += rob(root.right.left) + rob(root.right.right);
    }
    
    return Math.max(val + root.val, rob(root.left) + rob(root.right));
}
Step II -- Think one step further
In step I, we only considered the aspect of "optimal substructure", but think little about the possibilities of overlapping of the subproblems. For example, to obtain rob(root), we needrob(root.left), rob(root.right), rob(root.left.left), rob(root.left.right), rob(root.right.left), rob(root.right.right); but to get rob(root.left), we also needrob(root.left.left), rob(root.left.right), similarly for rob(root.right). The naive solution above computed these subproblems repeatedly, which resulted in bad time performance. Now if you recall the two conditions for dynamic programming: "optimal substructure" + "overlapping of subproblems", we actually have a DP problem. A naive way to implement DP here is to use a hash map to record the results for visited subtrees.
public int rob(TreeNode root) {
    Map<TreeNode, Integer> map = new HashMap<>();
    return robSub(root, map);
}

private int robSub(TreeNode root, Map<TreeNode, Integer> map) {
    if (root == null) return 0;
    if (map.containsKey(root)) return map.get(root);
    
    int val = 0;
    
    if (root.left != null) {
        val += robSub(root.left.left, map) + robSub(root.left.right, map);
    }
    
    if (root.right != null) {
        val += robSub(root.right.left, map) + robSub(root.right.right, map);
    }
    
    val = Math.max(val + root.val, robSub(root.left, map) + robSub(root.right, map));
    map.put(root, val);
    
    return val;
}
The runtime is sharply reduced to 9ms, at the expense of O(n) space cost (n is the total number of nodes; stack cost for recursion is not counted).

 X. Return multiple values

The idea of the DP solution is for each node, maintain two fields: the max value if rob the root, and the max value without robbing the root. Then we can use a bottom-up DP to avoid the repeated calculations. 
public int rob(TreeNode root) {
    if(root == null)
        return 0;
 
    int[] result = helper(root);
    return Math.max(result[0], result[1]);
}
 
public int[] helper(TreeNode root){
    if(root == null){
        int[] result = {0, 0};
        return result;
    }
 
    int[] result = new int[2];
    int[] left = helper(root.left);
    int[] right = helper (root.right);
 
    // result[0] is when root is selected, result[1] is when not. 
    result[0] = root.val + left[1] + right[1];
    result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
 
    return result;
}
对于每一个节点，都有两种状态，选或者不选。并且当某节点被选择时，其父节点和子节点都只有一种状态，即不能被选；当某节点不被选择时，其父节点和子节点分别有两种状态，选或者不选。因此，需要一个长度为 2 的数据结构，用以分别保存某节点被选和不被选时，其子树中满足要求的权值之和的最大值。在 c++ 中，可以使用 pair<int, int> 来记录，其中 first 记录节点被选择时的最大值，second 记录节点不被选择时的最大值。

由于每一个节点在计算其子树的最大值时，需要使用到左右子树的最大值，因此可以使用后序遍历来达到这个目的。

具体步骤为，后序遍历二叉树，对于每一个节点在获取其左右子树的最大值后，计算该节点被选择和不被选择时整个子树的最大值。对于当前节点，两种状态的最大值分别为

被选择时：最大值为当前节点权值加上左右子树都不被选择时的最大值；
不被选择时：最大值为左孩子被选或者不被选两种状态中的最大值，加上右孩子被选或者不被选两种状态中的最大值。
递归下去，最终在根节点取被选或者不被选的最大值即为结果


这种方法的递归函数返回一个大小为2的一维数组res，其中res[0]表示不包含当前节点值的最大值，res[1]表示包含当前值的最大值，那么我们在遍历某个节点时，首先对其左右子节点调用递归函数，分别得到包含与不包含左子节点值的最大值，和包含于不包含右子节点值的最大值，那么当前节点的res[0]就是左子节点两种情况的较大值加上右子节点两种情况的较大值，res[1]就是不包含左子节点值的最大值加上不包含右子节点值的最大值，和当前节点值之和，返回即可
Step III -- Think one step back
In step I, we defined our problem as rob(root), which will yield the maximum amount of money that can be robbed of the binary tree rooted at "root". This leads to the DP problem summarized in step II.
Now let's take one step back and ask why do we have overlapping subproblems? If you trace all the way back to the beginning, you'll find the answer lies in the way how we have definedrob(root). As I mentioned, for each tree root, there are two scenarios: it is robbed or is not.rob(root) does not distinguish between these two cases, so "information is lost as the recursion goes deeper and deeper", which resulted in repeated subproblems.
If we were able to maintain the information about the two scenarios for each tree root, let's see how it plays out. Redefine rob(root) as a new function which will return an array of two elements, the first element of which denotes the maximum amount of money that can be robbed if "root" is not robbed, while the second element signifies the maximum amount of money robbed if root is robbed.
Let's relate rob(root) to rob(root.left) and rob(root.right), etc. For the 1st element ofrob(root), we only need to sum up the larger elements of rob(root.left) androb(root.right), respectively, since root is not robbed and we are free to rob the left and right subtrees. For the 2nd element of rob(root), however, we only need to add up the 1st elements of rob(root.left) and rob(root.right), respectively, plus the value robbed from "root" itself, since in this case it's guaranteed that we cannot rob the nodes of root.left and root.right.
As you can see, by keeping track of the information of both scenarios, we decoupled the subproblems and the solution essentially boiled down to a greedy one.
https://discuss.leetcode.com/topic/40301/2ms-java-ac-o-n-solution
https://discuss.leetcode.com/topic/39700/c-java-python-explanation
https://discuss.leetcode.com/topic/39659/easy-understanding-solution-with-dfs
public int rob(TreeNode root) {
 int[] res = robSub(root);
    return Math.max(res[0], res[1]);
}

private int[] robSub(TreeNode root) {
    if (root == null) {
     return new int[2];
    }
    
    int[] left = robSub(root.left);
    int[] right = robSub(root.right);
    
    int[] res = new int[2];
    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];
    
    return res;
}
    public int rob(TreeNode root) {
        return dfs(root)[0];
    }
    
    private int[] dfs(TreeNode root) {
        int dp[]={0,0};
        if(root != null){
            int[] dp_L = dfs(root.left);
            int[] dp_R = dfs(root.right);
            dp[1] = dp_L[0] + dp_R[0];
            dp[0] = Math.max(dp[1] ,dp_L[1] + dp_R[1] + root.val);
        }
        return dp;
    }
http://bookshadow.com/weblog/2016/03/13/leetcode-house-robber-iii/
记当前房间为root，如果偷窃当前房间，则其左右孩子left和right均不能偷窃；而其4个孙子节点（ll，lr，rl，rr）不受影响。
因此最大收益为：
maxBenifit = max(rob(left) + rob(right), root.val + rob(ll) + rob(lr) + rob(rl) + rob(rr))

使用字典valMap记录每一个访问过的节点，可以避免重复运算。
def rob(self, root): """ :type root: TreeNode :rtype: int """ valMap = dict() def solve(root, path): if root is None: return 0 if path not in valMap: left, right = root.left, root.right ll = lr = rl = rr = None if left: ll, lr = left.left, left.right if right: rl, rr = right.left, right.right passup = solve(left, path + 'l') + solve(right, path + 'r') grabit = root.val + solve(ll, path + 'll') + solve(lr, path + 'lr') \ + solve(rl, path + 'rl') + solve(rr, path + 'rr') valMap[path] = max(passup, grabit) return valMap[path] return solve(root, '')

 https://leetcode.com/discuss/91597/easy-understanding-solution-with-dfs

http://yaoxin.me/index.php/2016/03/13/337-house-robber-iii/
似乎一个返回值是解决不了问题的。需要2个。一个表示抢劫了当前结点，一个是表示没有抢劫当前结点。
dfs all the nodes of the tree, each node return two number, int[] num, num[0] is the max value while rob this node, num[1] is max value while not rob this value. Current node return value only depend on its children's value.
public int rob(TreeNode root) {
    int[] num = dfs(root);
    return Math.max(num[0], num[1]);
}
private int[] dfs(TreeNode x) {
    if (x == null) return new int[2];
    int[] left = dfs(x.left);
    int[] right = dfs(x.right);
    int[] res = new int[2];
    res[0] = left[1] + right[1] + x.val;
    res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return res;
}
https://leetcode.com/discuss/91652/c-java-python-%26-explanation
    public int rob(TreeNode root) {
        return dfs(root)[0];
    }
    
    private int[] dfs(TreeNode root) {
        int dp[]={0,0};
        if(root != null){
            int[] dp_L = dfs(root.left);
            int[] dp_R = dfs(root.right);
            dp[1] = dp_L[0] + dp_R[0];
            dp[0] = Math.max(dp[1] ,dp_L[1] + dp_R[1] + root.val);
        }
        return dp;
    }
https://leetcode.com/discuss/91601/14ms-java-solution
http://www.cnblogs.com/chess/p/5271039.html
对于树的的前序遍历（根-左-右）；编写代码时，有效代码（处理函数）写在递归左子树之后，递归右子树之前；
中序遍历（左-根-右）用于二叉排序树的顺序输出，编写代码时，有效代码（处理函数）写在递归左右子树之前；
后序遍历（左-右-根），有效代码写在递归左右子树之后；
本题就是采用的后序遍历，对于每一个节点，先处理好其左右子树之后，再考虑本身节点的情况，非常符合实际
    int rob(TreeNode* root) {
        if(root==NULL)
           return 0;
        dfs(root);
        return max(dp1[root],dp2[root]);
    }
    void dfs(TreeNode* node){
        if(node==NULL)
           return;
        dfs(node->left);
        dfs(node->right);//实际干活的代码写在这两个递归之后，表示先处理一个节点的左右子树之后，才考虑本身节点（后序遍历处理手法）
        dp1[node]=dp2[node->left]+dp2[node->right]+node->val;//dp2[NULL]是等于0的，注意，只有key是指针类型才有效，本题满足条件
        dp2[node]=max(max(dp1[node->left]+dp1[node->right],dp2[node->left]+dp2[node->right]),max(dp1[node->left]+dp2[node->right],dp1[node->right]+dp2[node->left]));
    }
private:
      map<TreeNode*,int> dp1;
      map<TreeNode*,int> dp2;

X. return only one value

https://zxi.mytechroad.com/blog/tree/leetcode-337-house-robber-iii/
  int rob(TreeNode* root) {
    int l = 0;
    int r = 0;
    return rob(root, l, r);    
  }
private:
  // return rob(root) and stores rob(root->left/right) in l/r.
  int rob(TreeNode* root, int& l, int& r) {
    if (root == nullptr) return 0;
    int ll = 0;
    int lr = 0;
    int rl = 0;
    int rr = 0;
    l = rob(root->left, ll, lr);
    r = rob(root->right, rl, rr);    
    return max(root->val + ll + lr + rl + rr, l + r);
  }

https://blog.csdn.net/magicbean2/article/details/76875666
    int rob(TreeNode* root) {
        int left = 0, right = 0;
        return rob(root, left, right);
    }
private:
    int rob(TreeNode* root, int &left, int &right) {
        if(!root) {
            return 0;
        }
        int left_left = 0, left_right = 0, right_left = 0, right_right = 0;
        left = rob(root->left, left_left, left_right);      // left_left and left_right will be updated during recursions
        right = rob(root->right, right_left, right_right);  // right_left and right_right will be updated during recursions 
        return max(root->val + left_left + left_right + right_left + right_right, left + right);
    }
https://discuss.leetcode.com/topic/39846/easy-to-understand-java
public int rob(TreeNode root) {
    if (root == null) return 0;
    return Math.max(robInclude(root), robExclude(root));
}

public int robInclude(TreeNode node) {
    if(node == null) return 0;
    return robExclude(node.left) + robExclude(node.right) + node.val;
}

public int robExclude(TreeNode node) {
    if(node == null) return 0;
    return rob(node.left) + rob(node.right);
}

http://siukwan.sinaapp.com/?p=1013

As with general dynamic programming, we're required to think of 3 things.

The DP state information you will keep.
The solution to the base case.
How to go from a smaller solution to a larger solution.

https://www.commonlounge.com/discussion/8573ee40c4cb4673824c867715a5bc7b
Consider a tree in which every node has a positive value written on it. The task is to select several nodes from the tree (you may also select none), so that the sum of values of the nodes you select is maximized, and no two adjacent nodes are selected. The desired solution has complexity O(n).

Dynamic Programming(DP) is a technique to solve problems by breaking them down into overlapping sub-problems which follow the optimal substructure. We all know of various problems using DP like subset sum, knapsack, coin change etc. We can also use DP on trees to solve some specific problems.
We define functions for nodes of the trees, which we calculate recursively based on children of a nodes. One of the states in our DP usually is a node i, denoting that we are solving for the subtree of node i.

A common idea in DP on Trees is to have the sub-problems represent answers for subtrees (+ some state, we'll see what this means in a bit). What can be a base case? Surely, it is the smallest subtree, a node. Let us think about what can be the answer for a node.
But there is also another point in here: Note that all logic for a subtree is derived from whether its parent node is taken / not. None of the other ancestors play a part in the calculation.
Inspired by this let us define our DP "state" to be not just a subtree, but a subtree + a boolean representing whether its parent is taken or not.

Now lets see what happens (we write dp[x][true/false] for indicating answer for node x, and true/false whether its parent is taken or not). Let's start with node d again

dp[d][false] = 1 as you can take d (parent not taken).
dp[d][true] = 0 as you cannot take d.
The answers for e and f are also computed similarly and filled in this incomplete "DP tree:

So, in conclusion, this is our DP:

dp[leaf][ptaken] = vleaf if ptaken else 0
dp[node][true] = sum of dp[c][false] over all children c of node
dp[node][false] = max(vnode + sum over dp[c][true] over children c of node, sum over dp[c][false] over children c of node)


Simple Extension
Now let us think about how this problem could be made harder. A simple extension would be to disallow not only selection of parents, but also parent of parent.

Consider a solution of such a problem. Your DP state must carry information about parents and parents of parents. "Information" in this case would mean whether the node is taken or not. Also note that such information is sufficient, as if you know both of them, nothing else in the tree outside of this sub-tree can influence the answer for the sub-tree. In that case the state would be like dp[v][parent taken][parent-of-parent taken]. The complexity would be proportional to the size of the dp, that is 2*2*n or O(n).

In general suppose no parent within a distance of k can be taken. Then the state would be dp[parent taken][parent-of-parent taken]....[parent-of-parent-of-parent-of.... (k times) taken]. Such an algorithm will be of order O(n*2^k).

But this can be improved. Consider the state dp[v][height of closest parent taken / 0 if no parent is taken]. This takes time O(n*k).

Better Extension
Another extension can be that no two nodes at a distance of at-most 2 can be taken. This is significantly more interesting, because of this:


This cannot be captured by any state that looks like dp[v][any-information-about-parents]. Take a few minutes to see if you can come up with a solution.

Lets consider a part of a tree as shown:


Let our DP state be dp[v][1 = parent taken, 2 = parent of parent taken, 0 = none of them taken]. Suppose we've calculated all of them them for b, c, d, e. We want to calculate dp[a][0], dp[a][1], dp[a][2] .

If we're calculating dp[a][1], we cannot take a, b, c, d, e. So our answer for this case is: dp[a][1] = dp[b][2] + dp[c][2] + dp[d][2] + dp[e][2]
If we're calculating dp[a][2], a's parent of parent is taken. So we can take b, c, d, e, but cannot take a. But note that we can take exactly one of b, c, d, e (Why?). So take the best among them, specifically something like, dp[a][2] = max(dp[b][0] + dp[c][2] + dp[d][2] + dp[e][2], ... (symmetrically for c, d, e, in place of b).
There is an interesting point here. Why did we take dp[c][2]? c's parent of parent is not taken. Well if b is taken, its effect on the calculation of c is the same as if c had its parent of parent taken.


Implementation Details
Let us now think about a few implementation details:

DP of trees is generally implemented using a recursive depth first search (DFS). But sometimes you may also need to explicitly use a stack, if n is high.
States are generally stored in a multidimensional array, which is the reason why we adopted such a convention for writing answers.
In general code looks like:

dfs (v) {    
    for children c calculate dfs(c)
    calculate dp for v using children information
}    
int v[maxn]; // ensure v[i] <= 1e4, or else int won't work for dp
int dp[maxn][2]; // dynamic programming answers
std::vector<int> G[maxn]; // graph for connections
void dfs(int x, int parent) {
    for (int y: G[x]) {
        if (y == parent) continue; 
        dfs(y, x); // dfs all children
    }
    int taking_x = v[x], not_taking_x = 0; // two cases for the values
    for (int y: G[x]) {
        if (y == parent) continue;
        taking_x += dp[y][true]; 
        not_taking_x += dp[y][false]; 
    }
    dp[x][true] = not_taking_x;  // if parent of x is taken, x is not taken
    dp[x][false] = std::max(taking_x, not_taking_x);  //  if parent of x is not taken
}

https://codeforces.com/blog/entry/20935
//functions as defined above
int dp1[N],dp2[N];

//pV is parent of node V
void dfs(int V, int pV){

    //for storing sums of dp1 and max(dp1, dp2) for all children of V
    int sum1=0, sum2=0;

    //traverse over all children
    for(auto v: adj[V]){
    if(v == pV) continue;
    dfs(v, V);
    sum1 += dp2[v];
    sum2 += max(dp1[v], dp2[v]);
    }

    dp1[V] = C[V] + sum1;
    dp2[V] = sum2;
}
at
Labels: , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
    Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks Huffman coding is a lossless data compression algorithm. The idea is to assign ...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Minimum area of a square enclosing given set of points
    Problem solving with programming: Minimum area of a square enclosing given set of points Given a set of coordinates in a two dimensional ...
  • HackerRank: N Puzzle
    HackerRank: N Puzzle N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to ...
  • LeetCode 394 - Decode String
    Follow up:  LeetCode 471 - Encode String with Shortest Length https://leetcode.com/problems/decode-string/ Given an encoded string, retu...
  • Hilbert Curve - Airbnb
    airbnb面试题汇总 Hilbert Curve Hilbert曲线可以无限阶下去，从1阶开始，落在一个矩阵里，让你写个function，三个参数（x,y,阶数），return 这个点（x,y）是在这阶curve里从原点出发的第几步 int hilbertCurve(...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...
  • LeetCode 291 - Word Pattern II
    leetcode 291 Word Pattern II Given a  pattern  and a string  str , find if  str  follows the same pattern. Here  follow  means a full m...