LeetCode 01/06/18

早上咨询老师过后决定还是要去花时间搞几个大项目，没项目就只能当炮灰了，简历就要悲剧，没办法，同时搞吧。唉。。虽然有点失落但同时也消除了我的迷茫。知道了自己要做什么和怎么做之后，感觉整个人的状态都是不一样的，有一种使命感驱使我去完成每天的任务。
先刷几题冷静冷静

K Smallest In Unsorted Array
Find the K smallest numbers in an unsorted integer array A. The returned numbers should be in ascending order.
既可以用minHeap也可以用maxHeap来做，但最优解法是用quick select
注意maxHeap comparator的写法

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
      @Override
      public int compare(Integer o1, Integer o2) {
        if (o1.equals(o2)) {
          return 0;
        }
        return o1 > o2 ? -1 : 1;
      }
    });

215. Kth Largest Element in an Array
     这题跟上一题一样解法

BFS

102. Binary Tree Level Order Traversal
     典型bfs

while(!que.isEmpty()) {
            int size = que.size();
            List<Integer> lv = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = que.poll();
                if (cur.left != null) {
                    que.offer(cur.left);
                }
                if (cur.right != null) {
                    que.offer(cur.right);
                }
                lv.add(cur.val);
            }
            res.add(lv);
        }

***Bipartite
染色问题
maintain一个HashMap<GraphNode, Integer> Integer用来标记分组
通过BFS找neighbors， 然后分三种情况判断每个nei

1. unvisited -> visited.put() queue.offer()  
2. visited & visited.get(cur) != neiGroup -> return false
3. visited & visited.get(cur) = neiGroup -> do nothing, ignore

***check if binary tree is complete
case1: 出现了气泡，.right != null & .left == null
case2: one of the children is null
after detecting the first node that mises one child, then check whether all following nodes expanded to see whether they have any node generated(if any, return false)

378. Kth Smallest Element in a Sorted Matrix
     留明天 今天来不及了 一会儿还要跟爸妈视频
379. single num
     // N XOR 0 = N
     // N XOR N = 0
     // the XOR operator is commutative