01数据结构与算法简介

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

基本概念

什么是数据结构?什么是算法?

从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。以图书馆储藏书籍为例,为了方便查找,图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号,就是书籍这种“数据”的存储结构。那我们如何来查找一本书呢?有很多种办法,你当然可以一本一本地找,也可以先根据书籍类别的编号,是人文,还是科学、计算机,来定位书架,然后再依次查找。笼统地说,这些查找方法都是算法。

从狭义上讲,是指某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。

数据结构和算法关系

那数据结构和算法有什么关系呢?为什么大部分书都把这两个东西放到一块儿来讲呢?

这是因为,数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。 因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。

比如,因为数组具有随机访问的特点,常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构,二分查找算法就无法工作了,因为链表并不支持随机访问。

数据结构是静态的,它只是组织数据的一种方式。如果不在它的基础上操作、构建算法,孤立存在的数据结构就是没用的。

如何学习这门课

总结来说一句话:要有好的学习方法,抓住学习的重点。

好的学习方法

要有好的学习方法。对于对于每个概念和实现过程,都要知道”是什么“、”为什么“、”怎么做“。在学习数据结构和算法的过程中,你也要注意,不要只是死记硬背,不要为了学习而学习,而是要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”

抓住学习的重点

想要学习数据结构与算法,首先要掌握一个数据结构与算法中最重要的概念——复杂度分析

这个概念究竟有多重要呢?可以这么说,它几乎占了数据结构和算法这门课的半壁江山,是数据结构和算法学习的精髓。

数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,因此,我们就需要一个考量效率和资源消耗的方法,这就是复杂度分析方法。

搞定复杂度分析,下面就要进入数据结构与算法的正文内容了。

为了让你对数据结构和算法能有个全面的认识,我画了一张图,里面几乎涵盖了所有数据结构和算法书籍中都会讲到的知识点。

img

但是,作为初学者,或者一个非算法工程师来说,你并不需要掌握图里面的所有知识点。很多高级的数据结构与算法,比如二分图、最大流等,这些在我们平常的开发中很少会用到。所以,你暂时可以不用看。我还是那句话,咱们学习要学会找重点。如果不分重点地学习,眉毛胡子一把抓,学起来肯定会比较吃力。

所以,结合我自己的学习心得,还有这些年的面试、开发经验,我总结了20 个最常用的、最基础数据结构与算法,不管是应付面试还是工作需要,只要集中精力逐一攻克这 20 个知识点就足够了。

这里面有 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树;10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

一些技巧

边学边练,适度刷题

“边学边练”这一招非常有用。建议你每周花 1~2 个小时的时间,集中把这周的三节内容涉及的数据结构和算法,全都自己写出来,用代码实现一遍。这样一定会比单纯地看或者听的效果要好很多!

有面试需求的同学,可能会问了,那我还要不要去刷题呢?我个人的观点是可以“适度”刷题,但一定不要浪费太多时间在刷题上。我们学习的目的还是掌握,然后应用。除非你要面试 Google、Facebook 这样的公司,它们的算法题目非常非常难,必须大量刷题,才能在短期内提升应试正确率。如果是应对国内公司的技术面试,即便是 BAT 这样的公司,你只要彻底掌握这个专栏的内容,就足以应对。

多问、多思考、多互动

学习最好的方法是,找到几个人一起学习,一块儿讨论切磋,有问题及时寻求老师答疑。

打怪升级学习法

学习的过程中,我们碰到最大的问题就是,坚持不下来。

游戏你肯定玩过吧?为什么很多看起来非常简单又没有乐趣的游戏,你会玩得不亦乐乎呢?这是因为,当你努力打到一定级别之后,每天看着自己的经验值、战斗力在慢慢提高,那种每天都在一点一点成长的成就感就不由自主地产生了。

所以,我们在枯燥的学习过程中,也可以给自己设立一个切实可行的目标,就像打怪升级一样。比如,每节课后都写一篇学习笔记或者学习心得;或者你还可以每节课都找一下我讲得不对、不合理的地方……诸如此类,你可以总结一个适合你的“打怪升级攻略”。如果你能这样学习一段时间,不仅能收获到知识,你还会有意想不到的成就感。因为,这其实帮你改掉了一点学习的坏习惯。这个习惯一旦改掉了,你的人生也会变得不一样。

沉淀法

知识需要沉淀,不要想试图一下子掌握所有。

在学习的过程中,一定会碰到“拦路虎”。如果哪个知识点没有怎么学懂,不要着急,这是正常的。因为,想听一遍、看一遍就把所有知识掌握,这肯定是不可能的。学习知识的过程是反复迭代、不断沉淀的过程。

如果碰到“拦路虎”,你可以尽情地在留言区问我,也可以先沉淀一下,过几天再重新学一遍。所谓,书读百遍其义自见,我觉得是很有道理的!

推荐书单

针对不同层次、不同语言的同学,分别推荐了不同的书。

针对入门的趣味书

《大话数据结构》 这本书最大的特点是,它把理论讲得很有趣,不枯燥。而且每个数据结构和算法,作者都结合生活中的例子进行了讲解, 能让你有非常直观的感受。虽然这本书有 400 多页,但是花两天时间读完,应该是没问题的。如果你之前完全不懂数据结构和算法,可以先从这本书看起。

《算法图解》 跟《大话数据结构》走的是同样的路线,就像这本书副标题写的那样,“像小说一样有趣的算法入门书”,主打“图解”,通俗易懂。它只有不到 200 页,所以内容比较少。作为入门,看看这本书,能让你对数据结构和算法有个大概的认识。

针对特定编程语言的教科书

这里推荐《数据结构和算法分析》。国内外很多大学都拿这本书当作教材。这本书非常系统、全面、严谨,而且又不是特别难,适合对数据结构和算法有些了解,并且掌握了至少一门编程语言的同学。而且,这个作者也很用心。他用了三种语言,写了三个版本,分别是:《数据结构与算法分析 :C 语言描述》《数据结构与算法分析:C++ 描述》《数据结构与算法分析:Java 语言描述》。

如果你熟悉的是 Python 或者 JavaScript,可以参考《数据结构与算法 JavaScript 描述》《数据结构与算法:Python 语言描述》 。

img

面试必刷的宝典

算法对面试很重要,很多人也很关心。这里推荐几本有益于面试的书籍,分别是:《剑指 offer》《编程珠玑》《编程之美》。

从《剑指 offer》这本书的名字就可以看出,作者的写作目的非常明确,就是为了面试。这本书几乎包含了所有常见的、经典的面试题。如果能搞懂这本书里的内容,应付一般公司的面试应该不成问题。

《编程珠玑》这本书的豆瓣评分非常高,有 9 分。这本书最大的特色就是讲了很多针对海量数据的处理技巧。这个可能是其他算法书籍很少涉及的。面试的时候,海量数据处理的问题也是经常会问的,特别是校招面试。不管是开拓眼界,还是应付面试,这本书都很值得一看。

《编程之美》这本书有多位作者,其中绝大部分是微软的工程师,所以书的质量很有保证。不过,这里面的算法题目稍微有点难,也不是很系统,这也是我把它归到面试这一部分的原因。如果你有一定基础,也喜欢钻研些算法问题,或者要面试 Google、Facebook 这样的公司,可以拿这本书里的题,先来自测一下。

经典大部头

很多人一提到算法书就会搬出《算法导论》和《算法》。这两本确实非常经典,但是都太厚了,看起来比较费劲,估计很少有人能坚持全部看下来。如果你想更加深入地学一学数据结构和算法,还是强烈建议你看看。

《算法导论》这本书的章节安排不是循序渐进的,里面充斥着各种算法的正确性、复杂度的证明、推导,数学公式比较多,一般人看起来会比较吃力。所以,作为入门书籍,并不是很推荐。

《算法》这本书也是一本经典大部头,不过它比起《算法导论》来要友好很多,更容易看懂,更适合初学者入门。但是这本书的缺点也很明显,就是内容不够全面,比如动态规划这么重要的知识点,这本书就没有讲。对于数据结构的东西,它讲的也不多,基本就是偏重讲算法。

殿堂级经典

说到殿堂级经典书,如果《计算机程序设计艺术》称第二,我想没人敢称第一。这套书的深度、广度、系统性、全面性是其他所有数据结构和算法书籍都无法相比的。但是,如果你对算法和数据结构不是特别感兴趣,没有很好的数学、算法、计算机基础,想要把这套书读完、读懂是比较难的。你可以把它当作你算法学习的终极挑战。

闲暇阅读

再推荐几本适合闲暇时间阅读的书:《算法帝国》《数学之美》《算法之美》。这些书共同的特点是,都列举了大量的例子,非常通俗易懂。夸张点说,像《算法帝国》,文科生都能读懂。当你看这些书的时候,你常常会深深感受到算法的力量,被算法的优美之处折服。即便不是从事 IT 工作的,看完这几本书也可以开拓眼界。

学习指导手册

这次专栏有简单的数组、链表、栈、队列这些基础内容,也有红黑树、BM、KMP 这些难度较大的算法。为了给不同程度的同学一份具体、明确、有效的学习指导。下面每个知识点的难易程度、需要你掌握到什么程度、具体如何来学习。

先给出一个大致的学习路线。

img

下面针对每个知识点,逐一解释。

复杂度分析

必须要牢牢掌握两节复杂度分析课程,基本上要做到,简单代码能很快分析出时间、空间复杂度;对于复杂点的代码,比如递归代码,也要掌握专栏中讲到的两种分析方法:递推公式和递归树。

  • 难易程度:Medium
  • 是否重点:10 分
  • 掌握程度:在不看作者的分析的情况下,能自行分析专栏中大部分数据结构和算法的时间、空间复杂度

数组、栈、队列

内容简单,但一定要掌握。

  • 难易程度:Easy
  • 是否重点:8 分
  • 掌握程度:能自己实现动态数组、栈、队列

链表

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

  • 难易程度:Medium
  • 是否重点:9 分掌握程度:
  • 能轻松写出经典链表题目代码

递归

对于初学者,递归代码非常难掌握。但必要要跨过这个坎。后面讲的很多数据结构和算法的代码实现,都要用到递归。

递归相关的理论知识也不多,所以还是要多练。可以先在网上找些简单的题目练手,比如斐波那契数列、求阶乘等,然后再慢慢过渡到更加有难度的,比如归并排序、快速排序、二叉树的遍历、求高度,最后是回溯八皇后、背包问题等。

  • 难易程度:Hard
  • 是否重点:10 分
  • 掌握程度:轻松写出二叉树遍历、八皇后、背包问题、DFS 的递归代码

排序、二分查找

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

  • 难易程度:Easy
  • 是否重点:7 分
  • 掌握程度:能自己把各种排序算法、二分查找及其变体代码写一遍就可以了

跳表

初学者并不需要非要掌握跳表。所以无精力,这一章可以直接跳过。

  • 难易程度:Medium
  • 是否重点:6 分
  • 掌握程度:初学者可以先跳过。如果感兴趣,看懂专栏内容即可,不需要掌握代码实现

散列表

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

  • 难易程度:Medium
  • 是否重点:8 分
  • 掌握程度:对于初学者来说,自己能代码实现一个拉链法解决冲突的散列表即可

哈希算法

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

  • 难易程度:Easy
  • 是否重点:3 分
  • 掌握程度:可以暂时不看

二叉树

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

  • 难易程度:Medium
  • 是否重点:9 分
  • 掌握程度:能代码实现二叉树的三种遍历算法、按层遍历、求高度等经典二叉树题目

红黑树

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

  • 难易程度:Hard
  • 是否重点:3 分
  • 掌握程度:初学者不用把时间浪费在上面

B+ 树

虽然 B+ 树也算是比较高级的一种数据结构了,但是对初学者来说,也不是重点。有时候面试的时候还是会问的,所以这一部分内容,你能看懂专栏里的讲解就可以了。

  • 难易程度:Medium
  • 是否重点:5 分
  • 掌握程度:可看可不看

堆与堆排序

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

  • 难易程度:Medium
  • 是否重点:8 分
  • 掌握程度:能代码实现堆、堆排序,并且掌握堆的三种应用(优先级队列、Top k、中位数)

图的表示

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

  • 难易程度:Easy
  • 是否重点:8 分
  • 掌握程度:理解图的三种表示方法(邻接矩阵、邻接表、逆邻接表),能自己代码实现

深度广度优先搜索

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

  • 难易程度:Hard
  • 是否重点:8 分
  • 掌握程度:能代码实现广度优先、深度优先搜索算法

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

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

  • 难易程度:Hard
  • 是否重点:5 分
  • 掌握程度:有时间再看,暂时可以不看

字符串匹配(BF、RK)

BF 非常简单,RK 稍微复杂点,但都不难。这个最好还是掌握下。

  • 难易程度:Easy
  • 是否重点:7 分
  • 掌握程度:能实践 BF 算法,能看懂 RK 算法

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

这三个算法都挺难的,对于算法有一定基础的人来说,看懂也不容易。所以,对于初学者来说,千万别浪费时间在这上面。即便有余力,看懂就好了,不用非得能自己实现。

  • 难易程度:Hard
  • 是否重点:3 分
  • 掌握程度:初学者不用把时间浪费在上面

字符串匹配(Trie)

这个还是要能看懂,不过不需要能代码实现。有些面试官喜欢考这个东西,主要是结合应用场景来考察,只是看你知不知道要用 Trie 树这个东西。

  • 难易程度:Medium
  • 是否重点:7 分
  • 掌握程度:能看懂,知道特点、应用场景即可,不要求代码实现

位图

位图不是重点,如果有余力最好掌握一下。

  • 难易程度:Easy
  • 是否重点:6 分
  • 掌握程度:看懂即可,能自己实现一个位图结构最好

四种算法思想

这个是重点,也是难点。贪心、分治、回溯、动态规划,每一个都不简单,其中动态规划又是最难、最烧脑的。要应付 FLAG 这样公司的面试,必须拿下这块内容。但是呢,学习要循序渐进,这块能内容的学习可以放到最后,做个长时间的学习计划来攻克。这块内容理论的东西不多,要想真的掌握,还是要大量刷题。

  • 难易程度:Hard
  • 是否重点:10 分
  • 掌握程度:可以放到最后,但是一定要掌握!做到能实现 Leetcode 上 Medium 难度的题目

数据结构与算法学习框架

img

img

img

img

参考

01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
《数据结构与算法之美》学习指导手册
不定期福利第一期 | 数据结构与算法学习书单

------ 本文结束------
坚持原创技术分享,您的支持将鼓励我继续创作!

欢迎关注我的其它发布渠道