2018-06-25

Q1: swipline calculate area
Q2: move negative to another side
Q3: shuffle 1 2,3
Q4: 蓄水池随机求1/n
Q5: 反转k的链表
Q6: 4 integer sum to target
Q7: flat linkedlist with children
Q8: merge stone
Q9: inorder BST
Q10: max arr[j] + arr[i] + j - i

Q:
Q:
public Node flat(Node root) {
  //TODO:
  Queue<Node> queue = new ArrayDeque<>();
  //Node tmp = root;
  queue.offer(root);
return add(root, queue);
    
}

private Node add(Node root, Queue<Node> queue) {
 if (queue.isEmpty()) {
    return null;
  }
        Node root = queue.pollFirst();
        Node tmpRoot = root;
        while (root.next != null) {
            if (root.child != null) {
              queue.offer(root.child);
              root = root.next;
            }
          }
          if (root.child != null) {
            queue.offer(root.child);
          }
         }
         root.next = add(queue);
         return tmpRoot;
    
  }
}


Q:

Q:
public int find(int n) {
  IntWraper result = new IntWraper();
  dfs(n, 0, 1, result);
  return result.val;
}

private void dfs(int remaining, int level, int start, intWraper result) {
  if (level == 4 && remaining == 0) {
    result.val++;
    return;
  }
  for (int i = start; i < remaining; i++) {
    dfs(remaining - i, level + 1, i, result);
  }
}
Q3:


Q5:
pu


Q4:
class Solution {
    public List<int[]> getArea(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>(){
        //Collections.sort(input, new Comparator<Wall>(Wall a, Wall b){
            @Override
            public int compare(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(b.height, a.height);
                } 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.reverseOrder()); //reverseOrder()
        int result = 0;
        int heightPre = 0;
        int preX = input.get(0).x;
        for (Wall aWall : input) {
            if (aWall.isLeft) {
                maxHeap.offer(aWall.height);
            } else {
                maxHeap.remove(aWall.height);
            }
            int heightCur = maxHeap.isEmpty() ? 0 : maxHeap.peek(); //why isEmpty()?
            if (heightCur != heightPre) {
                result += heightPre * (aWall.x - preX);
                heightPre = heightCur;
                preX = aWall.x;
            }
        }
        System.out.print(result);
            return null;
        
    }
}

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;
    }
}


Q:
public class RerangeNegPos {
    public int[] rerange(int[] input) {
        int n = input.length;
        int i = 0, j = 0;

        while(j < n) {
            if (input[j] > 0 ) {
                if (i != j) {
                    swap(input, i++, j++);
                } else {
                    i++;
                    j++;
                }

            } else {
                j++;
            }
        }
        return input;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j]= temp;
        return;
    }

    public static void main(String[] args) {
        RerangeNegPos test = new RerangeNegPos();
        int[] a = test.rerange(new int[]{-12, 11, -13, -5, 6, -7, 5, -3, -6});
        System.out.print(a);
    }

}



Q4:
//Q4
public List<List<Integer>> shuffle(int n) {
  if(n == 0) {
    return null;
  }
  List<List<Integer>> results = new ArrayList<>();
  int[] onePath = new int[n * 2];
  dfs(0, used, results, onePath);
  return results;
}

private void dfs(int level, Set<Integer> used,List<List<rInteger>> results, int[] onePath){
  if (level == 2 * n) {
    results.add(Arrays.asList(onePath));
    return;
  }
  if (onePath[level] != 0 ) {
    for (int i = 1; i <= n; i++) {
      if (!used.contains(i) && level + i  + 1 < 2 * n) {
        used.add(i);
        onePath[level] = i;
        onePath[level + i + 1] = i;
        dfs(level + 1, used, results, onePath);
        onePath[level] = 0;
        onePath[level + i + 1] = 0;
        used.remove(i);
      }
    }
  } else {
    dfs(leevel + 1, used, results, onePath);
  } 
  
}



Q5//
public class ReverseK {

    public ListNode reverseK(ListNode root, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = root;
        ListNode pre = dummy;
        ListNode nextN = dummy;
        int counter = 1;

        while (root != null) {
            if (counter != k) {
                root = root.next;
                counter++;
            } else {
                nextN = root.next;
                root.next = null;
                ListNode tmpHead = pre.next;
                pre.next = reverse(tmpHead);
                pre = tmpHead;
                System.out.println(pre.val);
                pre.next = nextN;
                counter = 1;
                root = nextN;
            }
        }

        return dummy.next;

    }

    private ListNode reverse(ListNode root) {
        if (root == null) {
            return  null;
        }
        ListNode pre = null;
        ListNode nextN;
        while (root.next != null) {
            nextN = root.next;
            root.next = pre;
            pre = root;
            root = nextN;
        }
        //
        root.next = pre;
        return root;
    }
    public  static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        ListNode n7 = new ListNode(7);
        ListNode n8 = new ListNode(8);
        ListNode n9 = new ListNode(9);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n9;

        ReverseK test = new ReverseK();
        ListNode cur = test.reverseK(n1, 3);

        while (cur != null) {
            System.out.print(cur.val);
            cur = cur.next;
        }


    }
}

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}


//

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>(){
        //Collections.sort(input, new Comparator<Wall>(Wall a, Wall b){
            @Override
            public int compare(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(b.height, a.height);
                } 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.reverseOrder()); //reverseOrder()
        List<int[]> result = new ArrayList<>();
        int heightPre = 0;
        for (Wall aWall : input) {
            if (aWall.isLeft) {
                maxHeap.offer(aWall.height);
            } else {
                maxHeap.remove(aWall.height);
            }
            int heightCur = maxHeap.isEmpty() ? 0 : maxHeap.peek(); //why isEmpty()?
            if (heightCur != heightPre) {
                result.add(new int[]{aWall.x, heightCur});
                heightPre = heightCur;
            }
        }
            return result;
        
    }
}

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;
    }
}


//Q:
public class BSTSplit {
    public TreeNode[]split(TreeNode root, int target) {

        if (root == null) {
            return null;
        }
       return helper(root, new TreeNode[]{null, null}, target);

    }

    private TreeNode[] helper(TreeNode cur, TreeNode[] result, int target){
        if (cur == null) {
            return new TreeNode[]{null, null};
        }

        if (cur.val > target) {

            cur.left = helper(cur.left, result, target)[1];

            cur.right = helper(cur.right, result, target)[1];
            result[1] = cur;
        } else {
            cur.left = helper(cur.left, result, target)[0];
            cur.right = helper(cur.right, result,target)[0];
            result[0] = cur;
        }
        return result;
    }


Q:
public Node flat(Node root) {
  //TODO:
  Queue<Node> queue = new ArrayDeque<>();
  //Node tmp = root;
  queue.offer(root);
return add(root, queue);
    
}

private Node add(Node root, Queue<Node> queue) {
 if (queue.isEmpty()) {
    return null;
  }
        Node root = queue.pollFirst();
        Node tmpRoot = root;
        while (root.next != null) {
            if (root.child != null) {
              queue.offer(root.child);
              root = root.next;
            }
          }
          if (root.child != null) {
            queue.offer(root.child);
          }
         }
         root.next = add(queue);
         return tmpRoot;
    
  }
}


Q:

Q:
public int find(int n) {
  IntWraper result = new IntWraper();
  dfs(n, 0, 1, result);
  return result.val;
}

private void dfs(int remaining, int level, int start, intWraper result) {
  if (level == 4 && remaining == 0) {
    result.val++;
    return;
  }
  for (int i = start; i < remaining; i++) {
    dfs(remaining - i, level + 1, i, result);
  }
}
Q3:


Q5:
pu


Q4:
class Solution {
    public List<int[]> getArea(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>(){
        //Collections.sort(input, new Comparator<Wall>(Wall a, Wall b){
            @Override
            public int compare(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(b.height, a.height);
                } 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.reverseOrder()); //reverseOrder()
        int result = 0;
        int heightPre = 0;
        int preX = input.get(0).x;
        for (Wall aWall : input) {
            if (aWall.isLeft) {
                maxHeap.offer(aWall.height);
            } else {
                maxHeap.remove(aWall.height);
            }
            int heightCur = maxHeap.isEmpty() ? 0 : maxHeap.peek(); //why isEmpty()?
            if (heightCur != heightPre) {
                result += heightPre * (aWall.x - preX);
                heightPre = heightCur;
                preX = aWall.x;
            }
        }
        System.out.print(result);
            return null;
        
    }
}

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;
    }
}


Q:
public class RerangeNegPos {
    public int[] rerange(int[] input) {
        int n = input.length;
        int i = 0, j = 0;

        while(j < n) {
            if (input[j] > 0 ) {
                if (i != j) {
                    swap(input, i++, j++);
                } else {
                    i++;
                    j++;
                }

            } else {
                j++;
            }
        }
        return input;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j]= temp;
        return;
    }

    public static void main(String[] args) {
        RerangeNegPos test = new RerangeNegPos();
        int[] a = test.rerange(new int[]{-12, 11, -13, -5, 6, -7, 5, -3, -6});
        System.out.print(a);
    }

}



Q4:
//Q4
public List<List<Integer>> shuffle(int n) {
  if(n == 0) {
    return null;
  }
  List<List<Integer>> results = new ArrayList<>();
  int[] onePath = new int[n * 2];
  dfs(0, used, results, onePath);
  return results;
}

private void dfs(int level, Set<Integer> used,List<List<rInteger>> results, int[] onePath){
  if (level == 2 * n) {
    results.add(Arrays.asList(onePath));
    return;
  }
  if (onePath[level] != 0 ) {
    for (int i = 1; i <= n; i++) {
      if (!used.contains(i) && level + i  + 1 < 2 * n) {
        used.add(i);
        onePath[level] = i;
        onePath[level + i + 1] = i;
        dfs(level + 1, used, results, onePath);
        onePath[level] = 0;
        onePath[level + i + 1] = 0;
        used.remove(i);
      }
    }
  } else {
    dfs(leevel + 1, used, results, onePath);
  } 
  
}



Q5//
public class ReverseK {

    public ListNode reverseK(ListNode root, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = root;
        ListNode pre = dummy;
        ListNode nextN = dummy;
        int counter = 1;

        while (root != null) {
            if (counter != k) {
                root = root.next;
                counter++;
            } else {
                nextN = root.next;
                root.next = null;
                ListNode tmpHead = pre.next;
                pre.next = reverse(tmpHead);
                pre = tmpHead;
                System.out.println(pre.val);
                pre.next = nextN;
                counter = 1;
                root = nextN;
            }
        }

        return dummy.next;

    }

    private ListNode reverse(ListNode root) {
        if (root == null) {
            return  null;
        }
        ListNode pre = null;
        ListNode nextN;
        while (root.next != null) {
            nextN = root.next;
            root.next = pre;
            pre = root;
            root = nextN;
        }
        //
        root.next = pre;
        return root;
    }
    public  static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        ListNode n7 = new ListNode(7);
        ListNode n8 = new ListNode(8);
        ListNode n9 = new ListNode(9);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n9;

        ReverseK test = new ReverseK();
        ListNode cur = test.reverseK(n1, 3);

        while (cur != null) {
            System.out.print(cur.val);
            cur = cur.next;
        }


    }
}

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}


//

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>(){
        //Collections.sort(input, new Comparator<Wall>(Wall a, Wall b){
            @Override
            public int compare(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(b.height, a.height);
                } 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.reverseOrder()); //reverseOrder()
        List<int[]> result = new ArrayList<>();
        int heightPre = 0;
        for (Wall aWall : input) {
            if (aWall.isLeft) {
                maxHeap.offer(aWall.height);
            } else {
                maxHeap.remove(aWall.height);
            }
            int heightCur = maxHeap.isEmpty() ? 0 : maxHeap.peek(); //why isEmpty()?
            if (heightCur != heightPre) {
                result.add(new int[]{aWall.x, heightCur});
                heightPre = heightCur;
            }
        }
            return result;
        
    }
}

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;
    }
}


//Q:
public class BSTSplit {
    public TreeNode[]split(TreeNode root, int target) {

        if (root == null) {
            return null;
        }
       return helper(root, new TreeNode[]{null, null}, target);

    }

    private TreeNode[] helper(TreeNode cur, TreeNode[] result, int target){
        if (cur == null) {
            return new TreeNode[]{null, null};
        }

        if (cur.val > target) {

            cur.left = helper(cur.left, result, target)[1];

            cur.right = helper(cur.right, result, target)[1];
            result[1] = cur;
        } else {
            cur.left = helper(cur.left, result, target)[0];
            cur.right = helper(cur.right, result,target)[0];
            result[0] = cur;
        }
        return result;
    }


//Q:
public Node flat(Node root) {
  //TODO:
  Queue<Node> queue = new ArrayDeque<>();
  //Node tmp = root;
  queue.offer(root);
return add(root, queue);
    
}

private Node add(Node root, Queue<Node> queue) {
 if (queue.isEmpty()) {
    return null;
  }
        Node root = queue.pollFirst();
        Node tmpRoot = root;
        while (root.next != null) {
            if (root.child != null) {
              queue.offer(root.child);
              root = root.next;
            }
          }
          if (root.child != null) {
            queue.offer(root.child);
          }
         }
         root.next = add(queue);
         return tmpRoot;
    
  }
}


Q:

Q:
public int find(int n) {
  IntWraper result = new IntWraper();
  dfs(n, 0, 1, result);
  return result.val;
}

private void dfs(int remaining, int level, int start, intWraper result) {
  if (level == 4 && remaining == 0) {
    result.val++;
    return;
  }
  for (int i = start; i < remaining; i++) {
    dfs(remaining - i, level + 1, i, result);
  }
}
Q3:


Q5:
pu


Q4:
class Solution {
    public List<int[]> getArea(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>(){
        //Collections.sort(input, new Comparator<Wall>(Wall a, Wall b){
            @Override
            public int compare(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(b.height, a.height);
                } 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.reverseOrder()); //reverseOrder()
        int result = 0;
        int heightPre = 0;
        int preX = input.get(0).x;
        for (Wall aWall : input) {
            if (aWall.isLeft) {
                maxHeap.offer(aWall.height);
            } else {
                maxHeap.remove(aWall.height);
            }
            int heightCur = maxHeap.isEmpty() ? 0 : maxHeap.peek(); //why isEmpty()?
            if (heightCur != heightPre) {
                result += heightPre * (aWall.x - preX);
                heightPre = heightCur;
                preX = aWall.x;
            }
        }
        System.out.print(result);
            return null;
        
    }
}

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;
    }
}


Q:
public class RerangeNegPos {
    public int[] rerange(int[] input) {
        int n = input.length;
        int i = 0, j = 0;

        while(j < n) {
            if (input[j] > 0 ) {
                if (i != j) {
                    swap(input, i++, j++);
                } else {
                    i++;
                    j++;
                }

            } else {
                j++;
            }
        }
        return input;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j]= temp;
        return;
    }

    public static void main(String[] args) {
        RerangeNegPos test = new RerangeNegPos();
        int[] a = test.rerange(new int[]{-12, 11, -13, -5, 6, -7, 5, -3, -6});
        System.out.print(a);
    }

}



Q4:
//Q4
public List<List<Integer>> shuffle(int n) {
  if(n == 0) {
    return null;
  }
  List<List<Integer>> results = new ArrayList<>();
  int[] onePath = new int[n * 2];
  dfs(0, used, results, onePath);
  return results;
}

private void dfs(int level, Set<Integer> used,List<List<rInteger>> results, int[] onePath){
  if (level == 2 * n) {
    results.add(Arrays.asList(onePath));
    return;
  }
  if (onePath[level] != 0 ) {
    for (int i = 1; i <= n; i++) {
      if (!used.contains(i) && level + i  + 1 < 2 * n) {
        used.add(i);
        onePath[level] = i;
        onePath[level + i + 1] = i;
        dfs(level + 1, used, results, onePath);
        onePath[level] = 0;
        onePath[level + i + 1] = 0;
        used.remove(i);
      }
    }
  } else {
    dfs(leevel + 1, used, results, onePath);
  } 
  
}



Q5//
public class ReverseK {

    public ListNode reverseK(ListNode root, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = root;
        ListNode pre = dummy;
        ListNode nextN = dummy;
        int counter = 1;

        while (root != null) {
            if (counter != k) {
                root = root.next;
                counter++;
            } else {
                nextN = root.next;
                root.next = null;
                ListNode tmpHead = pre.next;
                pre.next = reverse(tmpHead);
                pre = tmpHead;
                System.out.println(pre.val);
                pre.next = nextN;
                counter = 1;
                root = nextN;
            }
        }

        return dummy.next;

    }

    private ListNode reverse(ListNode root) {
        if (root == null) {
            return  null;
        }
        ListNode pre = null;
        ListNode nextN;
        while (root.next != null) {
            nextN = root.next;
            root.next = pre;
            pre = root;
            root = nextN;
        }
        //
        root.next = pre;
        return root;
    }
    public  static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        ListNode n7 = new ListNode(7);
        ListNode n8 = new ListNode(8);
        ListNode n9 = new ListNode(9);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n9;

        ReverseK test = new ReverseK();
        ListNode cur = test.reverseK(n1, 3);

        while (cur != null) {
            System.out.print(cur.val);
            cur = cur.next;
        }


    }
}

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}


//

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>(){
        //Collections.sort(input, new Comparator<Wall>(Wall a, Wall b){
            @Override
            public int compare(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(b.height, a.height);
                } 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.reverseOrder()); //reverseOrder()
        List<int[]> result = new ArrayList<>();
        int heightPre = 0;
        for (Wall aWall : input) {
            if (aWall.isLeft) {
                maxHeap.offer(aWall.height);
            } else {
                maxHeap.remove(aWall.height);
            }
            int heightCur = maxHeap.isEmpty() ? 0 : maxHeap.peek(); //why isEmpty()?
            if (heightCur != heightPre) {
                result.add(new int[]{aWall.x, heightCur});
                heightPre = heightCur;
            }
        }
            return result;
        
    }
}

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;
    }
}


//Q:
public class BSTSplit {
    public TreeNode[]split(TreeNode root, int target) {

        if (root == null) {
            return null;
        }
       return helper(root, new TreeNode[]{null, null}, target);

    }

    private TreeNode[] helper(TreeNode cur, TreeNode[] result, int target){
        if (cur == null) {
            return new TreeNode[]{null, null};
        }

        if (cur.val > target) {

            cur.left = helper(cur.left, result, target)[1];

            cur.right = helper(cur.right, result, target)[1];
            result[1] = cur;
        } else {
            cur.left = helper(cur.left, result, target)[0];
            cur.right = helper(cur.right, result,target)[0];
            result[0] = cur;
        }
        return result;
    }

//Q
public int cal(int[] arr) {
  int maxI = A[0];
int result = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    int curJ = A[j] + j;
    maxI = Math.max(maxI, A[i] - i);
    result = Math.max(curJ + maxI);
  }
  return result;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,558评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,002评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,036评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,024评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,144评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,255评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,295评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,068评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,478评论 1赞 305
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,789评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,965评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,649评论 4赞 336
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,267评论 3赞 318
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,982评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,223评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,800评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,847评论 2赞 351

推荐阅读更多精彩内容

  • 2018-06-25
    九九乘法表 感谢您在白忙之中能抽出时间; 作为一个基础的程序员,通常会用到一些简单的逻辑,比如下面的九九乘法表.这...
    浅唱yjc阅读 120评论 0赞 0
  • Authentic materials
    NINE ELEMENTS OF AUTHENTIC LEARNING: 1.Provide authentic ...
    静_静_阅读 1,339评论 0赞 1
  • 笔试刷题-百度2018-06-25
    题目如下： 思路如下： 题目要求在当前方格只能往右边、下边这任意选择两个方向到达下一个方格若当前方格被阻挡，那么其...
    Dodo159753阅读 169评论 0赞 0
  • 2018-03-07
    梦儿是最瞒不过的呵， 清清楚楚的， 诚诚实实的， 告诉了 你自己灵魂里的密意和隐忧。
    范范er阅读 219评论 0赞 0