Leetcode刷题方法以及题型整理

今年又面了一波,集齐了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

Tree

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

BFS

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

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

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

拓扑和图

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

DFS

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

Linked List

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

Array

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

前缀和数组

双指针

Priority Queue

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

其他

其他资源

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

看完了?留个评分呗?
[4人评了分,平均: 5/5]

本站原创文章皆遵循“署名-非商业性使用-相同方式共享 3.0 (CC BY-NC-SA 3.0)”。转载请保留以下标注:

原文来源:《Leetcode刷题方法以及题型整理》

发表评论

邮箱地址不会被公开。

评论列表(1)

返回顶部