7月缺米的来刷题/Mock interview活动

今天做了House Robber I，用了两种不同的思路，对于top-down的DP还需要多理解

Day3，三道题。两个LC的每日一题 + 重刷天际线。

1. 天际线真的太坑爹了。感觉自己完全想不到。扫描线法。一个扫描集合 + pq维护当前扫描的过的最高值。左端点入堆，右端点出堆。嗷！！！！

刷题第二天！做了四题，其中3 sum closest， 4 sum， Remove duplicates为新题。这几道都是Two pointers的题
1. 3 sum closest: 先sort input，在用双指针做，跟3 sum唯一的不同是要keep track of a difference variable，记录sum和target的diff。然后去diff最小的解。O(n^2)
2. 4 sum：到了four sum，或者更general的k sum，即可先写一个two sum函数，然后用dfs的方法递归reduce到two sum。O(n^{k - 1})  
3.Remove duplicates from sorted array II: 同向双指针，需要一个count variable记录每个数出现的次数。
4. Binary Tree order level traversal II：试了两种方法，用deque或者直接用vector in C++/list in python做。结论是用deque比较快，以后这么写。

7/1 打卡第1天， 刷了3道题

31. Next Permutation
从后往前，先找第一个出现nums[i]<nums[i+1], 记住这个位置p，然后从这之后的数找出比它小并最接近的数，对调，

38. Count and Say
recursive

48. Rotate Image
从外圈到里， 相邻边转换，记得保存中间值

7/2 打卡第二天 做了五道题， 三道之前做过的，tree traversal, topological sort, 两道trie 和 hash的， 明天继续trie. 继续复习！

七月第二天，三道题。
今天继续binary search，有试两种方法，[lo, hi] 和 [lo, hi)
还在寻找哪样的写法自己更加顺手，明天继续。

Day 2打卡
107. Binary Tree Level Order Traversal II
今日daily challenge，复习了bfs。自己写的时候下意识写了dfs，但实际应使用queue实现bfs算法，当作复习了。
102. Binary Tree Level Order Traversal
前一题的正序输出版本，这一次用bfs+queue实现了
832. Flipping an Image
随机到的Easy，就是reverse a list。

20200701:
3: 0289, 0384, 0523, 0763, 0978, 1057, 1405
4: 0769
5:

0702 Day2 打卡三题

Robot Room Cleaner，解法为backtracking，在每个位置尝试往上下左右四个方向走，但是需要注意记录机器人的位置和方向，因为只能通过提供的api来控制机器人的位置和方向；
24 Game，同为backtracking，尝试所有数字组合和顺序以及所有计算方式，先将所有4个数字放入一个Bag（可以用linkedlist实现），每次取出两个数，尝试所有计算以及顺序，将结果放回bag，重复直至bag中只有一个数，比较其是否等于24（因为计算精度原因，只要是与24的距离小于一个小数即可）
Binary Tree Level Order Traversal II，BFS，将每层的数字插入result前面

菜鸡七月第三天

今天挑了几道简单的
1. range sum BST: 用的recursion，如果node value < L, 根据BST就看node.right的recursive function，如果node.val > R, 就看node.left
    如果value 在中间的话，就return node.val + rangeSum(node.left, L, R) + rangeSum(nodee.right, L, R)
2. Lowest Common Ancestor of a BST: 找两个node的common ancestor，main idea 是如果两个node的value都小于当前value，就说明
    都在current node左边，如果两个node.val 都大于当前value，就在右边找，如果两个node在两边的话，就说明current node是lowest common
    ancestor
3. minimum absolute difference in BST: 找parent和child之间的最小差，可以用一个prev node来keep track of parent node, 先在node.left上用
    recursion，如果prev不是null 的话就update minimum difference，然后把prev设成当前node，再看node.right
4. validate BST: 这个用dfs写的，用in order traversal, 看是不是increasing sequence, 可以用一个previous node 来存之前的值，如果是validate BST
    的话previous < current, 再把previous设成current
5. binary tree zigzag level order traversal: 这个和level order traversal很像，只不过用一个flag来记当前层要不要reverse，如果需要reverse就用
    level.add(0, node.val)来从后向前加，不需要reverse就正常traverse，每次记得把reverse设成 !reverse

明天继续，重新做人