在职刷题打卡

12/8 BFS专题
742. Closest Leaf in a Binary Tree, construct graph, BFS on graph
261. Graph Valid Tree, BFS, 1. m = n - 1, 2. all nodes are connected. Remember to create new HashSet for each n, since 0 may be not connected
323. Number of Connected Components in an Undirected Graph, init graph, then bfs

12/11
791. Custom Sort String, HashMap
986. Interval List Intersections, Two pointers, when check overlap, use if(maxStart <= minEnd)
529. Minesweeper, dfs, declare two dimensional dirs array: int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
867. Transpose Matrix, must be res[j][i] = A[i][j]; A[j][i] will be index out of boundary
498. Diagonal Traverse, 实现题, corner case很多, 想清楚几种边界情况要处理
161. One Edit Distance, Two pointers, corner case: when two string are exactly same, return false. check replace and insert cases.
241. Different Ways to Add Parentheses, 特殊的D&C, 可以理解成iterate每个运算符最低优先级的情况，将运算符两端用D&C的方法先收集好，然后再做最后的运算，记住若当前case没找到任何运算符要把单一的数值加入list，否则没有任何结果，需要复习巩固！！！
783. Minimum Distance Between BST Nodes, inorder, global TreeNode prev to track the previous node, then update res in inorder traversal
8. String to Integer (atoi)

12/12
1123. Lowest Common Ancestor of Deepest Leaves, find a node with left substree height is equals to right subtree height
969. Pancake Sorting, 主要是max值和实际index差1，容易越界
567. Permutation in String, Sliding Window, keep a window with s1 length, check whether current window is a valid, use count int array to keep character frequency

12/13
1027. Longest Arithmetic Sequence, 序列型DP, Map<Integer, Integer>[] dp = new HashMap[A.length]; 每一个index有一个hashmap来记录diff和count的pairs, 最后max是jth位的差n的最大值
398. Random Pick Index, reservoir sampling, 水塘抽样, 适用于n个数平均概率取k个值, n未知, 记录count是多少, res initialized as a value, and check if(r.nextInt(count) == 0), update res value
382. Linked List Random Node, reservoir sampling
341. Flatten Nested List Iterator, Queue & DFS, use dfs to flatten, and add all integer into a queue
163. Missing Ranges, corner case好多, increment l and check missing
154. Find Minimum in Rotated Sorted Array, Binary search, the pivot point is minimum, when nuns[m] == nums[e], e --;
80. Remove Duplicates from Sorted Array II, index to track the last position, when current i is valid or index < 2, which means current valid number is less than 2, update index value and move index

12/14
74. Search a 2D Matrix, treat as a sorted array, x = index / n, y index % n;
240. Search a 2D Matrix II, start from the top right corner, then everything on the left is smaller than cur, and everything on the bottom is larger than cur, see from the top right corner, it's like a binary search tree
81. Search in Rotated Sorted Array II, BS, 判断哪半边是valid, 再判断target是否落在那半边, 如果都不是, l或r随便移一位, 确保整个range每次必减小
597. Friend Requests I: Overall Acceptance Rate, 一道可怕的Sql, 要不是在FB的tag里我才不会做
1060. Missing Element in Sorted Array, BS, count the miss between l and m to reduce the range, if go right, remember to update k
1146. Snapshot Array, TreeMap特别fancy的用法, treemap.floorEntry(id).getValue(); floorEntry return the key value pair with the greatest key less than or equal to the given key, return null if no such key exists
771. Jewels and Stones, Set, use set to store all Jewels characters, then loop through S to count
295. Find Median from Data Stream, Two Heap, keep max.size() == min.size() or max.size() = min,size() + 1
298. Binary Tree Longest Consecutive Sequence, DFS, pass current max and the next target value into next level recursion, when not found, reset max = 1;
277. Find the Celebrity, int res = 0, loop start from 1, if knows(res, i), then update res as i, after the loop, res is the possible celebrity, loop n ppl, if ppl != res, then check if ppl don't know res or res knows ppl, then return -1;
209. Minimum Size Subarray Sum, Sliding window/BS, remember while(sum >= s), update res first, then minus nums[l] from sum, l ++; BS是基于prefix sum的, loop l, then find valid r which let the sum between l and r is greater than sum[l] + s
670. Maximum Swap, Similar to next permutation, find first increasing index, find max from first to the end, find first smaller index from start to first, swap those two index

12/15
4. Median of Two Sorted Arrays, BS
32. Longest Valid Parentheses, Stack

12/16
636. Exclusive Time of Functions, Stack
10. Regular Expression Matching, DFS / DP, 太难了。。，得复习！尤其是当*用多次的时候dp情况还是不是很清楚

12/17
452. Minimum Number of Arrows to Burst Balloons, sort by end, add arrow at index = end, if start <= index, the ballon can be bursted, if not, add one arrow at new end
721. Accounts Merge, DFS on graph, build email to email list graph, then dfs on graph, remember to keep another map to store email to name relationship
875. Koko Eating Bananas, 二分答案, Note: Math.ceil(a/b); a或b必须要是double才行，不然在里面就变int了
334. Increasing Triplet Subsequence, record two smallest value, then if find the third one, return true