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

今天做了9题，后天要FB电面了 希望一切顺利

day 6 打卡: 拓扑排序只需要确认入度为0，不需要额外的Set追踪是否已经被访问过，因为一旦入度为0就会入队，不会有重复。


求加米，必回加！一起加油！

day 4 只刷了一道题

day 4 刷了一道bfs
lintcode 178 graph valid tree
思路：
1. 建graph，i，j互相存进对方的neighbor。node 0压入queue，加入visited
2. queue中弹出node 0，count++，iterate所以node，如果是neighbor并且不再visit里，继续压入queue，加入visited
3.重复2

return True if count == node总数 else False

今天刷了3题，分别是：
Wiggle Subsequence
Guess Number Higher or Lower II
Binary Tree Zigzag Level Order Traversal

今天高效写了6道题
两道N-Queens用backtrack
Rotate List用两种方法解

7.22 打卡

1. Single Number III. 重点是用一个bit把这个问题转化成两个Single Number I 的问题
2. Basic Calculator. Stack 经典题
3. Binary Tree Zigzag Level Order Traversal. BFS层序遍历。

7/22

7.23打卡， 4道medium

刷题打卡第12天
15. 3Sum 这是一道medium提，有很多思路可以实现，一开始想着n*n遍历，然后用hash来定位最后一个，但是发现很难避免重复，接着尝试对原数组进行排序，然后用binary search找最后一个数，结果发现速度不达要求，最后使用n遍历第一个数，然后bi-directional binary search后两个数，以n^2的复杂度解决问题。

16. 3Sum Closest 也是使用类似bi-directional binary search, 遍历第一个数，从两端搜索第二个数，记录最小gap即可。

17. Letter Combinations of a Phone Number 使用dictionary将每个数字map到可能的字母，然后通过递归实现。同样的也可以用FIFO队列加上数组对应数字来取代dictionary.