2018-06-23

Q1: leetcode 617
Q2: skyline algo
Q3: vaild parthsis
Q4:meeting room
Q5: house robber 1
Q6: house robber 2
Q7: house robber 3
Q8: array hopper 1
Q9: array hopper 2
Q10: array hopper 3

public int rob(int[] num) {
    int prevNo = 0;
    int prevYes = 0;
    for (int n : num) {
        int temp = prevNo;
        prevNo = Math.max(prevNo, prevYes);
        prevYes = n + temp;
    }
    return Math.max(prevNo, prevYes);
}

///
public class Solution {
public int rob(int[] nums) {
    return Math.max(rob(nums, 0, nums.length-2), rob(nums, 1, nums.length-1));
}

public int rob(int[] nums, int lo, int hi) {
    int preRob = 0, preNotRob = 0, rob = 0, notRob = 0;
    for (int i = lo; i <= hi; i++) {
        rob = preNotRob + nums[i];
        notRob = Math.max(preRob, preNotRob);
        
        preNotRob = notRob;
        preRob = rob;
    }
    return Math.max(rob, notRob);
}
///
class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        //TODO: check input
        List<Wall> input = new ArrayList<>();
        for (int[] one : buildings) {
            Wall leftWall  = new Wall(one[0], one[2], true);
            Wall rightWall = new Wall(one[1], one[2], false);
            input.add(leftWall);
            input.add(rightWall);
        }
        Collections.sort(input, new Comparator<Wall>(Wall a, Wall b){
            if (a.x != b.x) {
                return Integer.compare(a.x, b.x);
            } else {
                if (a.isLeft == b.isLeft) {
                    return Integer.compare(a.height. b.height);
                } else {
                    if (a.isLeft) {
                        return -1;
                    } else {
                        return 1;
                    }
                }
            }
        });
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverse());
        List<int[]> result = new ArrayList<>();
        int heightPre = 0;
        for (Wall aWall : input) {
            if (aWall.isLeft) {
                maxHeap.offer(aWall.height);
            } else {
                maxHeap.remove
            }
            int heightCur = maxHeap.peek().height;
            if (heightCur != heightPre) {
                result.add(new int[]{maxHeap.peek().x, maxHeap.peek().height});
                heightPre = heightCur;
            }
        }
            
        
    }
}

class Wall {
    int x;
    int height;
    boolean isLeft;
    
    public Wall(int x, int h, boolean isLeft){
        this.x = x;
        this.height = h;
        this.isLeft = isLeft;
    }
}
///
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        return helper(t1, t2);
    }
    
    private TreeNode helper(TreeNode n1, TreeNode n2) {
      if (n1 == null && n2 == null) {
        return null;
      } else if (n1 != null && n2 != null) {
        n1.val += n2.val;
        n1.left = helper(n1.left, n2.left);
        n1.right = helper(n1.right, n2.right);
        return n1;
      } else if (n1 != null) {
       return n1;
      } else {
        return n2;
      }
    
   
    }
}