在职跳槽刷题打卡及适时分享感悟--计划明年2月面试

sanmao0715 发表于 2020-11-17 07:55
私信我联系方式呗

新人不够米，可以私信我你的联系方式吗？

sanmao0715 发表于 2020-11-17 07:55
私信我联系方式呗

嗨 可以拉我一起吗？ 私信你了哈

11.18

257. Binary Tree Paths （Easy）
正常的 post over traversal，

438. Find All Anagrams in a String (Medium)
需要通过 两个 character hashmap + sweep的方法，这里hashmap可以用 一个array size of 26来用，每个index代表一个字母，python 中用 ord(ch) - ord(‘a’) 来得到index， 我开始用了counter， 但是如果不注意remove count 归0的元素，在比较 counter的时候会不准确。

72. Edit Distance （Hard）
这题拿到后没有头绪，看了topic 是DP，也不知道怎么下手。看了youtube上Tech Dose的解题视频分析一下子就豁然开朗了，看了一半，就把题写出来了，然后直接给Tech Dose打赏了$5。以后一些好的解体视频还是要多看，很有助于理清解体思路。这道题的关键在于把 insert， remove ，replace 3个operation 转化成 dp的stae transition，从两个string的末端开始recursion，state transition。最后可以很直观写bottom up形式的DP

11.20
昨天晚上学了下ML的基础知识，今天听了个国内美团的技术讲座，所以刷题先就划个水
1086. High Five (Easy)
1480. Running Sum of 1d Array (Easy)
621. Task Scheduler (Medium)
这道题有多种解法，值得再钻研一下，我看了youtube的一个heap的做法才写出来的，关键是在heap上存每个task剩余的个数，然后每n+1个time unit来pop heap做task，计数和把没清零的task放回heap

11.21 11.22

227. Basic Calculator II (Medium)
207. Course Schedule (Medium)
210. Course Schedule II (Medium)

这个周末刷题不多，但是收获还是不小的，先是把通过看youtube 视频把basic calculator的题目的解题思想捋一捋，感觉再写calculator的题就顺多了
之后看了Course Schedule系列，同过自己写solution，和学习YouTube的上Tech Dose的解题思路感觉自己终于吧cycle detection 和 topological sort的基本东西弄明白了。
Cycle detection（无论是有向图还是无向图）的关键在于 traversal path中会不会碰到 path中的node，还要通过某种手段，比如节点的状态来区别visited 和在当前path上的node。Undirected 的情况稍微简单一些，可以通过多pass 一个node parent，只通过是否visited就行了。
Topological Sort 主要有两种方法，一种是DFS + 状态array，一种是Kahn’s algorithm，通过BFS + indegee array，只traverse indegree 为0的 vertice， traverse 每个edge的时候来会把相关vetex的indegree 减一，最后同过一个count variable看traversal是否遍历了所有节点。

感觉自己现在有些倾向于专题训练了，把解法类似的题目一起做来巩固知识，同时对同一道题的多种解法都尝试地写出来。看了一些面经，发现有的面试官在candidate做出一个解法后，还会要求更好或者另一种解法。感觉刷题还是要先注重质量，把每一道题搞透彻，再去想数量，否则只能是“看上去很美了”

11.23

今天重点研究了这两道自己之前理解很吃力的题，希望以后面试碰到类似的题能够拿下了：
10. Regular Expression Matching （Hard）
有递归和DP两种解法，重点在于碰到*时，要去match 0次和match 1次的状态转换。
332. Reconstruct Itinerary（Medium）
通过一个stack来存answer，通过DFS来traverse，先找到destination，再往回找， 当以一个node，所有的out edges（也就是题目中的机票）都走完的时候，就可一push进stack了。
67. Add Binary
用linkedlist的方法做的，好像面试的时候会要求用bit manipulation，这个还需要专门复习一下

我有组队日常c++刷题和交流讨论（针对无人驾驶机器人公司的）， 如果你感兴趣，可以一起刷题呀：estheryoubingba

楼主。求你去我地里加颗大米呗， 有急用。给你祝福。