0%

数据结构与算法学习笔记

学习路线图

复杂度分析

目标:

自行分析大部分数据结构和算法的时间、空间复杂度。在学习专栏中其他的时候,再不停地、有意识地去训练自己的复杂度分析能力。
掌握递推公式、递归树分析方法

重要程度:10

数组、栈、队列

这一部分内容非常简单,初学者学起来也不会很难。但是,作为基础的数据结构,数组、栈、队列,是后续很多复杂数据结构和算法的基础,所以,这些内容你一定要掌握。
目标:

实现动态数组、栈、队列

重要程度:8

链表

链表非常重要!虽然理论内容不多,但链表上的操作却很复杂。所以,面试中经常会考察,你一定要掌握。而且,我这里说“掌握”不只是能看懂专栏中的内容,还能将专栏中提到的经典链表题目,比如链表反转、求中间结点等,轻松无 bug 地实现出来。
目标:

能轻松写出经典链表题目代码

重要程度:9

递归

对于初学者来说,递归代码非常难掌握,不管是读起来,还是写起来。但是,这道坎你必须要跨过,跨不过就不能算是入门数据结构和算法。我们后面讲到的很多数据结构和算法的代码实现,都要用到递归。递归相关的理论知识也不多,所以还是要多练。你可以先在网上找些简单的题目练手,比如斐波那契数列、求阶乘等,然后再慢慢过渡到更加有难度的,比如归并排序、快速排序、二叉树的遍历、求高度,最后是回溯八皇后、背包问题等。
目标:

轻松写出二叉树遍历、八皇后、背包问题、DFS 的递归代码

重要程度:10

排序、二分查找

这一部分并不难,你只需要能看懂我专栏里的内容即可。
目标:

能自己把各种排序算法、二分查找及其变体代码写一遍就可以了

重要程度:7

跳表

对于初学者来说,并不需要非得掌握跳表,所以,如果没有精力,这一章节可以先跳过。
目标:

初学者可以先跳过。如果感兴趣,看懂专栏内容即可,不需要掌握代码实现

重要程度:6

散列表

尽管散列表的内容我讲了很多,有三节课。但是,总体上来讲,这块内容理解起来并不难。但是,作为一种应用非常广泛的数据结构,你还是要掌握牢固散列表。
目标:

对于初学者来说,自己能代码实现一个拉链法解决冲突的散列表即可

重要程度:8

哈希算法

这部分纯粹是为了开拓思路,初学者可以略过
目标:

可以暂时不看

重要程度:3

二叉树

这一部分非常重要!二叉树在面试中经常会被考到,所以要重点掌握。但是我这里说的二叉树,并不包含专栏中红黑树的内容。红黑树我们待会再讲。
目标:

能代码实现二叉树的三种遍历算法、按层遍历、求高度等经典二叉树题目

重要程度:9

红黑树

对于初学者来说,这一节课完全可以不看
目标:

初学者不用把时间浪费在上面

重要程度:3

目标:

可看可不看,能看懂专栏里的讲解就可以

重要程度:5

堆与堆排序

这一部分内容不是很难,初学者也是要掌握的。
目标:

能代码实现堆、堆排序,并且掌握堆的三种应用(优先级队列、Top k、中位数)

重要程度:8

图的表示

图的内容很多,但是初学者不需要掌握那么多。一般 BAT 等大厂面试,不怎么会面试有关图的内容,因为面试官可能也对这块不会很熟悉哈:)。但是,最基本图的概念、表示方法还是要掌握的。
目标:

理解图的三种表示方法(邻接矩阵、邻接表、逆邻接表),能自己代码实现

重要程度:8

深度广度优先搜索

这算是图上最基础的遍历或者说是搜索算法了,所以还是要掌握一下。这两种算法的原理都不难哈,但是代码实现并不简单,一个用到了队列,另一个用到了递归。对于初学者来说,看懂这两个代码实现就是一个挑战!可以等到其他更重要的内容都掌握之后,再来挑战,也是可以的。
目标:

能代码实现广度优先、深度优先搜索算法

重要程度:8

拓扑排序、最短路径、A* 算法

这几个算法稍微高级点。如果你能轻松实现深度、广度优先搜索,那看懂这三个算法不成问题。不过,这三种算法不是重点。面试不会考的
目标:

重要程度:5

字符串匹配(BF、RK)

目标:

能实践 BF 算法,能看懂 RK 算法

重要程度:7

字符串匹配(BM、KMP、AC 自动机)

较难,看懂不容易,即使要学,看懂就好
目标:

初学者不用把时间浪费在上面

重要程度:3

字符串匹配(Trie)

目标:

能看懂,知道特点、应用场景即可,不要求代码实现

重要程度:7

位图

目标:

位图不是重点,如果有余力最好掌握一下。看懂即可,能自己实现一个位图结构最好

重要程度:6

四种算法思想

可以放到最后,但是一定要掌握!
目标:

能实现 Leetcode 上 Medium 难度的题目

重要程度:10