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

Jun 7  打卡第6天，7道题
407. Trapping Rain Water II, 首先四周一定不能trap，出于短板考虑使用heap每次poll最低的四周进行遍历，注意点在于offer进队列时更新height的值，因为可能可容纳的高度增加有外面的保护；可以直接replace 数组值为-1，就可以avoid visited array；
304. Range Sum Query 2D - Immutable, 画图可以看出直接在二维计算，SumRange(r1, c1, r2, c2) = sum[r2][c2] - sum[r2][c1-1] - sum[r1-1][c2] + sum[r1-1][c1-1];
320. Generalized Abbreviation, Backtracking，使用count来计算当前num;注意点在于index==n后不return，还需要运行sb.setLength(len), 所以需要if-else判断;
307. Range Sum Query - Mutable, 普通解法：每次求sum遍历，O(n) sum；O(1) update; 或者preSum，O(1) sum，O(n) update; Segment Tree, build tree O(n); update O(log n); sum O(log n + k); 最多O(4log n)? 因为log n层，每层最多处理4个node。

第一天开始打卡，今天专门刷了经典的stack和queue的题。打卡3道题：232 implement Queue Using Stacks, 225 Implement Stack Using Queue, 155 Min Stack. implement a stack using queues和implement a queue using stacks可以互相借鉴思路，只要清楚每个data structure是用于什么purpose就容易解了。希望明天继续加油，刷多几道。

Day2 - 7/7   Pass 4 道 链表分类

Day 7: 刷三道islands的题
island perimeter：算小岛周长，遍历每一个点再看看周围死个是否为零
number of islands II：经典的union find的题，再刷一次
shortest bridge：这题很有意思，问任意两小岛的最短距离。可以dfs/bfs取到两个岛的坐标，再算Manhattan distance。

转专业边修网课边刷题中。。
D1
1343. 大小为 K 且平均值大于等于阈值的子数组数目   移动窗口每次-首项+末项即可；
面试题 16.04. 井字游戏   没写出来。。对每一行列和对角线加和即可判断是否获胜；
0～n-1中缺失的数字 比较每一项的索引和值即可；用二分法只有logn；
最长连续递增序列  遍历比较即可

刷了三道3sum 相关题

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

45. Jump Game II
分步走，每一步记录能到达的位置O(n)，注意只有一个元素的情况

56. Merge Intervals
先按起点排序，然后再合并

58. Length of Last Word
注意末尾空格，和只有一个word的情况

七月第三天，3道题。
前两道试了不同的边界条件，感觉自己用[lo, hi] 的方式相对顺手。
第三道，从右上开始，会比较容易。

07/07/2020
1. Island Perimeter 直接数就行
2. Binary Tree Level Order Traversal II 二刷： bfs
3. Clone Graph 用hashmap 存visited node和其copy

今天刷了 3 道题，都是 recursion 的题目，加油冲冲冲