A. 常用基础数据结构 (可能会有遗漏,总结的也不是很全面和完美,欢迎批评指正和推荐补充).--
a. LinkedList(必须要会如何遍历/反转链表,如何高效找到LinkedList中间节点的位置,slow/fast pointer, cycle)推荐题:LC2130
b. Queue (会应用poll(), offer(), peek()等操作,并知道其时间复杂度,常与BFS联合考察,BFS的space complexity往往由queue的size决定, 想一想为什么有时候BFS在从queue中poll一个元素前,会先记录下当前queue的size,而有时候却不用?)
c. Stack/Deque(基础的操作一定要会,monotonic stack一定要会,也常和Tree一起联合考察,即Iterative way pre-order and in-order traversal)推荐题:239(我最喜欢的monotonic stack的题,请务必弄清楚理解为什么时间复杂度是O(n)而不是O(n^2),496,20,155, 772
d. Heap/PriorityQueue (请务必知道,如何根据特定规则定义PriorityQueue的排列顺序,了解offer, poll, peak的时间复杂度,请自己尝试实现一个heap,也常与Dijkstra一起联用)推荐题:23, 973,295
e. Set/Map/TreeSet/TreeMap (请务必了解四种数据结构常用操作的时间复杂度,请尝试自己实现一个HashMap,了解一下hash collision,请务必了解如何重写一个自定义classs的hashCode()与equals()以及二者的关系)推荐题:2158(TreeMap), 560(HashMap). check 1point3acres for more.
f. Graph (BFS/DFS/Dijkstra/check cycle[4]) (请务必熟练掌握这三种算法,非常非常非常重要!要会分析每一种的时间空间复杂度)推荐题:317
g. Tree (一般常与Recursion联用,注意average case/worst case的不同,注意Binary Search Tree的特性)推荐题:545 and so many questions
B. 常用算法及思想
a. Sorting (Merge Sort, Quick Sort, Bucket Sort) -> 这里稍微改动一下就是quick select是很多Kth题的最优解,average time O(n),那问题来了,worst time是多少呢? 推荐题目:347 (很巧妙的bucket sort)
b. BFS/DFS/Dijkstra 我再强调一遍哥仨的重要性!
c. Greedy (这个真的有时候比较难想,难的点在于如何证明其正确性)
d. DP (我到现在也不是很会DP,在这里抛砖引玉一下,但是目前我的看法是,第一步一定要想清楚你dp的物理意义,第二步一定要定义好你的induction rule!一般一道题,你可以先从brute force DFS(recursion)的方法开始,优化到DFS + MEMO(这还挺常见的),如果能再优化到iterative dp更好),如果准备时间不多,也不必花太多时间在dp(但经典DP要会!)推荐题:300, 198
e. Binary Search (常见模板一定要烂熟于心,常与一个O(n)的check function联用,从而得到一个O(nlogn)的套路解法)推荐题:875 (必做,你做了这套题,等于多会了10道题!). ----
f. Sliding Window (必会,不是很难)推荐题:3
g. Two pointers (必会,也不难,常与sorting联用)推荐题:15
h. Prefix Sum(必会)推荐题:528(很有趣一题)
i. Union Find (我觉得最好会,不是很难,我推荐跟古城算法的视频学一下[2],城主yyds,注意听听城主对其时间/空间复杂度的分析)推荐题:2092(也是很有意思的一道题)
j. Topologic sort (必会,经典题course schedule,以及最近谷歌常考的食谱的那道题)
C. 不常考但推荐会的算法or数据结构
a. Trie (面亚麻必会,常见的比如buildTree,insert,search,delete(也可以会),时间复杂度分析)推荐题:1268
b. Line Sweep (常与TreeSet and TreeMap联用)
c. Segment Tree(面谷歌需要会一下,我推荐城主视频,我也是跟城主大佬学的,顺便准备一下cord tree)
d. Rolling Hash (其实说白了,也不难,学学呗)推荐题:1044(有趣有趣,这题突然让我想到一点,当你看到minimum的题的时候,不妨往BFS和Binary Search身上想想!)
. .и
D. OOD
a. 面亚麻要准备,我推荐一个我个人心目中的神贴[3]!写的太好了,总结来说,要有辨别core class and object的能力!以及想清楚各个class之间的关联关系,一定要用上extends or implements,设计模式是亮点,不必强求,也不必太急着写代码,分析好class先,以及如何调用相关的method?
. 1point3acres
一些小建议:.1point3acres
A. 如果时间多的话,我强烈推荐你参加每周末的LC周赛!对我的帮助真的很大!而且你能看到自己的进步!是一件非常令人愉悦的事情!
B. 多招人Mock,看别人Mock和自己上去Mock是感觉完全不同的两件事情,更多的练习和紧张的气氛,更容易锻炼你的临场反应和能力!-baidu 1point3acres
C. 多向工业界的前辈/大佬请教,能学到太多知识了!
D. 多多networking,多多connection,多一个朋友多一条路!
E. 做人有礼貌,态度好一点,这样大家也愿意帮助你,都能有一个好心情!