今年又面了一波，集齐了FANMG的offer，发现刷题在找工作中的比重越来越低。这有多方面的原因，但是最大的因素是刷题对我来说已经不是那么的困难了。

回头看，刷题其实是一劳永逸的，熬过之后收获是持续性的，完成一次完整系统的刷题，之后再找工作只需要稍加温习即可。而且随着level越来越高，算法题的比重也越来越低，更多的是考察系统性知识、leadership和culture fit。

最近做了一些分享，发现很多人还在刷题的煎熬中，甚至有些迷茫，这边我整理下我的刷题方法，希望对大家有帮助。

几个重点

1. 刷题只需要200-300道即可，不是以量取胜的，加量会透支自己的精力（当然如果精力旺盛的话，尽管刷）
2. 不是能写出来答案就能过面试，需要理解为什么用这个解法，各种解法之间的trade off，写代码之前如果能做好沟通，能大大的给你加分
3. 别把刷题看的很难，对比于高考来说这都是小儿科，而且核心的算法就那么几个，解法也就那么多，把每一个解法都吃透了，不会碰到太出格的。
4. DP不在今天讨论范围，常见的可以看下，除非你要找特定公司，不然的话DP纯浪费青春
5. 面试是看缘分的，不要害怕被问到一道不会的题目，就想去把所有奇奇怪怪的题都刷了，大多数面试题都是高频常见的，面试官也是人，他只是想考察你的能力，太难的并不利于考察也不利于招聘，当然那些不怕招不到人的公司除外，如果真的被问到了不会的，尽力去做就好，这是缘分。换句话说，有些时候你答的很好，也会被拒，不要太放在心上，缘分到了啥都来了。
6. 系统设计和BQ不在这次讨论之中

刷题方法

我每次刷题都是按照以下的步骤，如果是第一次刷题，需要花更多的时间在每一题的理解上，而非仅仅把他做出来。时间线大约是1个月，如果第一次的话一般需要3个月。不推荐安排3个月以上，一来消耗自己的精力，二来每次刷题如果不够专注的话并不能让你深刻理解。

1. 基础知识复习：这方面基本上就是看下各种算法优劣点、时间复杂度、适用场景，这个自己整理好，每次都能拿出来用。
2. 按照解法、题型刷题（题型整理在后面），标记那些自己觉得没把握的（没有彻底理解的），这一块根据自己的能力推进，切记完全搞懂了再推进下一个，不然就白刷了。除了我列出来的题目，可以在leetcode上按照右侧的tag刷一下该题型的高频，确定自己理解透彻了。
3. 查漏补缺，把之前标记的题拿出来混做一下
4. 【投简历之后】开始按照面经和公司tag高频刷一下，边面试边刷。投简历的时候自己分一下tier，把不想去的最先投，练练手。要是简历投了没回应，请到这里：北美找工作（简历修改）咨询服务

题型、解法整理

这里只是给你整理了典型的题型和解法，具体怎么解，模板自行网上搜，或者留言提问。如果实在搞不清楚，上面那个链接的咨询服务可以用来答疑

Binary Search

这是最最最基础的，一定要熟记并且知道什么时候用。基本上有排序的数组，然后找个一个数字都应该想到binary seach。排序的时间复杂度是NLog(n)，搜索的时间复杂度是Log(n)，所以比O(n)遍历更加的解法就是他了。

这里给一套我用的模板，注意我这边是start + 1 < end 所以在结束的时候是相邻的，需要检查下相邻的两个哪个是结果。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        start = 0
        end = len(nums) -1
        
        while start + 1 < end:
            mid = start + (end-start)//2
            
            if nums[mid] >= target:
                end = mid
            
            if nums[mid] < target:
                start = mid
                
        
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        
        return -1

• https://leetcode.com/problems/binary-search/
• https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
• https://leetcode.com/problems/first-bad-version/
• https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/
• https://leetcode.com/problems/search-in-rotated-sorted-array/
• https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
• https://leetcode.com/problems/search-a-2d-matrix/
• https://leetcode.com/problems/search-a-2d-matrix-ii/
• https://leetcode.com/problems/find-peak-element/

Tree

如果新手的话，树的题目会比较难上手，不过他都是有两种解法——Traverse 和 Divide Conquer，体会两者的不同，为后面的DFS打基础。Tree 这部分会比较煎熬，但是一定要掌握。

• https://leetcode.com/problems/binary-tree-inorder-traversal/
• https://leetcode.com/problems/binary-tree-preorder-traversal/
• https://leetcode.com/problems/binary-tree-postorder-traversal/
• https://leetcode.com/problems/maximum-depth-of-binary-tree/
• https://leetcode.com/problems/diameter-of-binary-tree/
• https://leetcode.com/problems/binary-tree-paths/
• https://leetcode.com/problems/maximum-subarray/
• https://leetcode.com/problems/balanced-binary-tree/
• https://leetcode.com/problems/maximum-average-subtree/
• https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
• https://leetcode.com/problems/validate-binary-search-tree/
• https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
• https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
• https://leetcode.com/problems/binary-search-tree-iterator/
• https://leetcode.com/problems/insert-into-a-binary-search-tree/
• https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

BFS

这部分是我觉得仅次于二分法简单的，不过代码比较长，但写起来很享受，有很多时候BFS和DFS都可以的话，推荐写BFS，容易理解也不容易出错。当然我也碰到面试官一定要你写DFS的，毕竟BFS过于简单了。

BFS的模板我就不提供了，简单的来说就是用一个queue，把初始点放进去，然后while循环直到queue空为止，每次操作把处理到的附近节点都放到queue里面去，记得要用个set去check是否已经放过了，不然会死循环。

**另外BFS里面涉及到图的题目，这里也放进去了。

• https://leetcode.com/problems/binary-tree-level-order-traversal/
• https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
• https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
• https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
• https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
• https://leetcode.com/problems/graph-valid-tree/
• https://leetcode.com/problems/clone-graph/
• https://leetcode.com/problems/number-of-islands/
• https://leetcode.com/problems/number-of-distinct-islands/
• 【这题虽然关系不大，但考察操作】https://leetcode.com/problems/spiral-matrix/
• 【用DFS更好】https://leetcode.com/problems/word-ladder/

拓扑和图

拓扑（Topological Sort）和图相关的，极度高频，掌握怎么用indegree去寻找入口

• https://leetcode.com/problems/course-schedule/
• https://leetcode.com/problems/course-schedule-ii/
• https://leetcode.com/problems/sequence-reconstruction/

DFS

基本上就是找排列或者组合的题目，DFS的入门比较难，但是只要入门了，就是非常厉害的一个工具，不像DP，学了半天也不知道怎么用。

• https://leetcode.com/problems/combination-sum/
• https://leetcode.com/problems/combination-sum-ii/
• https://leetcode.com/problems/subsets/
• https://leetcode.com/problems/subsets-ii/
• https://leetcode.com/problems/palindrome-partitioning/
• https://leetcode.com/problems/permutations/
• https://leetcode.com/problems/permutations-ii/
• https://leetcode.com/problems/n-queens/
• https://leetcode.com/problems/word-ladder/

Linked List

这个概念要先掌握，不然会一团浆糊，特别是指针，不是很懂的推荐先去看看书。linkedin list最重要的一个技巧就是用dummy node

• https://leetcode.com/problems/partition-list/
• https://leetcode.com/problems/merge-two-sorted-lists/
• https://leetcode.com/problems/reverse-linked-list/
• https://leetcode.com/problems/reverse-linked-list-ii/
• https://leetcode.com/problems/swapping-nodes-in-a-linked-list/
• https://leetcode.com/problems/reorder-list/
• https://leetcode.com/problems/rotate-list/
• https://leetcode.com/problems/copy-list-with-random-pointer/
• 【绝对不会考，但是学习下技巧】https://leetcode.com/problems/linked-list-cycle/
• https://leetcode.com/problems/sort-list/
• https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
• https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
• https://leetcode.com/problems/reverse-nodes-in-k-group/

Array

array的题目特别多，特别杂，一部分可以用hashmap/hashset或者PriorityQueue解决，不过还是推荐有空多刷一刷，没空的话，就看看下面几个典型的

• https://leetcode.com/problems/implement-strstr/
• 【三目翻转】https://leetcode.com/problems/rotate-array/
• https://leetcode.com/problems/intersection-of-two-arrays/
• https://leetcode.com/problems/merge-sorted-array/
• https://leetcode.com/problems/median-of-two-sorted-arrays/
• https://leetcode.com/problems/k-closest-points-to-origin/

前缀和数组

• https://leetcode.com/problems/maximum-subarray/
• https://leetcode.com/problems/subarray-sum-equals-k/

双指针

• https://leetcode.com/problems/move-zeroes/
• https://leetcode.com/problems/remove-duplicates-from-sorted-array/
• https://leetcode.com/problems/valid-palindrome/
• https://leetcode.com/problems/rotate-string/
• 【和hashmap解法的区别】https://leetcode.com/problems/two-sum/
• 【本质上是2sum】https://leetcode.com/problems/3sum/
• 【本质上是3sum】https://leetcode.com/problems/4sum/
• https://leetcode.com/problems/3sum-closest/
• https://leetcode.com/problems/sort-colors

Priority Queue

非常强大且容易掌握的数据结构，但是一定要知道他是怎么实现的（heap）

• https://leetcode.com/problems/ugly-number/
• https://leetcode.com/problems/ugly-number-ii/
• https://leetcode.com/problems/top-k-frequent-elements/
• https://leetcode.com/problems/merge-k-sorted-lists/
• https://leetcode.com/problems/high-five/
• https://leetcode.com/problems/k-closest-points-to-origin/
• https://leetcode.com/problems/merge-k-sorted-lists/
• https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

其他

• 非常高频以及综合的一道题：https://leetcode.com/problems/lru-cache/
• https://leetcode.com/problems/meeting-rooms-ii/
• https://leetcode.com/problems/insert-interval/
• 【常见的DP题目】https://leetcode.com/problems/trapping-rain-water/
• 【买卖股票的终极DP】https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
• https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/
• https://leetcode.com/problems/random-pick-with-weight/
• https://leetcode.com/problems/insert-delete-getrandom-o1/
• https://leetcode.com/problems/valid-sudoku/

其他资源

Blind 75极致快速刷题：https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions