Maximum Product Subarray

Maximum Product Subarray


Code Ganker's post: http://blog.csdn.net/linhuanmars/article/details/39537283?locationNum=1
The local and global variable is very interesting and useful. Key point is that local max should be max(A[i], local[i-1] + A[i]). If A[i] is even larger than previous local max + A[i], then itself should be local max instead.

My answer:

Binary Tree Postorder Traversal

Similar to inorder and preorder traversal. Key point is to keep track of visited right child, by using one node. This is code ganker's idea.

When I started to attack this question, I tried to use a hashset to record all visited nodes, which is less space efficient than code ganker's code.

Below is my code(just for reference):

 public class Solution {  
   public List<Integer> postorderTraversal(TreeNode root) {  
     LinkedList<TreeNode> stack = new LinkedList<TreeNode>();  
     HashSet<TreeNode> visitedNodes = new HashSet<TreeNode>();  
     ArrayList<Integer> res = new ArrayList<Integer>();  
     while(root != null || !stack.isEmpty()){  
         stack.push(root);  
         if(root.left == null || visitedNodes.contains(root.left)){// try go right child  
           if(root.right == null || visitedNodes.contains(root.right)){// if right child visited or null  
             root = stack.pop();  
             res.add(root.val);  
             visitedNodes.add(root);  
             if(stack.isEmpty()) return res;  
             root = stack.pop();  
           }  
           else{  
             root = root.right;  
           }  
         }  
         else{  
           root = root.left;  
         }  
     }  
     return res;  
   }  
 }  

Best Time to Buy and Sell Stock

Key point is to keep track of the smaller "buying price" and update profit when current price can make more money if sold out. DP is usually applied when we need to find out some optimized value, like max or min. profits[i] means max profit by ith day.

 public class Solution {  
   public int maxProfit(int[] prices) {  
     if (prices == null || prices.length <= 1) return 0;  
     int buy_idx = 0;  
     int[] profits = new int[prices.length];  
     profits[0] = 0;  
     profits[1] = Math.max(0, prices[1] - prices[buy_idx]);  
     buy_idx = profits[1]>0?0:1;  
     for(int i = 2; i < prices.length; i ++){  
       profits[i] = profits[i - 1];  
         if (prices[i] < prices[buy_idx]) buy_idx = i;  
         if ((prices[i] - prices[buy_idx]) > profits[i]){  
           profits[i] = prices[i] - prices[buy_idx];  
         }  
     }  
     return profits[prices.length - 1];  
   }  
 }  

code ganker's post about this question: http://blog.csdn.net/linhuanmars/article/details/23162793
His answer is much better, with only O(1) space. And the idea is simpler and more general. Key point he proposes is local optimization and global optimization.

A better and general explanation can be found in the 3rd version of this problem: http://blog.csdn.net/linhuanmars/article/details/23236995

Triangle

At first glance, I thought it is recursion problem, since it is related to or similar with the "Tree" structure. So this time my code is like below:

 public class Solution {  
   public int minimumTotal(List<List<Integer>> triangle) {  
     if (triangle == null) return 0;  
     if (triangle.size() == 1) return triangle.get(0).get(0);  
     ArrayList<Integer> list = new ArrayList<Integer>();  
     WrapInt wi = new WrapInt(Integer.MAX_VALUE);  
     findMinSum(triangle, 0, 0, wi, list);  
     return wi.val;  
   }  
   public void findMinSum(List<List<Integer>> triangle, int level, int idx, WrapInt wi, ArrayList<Integer> list){  
     list.add(triangle.get(level).get(idx));  
     if (list.size() == triangle.size()){  
       int sum = 0;  
       for (int e : list){  
         sum += e;  
       }  
       if (sum < wi.val) wi.val = sum;  
       return;  
     }  
     findMinSum(triangle, level + 1, idx , wi, list);  
     list.remove(list.size() - 1);  
     findMinSum(triangle, level + 1, idx+1, wi, list);  
     list.remove(list.size() - 1);  
   }  
 }  
 class WrapInt{  
   int val;  
   public WrapInt(int v){  
     val = v;  
   }  
 }  

Apparently, this is not very efficient. It is like a brute force answer, with all possible results been computed. Time complexity should be O(2^(n - 1)). NO!! Too much time.

Now we can know that we must waste time in computing redundant path, or duplicate computing. To improve recursion version, DP is usually applied.

Thanks again for code ganker's good job.  Key point is sum[i][j](the "min sum value" at level i, index j) is equal to min(sum[i-1][j-1], sum[i-1][j]) + triangle[i][j]. This is a bottom-to-up idea. For each level, calculation is based on previous level. Overall, each element is traversed once, so time is O(n^2), and using an array can keep space O(n)

Hope I can think of this idea by myself next time.

Single Number

Thanks Wei for suggesting this problem to me. This is a very tricky, but simple question. People may not think of the approach at first glance. Once it came to your mind, then remaining thing become much easier.

For XOR operation, one rule we need to know is: x^y=y^x. Order DOES NOT matter.

Check out my code below:

 public class Solution {  
   public int singleNumber(int[] A) {  
     if(A.length == 0) return 0;  
     int tmpRes = A[0];  
     for(int i = 1; i < A.length; i++){  
       tmpRes ^= A[i]; //x^y = y^x, so x ^ y ^ ~x ^ z ^ ~y = x ^ ~x ^ y ^ ~y ^ z = 0 ^ 0 ^ z = z  
     }  
     return tmpRes;  
   }  
 }  

And also thank Code_Ganker for his alternative solutions. Brilliant! His algorithm:

 public int singleNumber(int[] A) {  
   int[] digits = new int[32];  
   for(int i=0;i<32;i++)  
   {  
     for(int j=0;j<A.length;j++)  
     {  
       digits[i] += (A[j]>>i)&1;// get cumulative sum on each bit  
     }  
   }  
   int res = 0;  
   for(int i=0;i<32;i++)  
   {  
     res += (digits[i]%2)<<i;  
   }  
   return res;  
 }