早上咨詢老師過(guò)后決定還是要去花時(shí)間搞幾個(gè)大項(xiàng)目东跪，沒(méi)項(xiàng)目就只能當(dāng)炮灰了，簡(jiǎn)歷就要悲劇鹰溜，沒(méi)辦法越庇，同時(shí)搞吧。唉奉狈。卤唉。雖然有點(diǎn)失落但同時(shí)也消除了我的迷茫。知道了自己要做什么和怎么做之后仁期，感覺(jué)整個(gè)人的狀態(tài)都是不一樣的桑驱，有一種使命感驅(qū)使我去完成每天的任務(wù)。
先刷幾題冷靜冷靜
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來(lái)做跛蛋，但最優(yōu)解法是用quick select
注意maxHeap comparator的寫(xiě)法
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;
}
});
- Kth Largest Element in an Array
這題跟上一題一樣解法
BFS
- 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
染色問(wèn)題
maintain一個(gè)HashMap<GraphNode, Integer> Integer用來(lái)標(biāo)記分組
通過(guò)BFS找neighbors熬的， 然后分三種情況判斷每個(gè)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: 出現(xiàn)了氣泡，.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)
- Kth Smallest Element in a Sorted Matrix
留明天 今天來(lái)不及了 一會(huì)兒還要跟爸媽視頻 - single num
// N XOR 0 = N
// N XOR N = 0
// the XOR operator is commutative
