为什么写这篇文章

很多人刷 LeetCode 之前只有非常有限的代码和数据结构基础，然后想要暴力的通过刷 LeetCode 来迅速转码上岸，最后直接去大厂当码农挣大钱。作为一个也曾经抱有此类幻想的人，本人也曾经试图在没有基础情况下简单暴力的去 LeetCode 刷题，然后被打击的体无完肤，答案看不懂，别人的解释看不懂，甚至各种教学视频都看不懂，于是直接放弃了转码的幻想，一段时间后不甘心拾起来又放下反反复复三年就过去了，现在回想下真的是耽误了好多时间。鉴于个人的惨痛经历，我准备把刷题之前应该先掌握的基础知识罗列在这里，希望对也想要刷题当码农，尤其是转码的各位有帮助吧。如果你有一门熟悉的语言，但是没有太多数据结构/算法的基础知识，把下面列举的基础补齐大概需要一个月左右时间。

语言基础

• 至少选择一门相对熟悉的语言来刷题，虽然 LeetCode 上常见的开发语言都是支持的，但是个人还是建议选择 Python/ Java / C++ 其中一个。这几门语言各种基础的数据结构都比较完善，刷题时候用的人也是最多的，看答案/别人的解答时候也最容易找到参考资料。
• 对于你要选择的刷题语言，起码你需要知道代码是怎么运行的，什么是变量、循环、函数、类与对象等。

时间复杂度与空间复杂度基础

• 你需要知道什么是时间/空间复杂度， 大 $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）：
  • 深度优先遍历的模板是什么？
  • 深度优先遍历的时间/空间复杂度是什么？
  • 深度优先遍历一颗二叉树与一个图的区别在哪？
  • 深度优先遍历一般用于解决什么问题？

如果以上问题你都能回答的上来的话，那你已经可以去 LeetCode 的题海中徜徉了。

本文转载自其他平台，作者：TimothyL，文章内容略有删改。