Graph类型题总结

Graph类型题常见的有1. Topological sorting 2. connected component 3. find cycle。同时要注意有向/无向的区别。

To help you guys have a better understanding of this problem, I tried to summary the methods I saw from others in this post. This is my first time to write a summary post, so correct me if there is any problem. Thanks!

To analyze Time Complexity and Space Complexity: n is the total number of words, m is the average length of each word

背包问题主要分为01背包和完全背包问题。
思路上转载from背包九讲。

DP类型题总结

Word Ladder I和Word Ladder II两道题给我们的经验：

1. It’s much faster than one-end search indeed as explained in wiki.
2. BFS isn’t equivalent to Queue. Sometimes Set is more accurate representation for nodes of level. (also handy since we need to check if we meet from two ends)
3. It’s safe to share a visited set for both ends since if they meet same string it terminates early. (vis is useful since we cannot remove word from dict due to bidirectional search)
4. It seems like if(set.add()) is a little slower than if(!contains()) then add() but it’s more concise.

Path Sum类型题的思路就是进行DFS。编写DFS函数的时候要想明白：1.DFS函数的作用是干什么 2.DFS函数的base case是什么 3.DFS函数的输入输出分别是什么

Majority Element题型是找一个数组中超过n/k的majority元素，使用的算法是Majority Vote。
原理就是对于每一个Majority Element都设置一个count：1.如果选中的num与Majority Element相等，对应的count++ 2.如果所有的Majority Element没有与num相等的，那么去检查有没有count为0，如果有，将这个Majority Element设置为num并将count设为1 3.如果以上都不符合，那么所有count–

所以我们看到程序中都是用的if，else if，也就是说有符合条件的情况，对于这个num的判断就结束了

Monotonic Stack问题总结

单调栈问题的思路就是栈中的元素都是单调增或者单调减的，当我们想要新加入元素到栈的时候，我们回去查看是否符合单调标准，不符合的弹出。
https://blog.csdn.net/qq_17550379/article/details/86519771

Greedy慢慢总结：