Skip to main content

推荐题目

不建议刷的题目类型：

  • 非高频的hard题目，费时费力又很难在面试中遇到，性价比太低。
  • 贪心法题目，每道题都不一样，解法没有通用性。

排序​

注意：215题是与快速排序非常相似的快速选择（Quick Select）算法，面试中很常考

链表​

注意：快慢指针和链表反转几乎是所有链表类问题的基础，尤其是反转链表，代码很短，建议直接背熟。

堆、栈、队列、哈希表​

二分法​

双指针​

宽度优先搜索​

面试中最常考的

深度优先搜索​

面试中最常考的（分类的稍微有点粗糙了，没有细分出回溯/分治来，准备找个时间给每个DFS的题标记下是哪种DFS）

前缀和​

以上内容皆为面试中高频的知识点，以下知识点和题目在面试中属于中等频率（大概面10道题会遇到一次），时间不足的情况下，请以准备上面的知识点为主。

并查集​

  • 基础知识：如果数据不是实时变化，本类问题可以用BFS或者DFS的方式遍历，如果数据实时变化（data stream）则并查集每次的时间复杂度可以视为O（1）；需要牢记合并与查找两个操作的模板

  • 常见题目：

字典树​

  • 基础知识：（https://zh.wikipedia.org/wiki/Trie）；多数情况下可以通过用一个set来记录所有单词的prefix来替代，时间复杂度不变，但空间复杂度略高

  • 常见题目：

    • 208. 实现 Trie (前缀树)
    • Leetcode 211 Design Add and Search Words Data Structure
    • Leetcode 1268 Search Suggestions System
    • Leetcode 212 Word Search II

单调栈与单调队列​

扫描线算法​

  • 基础知识：一个很巧妙的解决时间安排冲突的算法，本身比较容易些也很容易理解
  • 常见题目：

TreeMap​

  • 基础知识：基于红黑树（平衡二叉搜索树）的一种树状 hashmap，增删查改、找求大最小均为logN复杂度，Python当中可以使用SortedDict替代；SortedDict继承了普通的dict全部的方法，除此之外还可以peekitem(k)来找key里面第k大的元素，popitem(k)来删除掉第k大的元素，弥补了Python自带的heapq没法logN时间复杂度内删除某个元素的缺陷；最近又在刷一些hard题目时候突然发现TreeMap简直是个神技，很多用别的数据结构写起来非常麻烦的题目，TreeMap解决起来易如反掌。
  • 常见题目：
  • 729. 我的日程安排表 I***
  • Leetcode 981 Time Based Key-Value Store
  • 846. 一手顺子*
  • Leetcode 218 The Skyline Problem
  • Leetcode 480. Sliding Window Median (这个题用TreeMap超级方便)
  • 318. 最大单词长度乘积

动态规划​