# 1. 概览

![](https://3627908257-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPqEevD2Q0Ke8GAFUsnRo%2Fuploads%2FD4TFOxfRGsjAfMAszlGH%2F%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A6%82%E8%A7%88.png?alt=media\&token=d05004cf-eda3-4480-a27b-3f40af28fe80)

## 1. 高频

### 1.1 计算机基础

这部分是重中之重，必须学扎实，在平时也会用到。

1. 数据结构
   1. 四种最基本的一维容器：数组+链表、栈+队列。必须熟练掌握
   2. Hash 表：熟练应用、掌握基本的建立方法
   3. 四种基本的树形结构：二叉堆、二叉搜索树、字典树、并查集。要熟练掌握，它们的应用非常广泛，在库/框架里很常用，而且都不难写
2. 树和图：重点。链表是特殊的树，树是特殊的图，树和递归也有着密切关系
3. DFS 和 BFS：重点。搜索是解决一切问题的万金油算法
4. 字符串：重点。平时应用的最多

### 1.2 子问题划分

这部分更进阶一些，是有决策地整理和理解，会考虑整个状态空间。

1. 递归：子问题是不同规模如何处理
2. 分治
3. 动态规划：子问题是当前阶段如何决策
4. 贪心

不论是递归还是动规，都考虑的是本层逻辑。递归要想的是本层逻辑，而不要往太深的地方想。要把子问题看作是一个写好的函数，去直接调用；然后在本层考虑怎样把问题的规模进一步缩小，只要一缩小，子问题就会遇到边界，然后就能层层返回。动规是分阶段的，考虑“当前阶段”这个子问题，然后通过不同决策再变到之后的一个问题，直到目标阶段。

### 1.3 基本技巧

这部分属于优化类。候选集合优化是提高效率的关键，本质是去除冗余。前缀和+二分答案是重点，都比较好写，且代码也不难

1. 双指针
2. 滑动窗
3. 前缀和：属于预处理，用空间换时间。
4. 二分答案：是把一个最优解问题变成判定问题，因为验证要比求解简单些

## 2. 相对低频

高端技巧

1. 最短路、最小生成树：图论算法，一般 Hard 题较多

2. 离线批处理、关键事件思想

3. [218. 天际线问题（H）](https://leetcode.cn/problems/the-skyline-problem/)

4. [1851. 包含每个查询的最小区间（H）](https://leetcode.cn/problems/minimum-interval-to-include-each-query/)