Good! Seems like Cracking the coding Interview question 4.4.
chenshiyang
@chenshiyang
Posts made by chenshiyang

RE: Share My DFS JAVA Solution; Beat 97%; easy to understand

RE: Very Easy to Understand One Pass O(n) Solution with No Extra Space
I have two questions.
 "if you take action 3 on day i ==> you can only take the same action on day i1 (you can not sell on day i1 due to cool down)
if you take action 4 on day i ==> you have either taken action 1 or 3 on day i1
". Is there some mistakes?
2.In the code.
" has1_Sell = prices[i] + has1_doNothing;"// here has1_doNothing has been changed before, don't we buffer it before change?  "if you take action 3 on day i ==> you can only take the same action on day i1 (you can not sell on day i1 due to cool down)

2ms Java DP solution, easy understand
public int maxProfit(int[] prices){ if(null == prices  1 >= prices.length) return 0; int last = 0, current = 0, maxProfit = prices[1]  prices[0]; //i means sell in the ith day for(int i = 1; i < prices.length; i ++){ current = last > 0? last + prices[i]  prices[i  1] : prices[i]  prices[i  1]; maxProfit = current > maxProfit? current : maxProfit; last = current; } return maxProfit >= 0? maxProfit : 0;//0 means do not sell }

RE: Easy Understand Straight Forward Java Solution with Explanation
Just think like this: If there are only two houses, and you don't want to rob the first house, then the best choice is to rob the second house. When there are more than 2 houses, it already consider that the first two houses may be both not selected. You can check the second For loop taking i as 2 : dp[2] = Math.max(dp[1], nums[2] + dp[0]).

RE: 0ms Accepted Simple Recursive Java Solution
dp means dynamic programming, you can record the trees you have searched so that you don't need to search it again. I use another class to remember whether each tree is balanced.
public class Solution { class TreeNode2{ private TreeNode2 left; private TreeNode2 right; private int height; private boolean isBalanced; private TreeNode2(int value){ height = value; } private void setHeight(){ if(null == this.left && null == this.right) this.height = 1; else if(null == this.right) this.height = this.left.height + 1; else if(null == this.left) this.height = this.right.height + 1; else this.height = Math.max(this.left.height, this.right.height) + 1; return; } public String toString(){ return this.height + "," + this.isBalanced; } } public boolean isBalanced(TreeNode root){ TreeNode2 croot = copyTree(root); return null == croot ? true : croot.isBalanced; } private TreeNode2 copyTree(TreeNode root){ if(null == root) return null; //copy root TreeNode2 croot = new TreeNode2(1); //copy left subtree. croot.left = copyTree(root.left); //check whether left tree is balanced, if left tree is unbanlanced ,then return directly. if(null != croot.left && ! croot.left.isBalanced){ croot.isBalanced = false; return croot; } //copy right subtree croot.right = copyTree(root.right); if(null != croot.right && ! croot.right.isBalanced){ croot.isBalanced = false; return croot; } int leftHeight = null == croot.left ? 0 : croot.left.height; int rightHeight = null == croot.right ? 0 : croot.right.height; if(Math.abs(leftHeight  rightHeight) > 1){ croot.isBalanced = false; } else{ croot.isBalanced = true; } croot.setHeight(); return croot; }
}

Java, simple and clear, using only int
public class Solution { private static final int MAXDIV10 = Integer.MAX_VALUE / 10; private static final int MINDIV10 = Integer.MIN_VALUE / 10; public int reverse(int x) { int num = 0; while(x != 0){ int digit = x % 10; if(num > MAXDIV10  num < MINDIV10  (num == MAXDIV10 && digit > 8)  (num == MINDIV10 && digit < 8)) return 0; num = num * 10 + digit; x /= 10; } return num; }
}

RE: Simple Java iterative using two queue, 3ms
Sorry, I thought breadthFirstSearch is not a good method name because I thought I wasn't using breadth first search here, so I change it to symmetric. But I forgot to change all the method name.