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

打卡  7/1 7/3 7/5 完成6题...蛮少的，争取本周刷完所有的 easy

打卡第三天

今天学了如何做pivot table 的，通过MAX()来选出每列不是NULL的值，如果每列有多个值的话，可以先assign一个row_id，最后GROUP BY 这个id

今天的五题dp

day 2
刷了3道trie的题

208. Implement Trie (Prefix Tree)
讲的如何构建 trie tree。有很多很多应用，比如autocomp， 词语检查等
其实就是每个letter是一个node，然后link上下一个letter
1. 实现link其实就是HashMap，key是letter，value是对应的node。如果不用hashmap，并且能假设只有26个字母，那么用int[26] 来存node也可以。
2. 注意需要mark一下词语的end在哪个node

211. Add and Search Word - Data structure design
这个题是Trie的应用之一
有点不一样的是，词语可以包含"."代表任何字母。那么实现的时候如果遇到 "." 就要遍历当前node的children然后一路search下去

212. Word Search II
也是trie的应用，先build一个trie，再遍历board的字母，发现board的字母跟root的children一样，就从这个位置Backtracking下去
1. 有个方便的事情就是，把完整的词语存在是end的那个node里面，这样就可以直接把这个word加到结果里面
2. Backtracking的时候，记得先把当前在board里的letter mark成非字母，然后search完它的邻居之后再恢复这个字母，否则那种连续的(e.g. "aaaa") 会找回去原来的字母的
3. 注意如果一个词语找到多个路径，那只能加一个在答案里

第二天打卡

07/06
打卡第5天
○ Longest substring that contain at most k zeros
○ Last Moment Before All Ants Fall Out of a Plank
                ○ can't tell difference between the ant
                ○ only the most right ant in the left array, find the most left ant in the right array
                ○ return the ant need most step to fall out of a plank
○ Maximum Sum Partition I
                ○ sort the array then add num with step = 2
                   prove:  min(max1, max2) + min(v1, v2)   >=   min(max1, v1) + min(max2, v2)
○ Ways of Array Partition

7.6 打卡第六天

1. Line Sweep。几乎所有的My Calendar问题都能用这种方法。
2. Binary Index Tree。BIT的写法一定要千锤百炼。
3. DP。提前计算每行的prefixSum.

7/6/20
46        Permutation
DFS, distinct numbers可以用个dictionary存每个数是否已经加入path
79        Word Search
DFS, 上下左右recurssion
1046 Last Stone Weight
Heap

Day 4，刷了5道题，比较水。

打卡 7.6 Day 6
今日放缓节奏，完成binary search 学习卡中 templateIII 的三题以及 July challenge：Plus One