缺大米的请参加这个刷题/Mock interview活动

20200610:
3: 0320
4: 0306, 0351
5:

day 2 打卡4道题

#第四次打卡 今天刷了6道题，其中有两道是hard，最naive的方法也能做出来，不过离最优解还有比较大的差距。不过看discussion的时候看到标题是用BFS，我就灵光乍现，在没有看具体答案的情况下自己写出了最优解，也算是一种进步了吧嘻嘻

2020年6月10日，第九天发帖，今天刷了9道题：

以下题目全部来自LC pick one：

1216. Valid Palindrome III。这道题目比较顺利地定义了状态（定义为某个substring去掉多少个字符就可以变成回文），同时也写出了正确的状态转移函数，虽然标记为hard但是还是比较轻松滴拿下了。
517. Super Washing Machines。这道题目的状态的定义我感觉很是奇怪，也确实没有往这个方向去思考，而是把所有的精力全都拿来分析自己穷举出来的test case了。这个题目很像在计算”最大断面流量“。
760. Find Anagram Mappings。为了安慰自己做的简单题。典型的用hashtable空间换时间将O(N^2) 变为O(N)的问题。
524. Longest Word in Dictionary through Deleting。这个题目感觉就是在挨个找subsequence然后选那个最长的，这就是重复多次的双指针了。
502. IPO。这个题目一上来就理解错了，花了好长时间都不知道它想要求的结果是什么，结果发现自己理解错了profit这个数组的含义。然后自己写了一个recursive的算法，结果就TLE了。这道题目的答案我不是很喜欢：分两种情况讨论的感觉完全是把一个maxheap和一个recursion的代码拼接在了一起，为了过test case写出来的。于是参考了另一个高票的双heap的做法，这方法相当惊艳啊，给每一个project两步的缓冲：一步缓冲解决了预算与成本的比较问题，另一步则选出了利润的最大值。
796. Rotate String。也是为了安慰自己做的简单题，将两个A字符串拼接在一起找里面有没有能matchB字符串的substring就可以了。AC后又用这个题目复习了一遍KMP。
406. Queue Reconstruction by Height。这个题目乍一看是完全没有思路的。点开一个hint突然间意识到：如果优先安排矮的人，其它所有未被安排的人都比他高，于是这个矮人前面的人数就锁定了他的位置，接下来再安排更高的人。这是个贪心算法。自己实现了这个算法。看答案后还有了另一个思路：如果优先安排高的人，那么矮的人如果有相同的位置可以插队同时不影响高的人的位置要求，此时可以用linkedlist实现O(1)插入元素，这个方法将时间复杂度降为排序所需的O(NlogN)。有的答案提到了binary indexed tree，说实话真的感觉没太大必要去学习它了。
931. Minimum Falling Path Sum。这个DP的状态转移也非常简单，同时将二维的DP数组降维到两个一维DP数组相互迭代。
761. Special Binary String。这个题在拿到手的时候思路是空白的，连Brute force都不知道该如何下手的那种。点开hint之后表示它说的话并看不懂，但是爬山的模型图倒是记在脑子里了。看答案之后惊奇地发现这个题目和那一大堆括号类的题目有相似性（”1100“可以等效于”(())“），同时也明白了为啥这个题目被tag了recursion。这种类似的题目得多练习了。

总结一下：

1.在确认一道题目是DP之后先把state定义下来，test case可以之后讨论state transition的时候再研究。
2.一般情况下，遍历一个有连续属性的数组来找边界的问题都是要用binary search来代替遍历的；如果有大量数据需要这样做的话要用heap；如果给定了要找第k个最值要用quick select。
3.在一道题目连DP都不适用的情况下，往贪心的思路上去想一想，或许会有惊喜。

Action item：
1. 总结括号类或者类似爬上爬下类的题目；

06/10 Day 6 : 六道题

刷题第二天，今天做的是关于dp的题目。

06/10/2020, Day 7
终于在12点之前刷了6道题。

day8
继续tree 三题
level order with Queue
注意list.reverse() and reversed(list)
学习了list comprehensive in python

连续第 7 天打卡，完成 3 道 Binary Search, Graph 题：(1.5/3)
1. Search Insertion Position
2. Course Schedule I
3. Course Schedule II

Tips 总结：
1. Graph 有 3 种 representation，分别是 Edge List, Adjacency Matrix, Adjacency Lists，其中最后一种方式最为常用（因为 on average 具有更好的 performance）；
2. 在计算机科学领域，directed graph 的 topological order or topological sorting 是其所有 vertices 的 linear sorted order，使得对于从顶点 u 到顶点 v 的每个有向边 u -> v， u 在排序中都在 v 之前。
    例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束，在这个应用中，topological order or topological sorting 只是一个有效的任务顺序；
3. 当且仅当图中没有 directed circle 时（即 directed acyclic graph），才有可能进行 topological sorting；
3. 任何 directed acyclic graph 至少有一个 topological order or topological sorting。已知有算法可以在线性时间内，构建任何 directed acyclic graph 的 topological order or topological sorting。分别是 DFS 和 BFS。

坚持第10天，刷了三题
笔记：
1. stack.peek() 和pull()不一样。peek不删除节点，只是retrieve
2. 如果希望stack最top的node是left node, 则应该先加入right node to stack, 再加入left node to stack
3. In binary search tree, left.val < root.val <right.val