Leetcode刷题前应该具备哪些入门知识

时间复杂度、空间复杂度

你需要知道什么是时间/空间复杂度， 大O是什么意思，常见的复杂度包括哪些。如何来判断一段程序的复杂度。

一般语言自带的常用数据结构：（不用语言的对应数据结构名称可能有所差异）

列表（list/array list/array等）。列表常见操作，以及相关的时间复杂度。

• append一个元素、pop末尾元素均为O（1）
• 查找某个元素的索引O（n）

哈希（hash table）。需要掌握以下基础知识：

• 什么是哈希，哈希函数是什么，最常见的哈希表数据结构是什么（集合与哈希表）

集合（set/ hashset等）。

• 集合一般用于干什么？
• 集合的常见操作有哪些？每个常见操作的时间复杂度是什么？

哈希表（Hashmap/ dict/ unordered_map等）。

• 哈希表一般用于干什么？
• 哈希表有哪些常见操作？对应的时间复杂度，空间复杂度分别是什么？

栈（stack）

• 什么是栈？什么是后进先出？
• 栈一般用于解决什么问题？
• 什么是程序栈？
• 你所熟悉的语言当中栈是用什么数据结构实现的？（Python当中用list就可以代表栈）

队列（queue）

• 什么是队列？什么是先进先出？
• 队列一般应用在哪些场景当中？
• 什么是消息队列？
• 你所熟悉的语言当中栈是用什么数据结构实现的？（Python当中可以用deque或者queue）

堆（heap）

• 什么是堆？什么是最大堆、最小堆？
• 堆一般用于解决什么问题？
• 你所熟悉的语言当中堆是用什么数据结构实现的？（Python当中堆用的是列表实现的，并且Python只有最小堆没有最大堆）

一般语言不自带的数据结构：（需要自己手工创建）

链表（linked list）

• 链表的节点（node）是如何实现的？
• 如何创建一个链表？
• 如何遍历一个链表？
• 如何在链表中查找一个元素是否存在？
• 如何在链表中添加/删除一个元素？

二叉树（binary tree）

• 二叉树的节点（node）是如何实现的？
• 如何创建一个二叉树？
• 如何遍历一个链表？何谓二叉树的层序、前序、中序、后序遍历？
• 二叉搜索树（二叉查找树、binary search tree、BST）
• 与普通的二叉树相比，二叉搜索树特点是什么？如何证明一棵二叉树是/不是一课二叉搜索树？
• 一个二叉树是二叉搜索树 <-> 该二叉树的中序遍历是单调递增的

简单图（graph）

• 什么是图？什么是有向图（directed graph）？什么是无向图（undirected graph）？
• 图与树的关系是？如何知道一个图是不是一课树？
• 如何实现一个简单图？
• 应该掌握的入门算法：

递归：

• 什么是递归？
• 递归的优势、劣势是什么？
• 递归三要素是什么？

排序算法：

• 快速排序如何实现？时间/空间复杂度是多少？
• 归并排序如何实现？时间/空间复杂度是多少？

二分法：

• 二分法的基本原理是什么？
• 二分法一般用于解决什么问题？
• 二分法的时间复杂度是什么？

宽度优先遍历（宽度优先搜索、Breadth first search、BFS）：

• 宽度优先遍历的模板是什么？
• 宽度优先遍历的时间/空间复杂度是什么？
• 宽度优先遍历一颗二叉树与一个图的区别在哪？
• 宽度优先遍历一般用于解决什么问题？

深度优先遍历（深度优先搜索、Depth first search、DFS）：

• 深度优先遍历的模板是什么？
• 深度优先遍历的时间/空间复杂度是什么？
• 深度优先遍历一颗二叉树与一个图的区别在哪？
• 深度优先遍历一般用于解决什么问题？