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

20200728:
3: 0015, 0016, 0033, 0034, 0036, 0048, 0049
4:
5:

gogogo菜啊最近

7月31日 打卡15天 训练4 + 1道题 == 5 道题 7月最后一天求多一点米啦！

今天着重练习并分析了LCA的前四道题，体会了不同的LCA变种的联系和区别；

基础款LCA
-给到node都在Tree里面
-通过非隶属和隶属两种cases的分析
-基本的recursion就能解决

进阶款LCAII
-node可能不再Tree里面
-root node不可知
-需要用到Height这个int variable
-然后消弭掉两者的gap
-然后在统一水平位置向上找parent直到找到LCA为止，如果任何一个为null，返回null;

加强款LCAIII
-与基础款不同的是node可能不再Tree里面，但是给出了root
-Solution1: O(N)
traverse 两个targetNode是不是都在里面然后在用传统LCA
（时间复杂度过高了，舍弃）
-Solution2: O(logN)
先默认两个target Nodes都在Tree里面，去判断以等于a的返回值作为root，是否找到以b作为两个targetNode的LCA；和再判断以等于b的返回值作为root，是否找到以a作为两个targetNode的LCA；最后得出结论返回result 或者null

再次升级版LCAIV
-node是以List形式给出，需要借用一个hashSet
-更换base case的条件：
if (root == null || set.contains(root)) {
        return root;
}
-剩下都相同；

5. find Kth smallest element in the sorted matrix;
**********
if needed to override equals
must override hashCode;
because if two elements equal then its hashcode must be the same
but if two elements hashcode are the same but the two-element could not be equal
**********
-use a map<Cell, Integer> with a minHeap to put the first k elements into it and its two neighbors
-then maintained the map and minHeap dynamically
-finally return the minHeap.peekFirst()

今天写了12道题，效率不错，都是一次就过，可能是今天运气比较好碰到的都是easy和medium的题吧

主要是位运算，DP，linkedlist，找循环，比较杂

Day 21

70. Climbing Stairs, dp
1140. Stone Game II, backtracking + mem
432. All O`one Data Structure, double linked list + hash map 双链表写起来还是挺容易出错的 因为逻辑复杂整体写出来有挺多的小bug 我觉得这道题是一个不错的锻炼在逻辑复杂的情况下如何合理设计oo 拆分模块 减少单个函数的复杂度以减少bug

20200729:
3: 0054, 0055, 0061, 0062, 0069, 0071, 0075
4:
5:

7.31 打卡， 这个月除了一天没有打卡，其它30天应该都打卡了

1. Logger Rate Limiter. Queue + Set 解决
2. Odd Even Jump。TreeMap解决
3. Climbing Stairs. DP,  可以从O(n) -> O(1)

7/31

8月day1 没看到别的帖子 三道dp

8.1打卡, leetcode 面试题08.08，632，304，783