不 BB,直接上干货,非科班出生,毕业工作后才开始学算法,到目前学了 4 年 !!!

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


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

掌握了这些基础的数据结构和算法,再学更加复杂的数据结构和算法,就会非常容易、非常快。

如果觉得不错,别忘了双击点个赞哦。

在这里也送大家一本帮助我拿到BAT 等一线大厂 offer 的算法笔记,是一位阿里大神写的,对于算法薄弱或者需要提高的同学都十分受用,算法一定是计算机学习的重中之重:

貌似手机端打开连接有的会出现问题,可以点击这个总结看看:

1、复杂度分析

看动画轻松理解时间复杂度(一)

看动画轻松理解时间复杂度(二)

冰与火之歌:「时间」与「空间」复杂度

每个程序员都应该收藏的算法复杂度速查表

2、基本算法思想

五分钟了解一下什么是「贪心算法 」

有了四步解题法模板,再也不害怕动态规划!

(进阶版)有了四步解题法模板,再也不害怕动态规划!

(再进阶版)有了四步解题法模板,再也不害怕动态规划!

浅谈什么是分治算法

看动画轻松理解「递归」与「动态规划」

浅谈什么是动态规划以及相关的「股票」算法题

深度解析「正则表达式匹配」:从暴力解法到动态规划

3、排序算法

「多图警告」手撕排序算法 – iOS进阶必备

十大经典排序算法动画与解析,看我就够了!(配代码完全版)

这或许是东半球分析十大排序算法最好的一篇文章

4、搜索

几道和「广度优先搜索」有关的算法面试题

初识广度优先搜索与解题套路

从简单二叉树问题重新来看深度优先搜索

5、查找

二分查找算法详解

一网打尽!二分查找解题模版与题型全面解析

面试官,我会写二分查找法!对,没有 bug 的那种!

6、字符串匹配

动画:BM 算法中的坏字符规则与好后缀规则

动画:七分钟理解什么是KMP算法

动画:什么是 BF 算法 ?

动态规划之 KMP 算法详解(配代码版)

7、线性表

如何高效对有序数组/链表去重?

超详细!详解一道高频算法题:数组中的第 K 个最大元素

一道简单的数组遍历题,加上四个条件后感觉无从下手

数组特性的妙用!如何找到「缺失的第一个正数」

剑指 offer 第一题:二维数组中的查找

动画:什么是单调栈?

在数据结构中穿针引线:链表实现栈和队列

从简单的线性数据结构开始:栈与队列

五分钟学算法小知识:用栈实现队列/用队列实现栈

几道和「堆栈、队列」有关的面试算法题

超详细!图解「合并 K 个排序链表」

动画:面试如何轻松手写链表?

LeetCode 上最难的链表算法题,没有之一!

链表算法面试问题?看我就够了!

看动画轻松理解「链表」实现「LRU缓存淘汰算法」

从简单的线性数据结构开始:穿针引线的链表(一)

在数据结构中穿针引线:链表实现栈和队列

8、散列表

五分钟速读:什么是散列表(哈希表)?

什么是哈希洪水攻击(Hash-Flooding Attack)?

几道和散列(哈希)表有关的面试题

如何判断一个元素在亿级数据中是否存在?

9、树

面试前准备:二叉树高频面试题和答案

懵逼树上懵逼果:学习二分搜索树

LeetCode 二叉树问题小总结

从简单二叉树问题重新来看深度优先搜索

几道和「二叉树」有关的算法面试题

详解什么是平衡二叉树(AVL)(修订补充版)

【面试现场】为什么 MySQL 数据库要用B+树存储索引?

字典树概念与题型解析

面试官:为什么 MySQL 的索引要使用 B+ 树,而不是其它树?比如 B 树?

心里没点 B 树。。。

数据结构与算法——最小生成树

植树节,程序猿种的那些树

数据结构与算法——2-3-4树

数据结构与算法——2-3树

看动画轻松理解「Trie树」

10、图

浅谈什么是图拓扑排序

数据结构与算法——图论基础与图存储结构

数据结构与算法:三十张图弄懂「图的两种遍历方式」

数据结构与算法——图最短路径

总结

学习数据结构和算法的过程,是非常好的思维训练的过程,所以,千万不要被动地记忆,要多辩证地思考,多问为什么。

如果你一直这么坚持做,你会发现,等你学完之后,写代码的时候就会不由自主地考虑到很多性能方面的事情,时间复杂度、空间复杂度非常高的垃圾代码出现的次数就会越来越少。

你的编程内功就真正得到了修炼。

在这里向大家推荐一下我的微信公众号:五分钟学算法(ID:CXYxiaowu),专注算法技术分享,包括算法面试题、数据结构、LeetCode、图解算法、漫画算法等;每天推送优质技术文章,精彩视频教程以及项目源码下载,致力做一个实用的公众号。


2020 年 01 月 13 日补充:

我再推荐一些算法书籍的选择给大家参考一下。

入门系列

入门的同学,我建议你不要过度追求上去就看经典书。

不要一来就拿着《算法导论》开始啃,初学就去啃这些书肯定会很费劲。你一旦啃不下来,挫败感就会很强。

然后就放弃学算法了。

所以,入门的同学,我建议你找一些比较容易看的书来看,比如《大话数据结构》和《算法图解》。

不要太在意书写得深浅,重要的是能不能坚持看完。

《大话数据结构》 这本书最大的特点是,它把理论讲得很有趣,不枯燥。而且每个数据结构和算法,作者都结合生活中的例子进行了讲解, 能让你有非常直观的感受。

虽然这本书有 400 多页,但是花两天时间读完,应该是没问题的。

如果你之前完全不懂数据结构和算法,可以先从这本书看起。

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

作为入门,看看这本书,能让你对数据结构和算法有个大概的认识。

当然,这些入门书共同的问题是,缺少细节,不够系统,也不够严谨。

所以,如果你想要系统地学数据结构和算法,看这两本书肯定是不够的。

基础系列

通过基本入门算法书的调教,你已经逐渐体会到了算法的魅力,现在正是时候踏入基础系列算法的领域!!!

这些书籍需要你费点心思去阅读。

很多同学在学习的过程中,看到一篇算法科普文章经常会有这样的想法。

哎呀,要是文章的代码是 Java 语言就好了呀。

哎呀,要是文章的代码是 Python 语言就好了呀。

虽然代码并不会很严重影响阅读,但还是有很多强迫症的同学喜欢看到文章的解释代码是自己擅长的。

我这里推荐《数据结构和算法分析》,这本书非常系统、全面、严谨,而且又不是特别难,适合对数据结构和算法有些了解,并且掌握了至少一门编程语言的同学。而且,这个作者也很用心。

他用了三种语言,写了三个版本,分别是:《数据结构与算法分析 :C 语言描述》《数据结构与算法分析:C++ 描述》《数据结构与算法分析:Java 语言描述》。

面试实战系列

大家都知道,对于程序员来说很大程度上算法就是为了应付面试的。

所以,推荐三本有益于面试的书籍,分别是:《剑指 offer》《编程珠玑》《编程之美》。

《剑指 offer》这本书的目的非常明确,就是为了面试。

这本书几乎包含了所有常见的、经典的面试题。如果能搞懂这本书里的内容,应付一般公司的面试应该不成问题。

我做了一个 图解《剑指 offer》的小程序,应该能帮助你学习,感兴趣的可以在微信搜索 图解剑指offer。

我也在 B 站录制了一些图解剑指 offer 的免费视频课程,感兴趣的也可以看看,每个视频控制在5分钟以内。

《编程珠玑》这本书的豆瓣评分非常高,有 9 分。

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

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


2020年05月31日补充:数据结构与算法在平时工作中的作用。

正如 N.Wirth 教授所说的: 数据结构+ 算法=程序

遇到一个实际问题,充分利用所学的数据结构,将数据及其之间的关系有效地存储在计算机中,然后选择合适的算法策略,并用程序高效实现。

这句话可能有点抽象,我举个例子给你们解释一下

在工作过程中,我们多多少少都接触过 OAuth2 ,在使用 OAuth2 授权的时候,通常应用会弹出一个类似这样的信息:

1) 获取用户基本信息接口

2) 获取用户列表接口

3) 用户分组管理接口

。。。


微信获取授权

思考一下,如果让你设计数据库,应该怎么设计信息存储权限?

如何你熟练掌握了各种数据结构的特点的话,那自然而然想到使用 bitmap 来存储权限。

我们把权限划分成最小粒度之后,每一个 bit 都它的含义, 例如我们把权限划分为以下几种:

  • 获取你的头像、性别、昵称等基本用户信息
  • 以你的身份发布微博
  • 获取你的好友列表
  • 获取你的朋友圈信息

每勾选一个选项,就代表着这个权限被授权,为了保证可扩展性,我们使用一个 uint64 来保存这些 bit ,也就是说,我们一共可以划分 64 种细分权限,然后对这些权限进行组合。

例如,第一个 bit 如果设置了,那么就代表可以获取你的昵称、头像、地区、性别等基本用户信息, 第二个 bit 如果设置了,就可以用你的身份发状态。

数据结构的实际作用还有挺多,感兴趣的可以搜索以下知识点:

  1. 二叉树搜索用于中断处理、登记缓存查找等
  2. 哈希表,用于实现索引节点、文件系统完整性检查等
  3. 红黑树用于调度、虚拟内存管理、跟踪文件描述符和目录条目等
  4. Radix树,用于内存管理、NFS相关查找和网络相关的功能
  5. ……

上面这些例子是关于数据结构的,我再举一个算法的例子,如果有帮助,不妨点个赞收藏一下,好的内容值得肯定。

同样的也来思考一个问题:计算机的缓存容量无论再大,缓存满了还是要删除一些内容,给新内容腾位置。

那么删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。那么,什么样的数据,我们判定为「有用的」的数据呢?

这个时候采取的策略就是 LRU 缓存淘汰算法

LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。

具体的关于 LRU 缓存淘汰算法 的介绍可以看我之前写的一篇文章。

补充

再推荐一个阿里朋友的算法刷题的开源项目。

截至 2020 年 11 月,该开源项目配套的网站已经有一百二十万的访问量,在 GitHub 上收获了 8500 颗小星星。


这个开源项目是@halfrost(中文名一缕殇流化隐半边冰,简称霜神)去年刷算法题时整理出的 520 题,每道题都写了解题思路,全部都是 GO 实现的,并且每题都 runtime beats 100% 了。




至于为什么要求每题都 runtime beats 100%

霜神是这样回复的:优化到 beats 100% 才算是把这题做出感觉了。有好几道 Hard 题,可以用暴力解法 AC 了,但只 beats 了 5%,这题就如同没做一样;而且面试中如果给了这样的答案,面试官也不会满意,“还有没有更优解?”。如果通过自己的思考能给出更优解,面试官会更满意一些。

如果你把这些题解都摸透,相信在面试环节你可以从容的回答“还有没有更优解”。


作者介绍:霜神是前阿里巴巴资深后端工程师,业余时间酷爱写博客,目前他的博客已经有 300W+ 的浏览量,是 iOS 开发届的大佬级别人物,霜神为人谦和,上周六我说能不能提供一份离线电子书,方便读者阅读,他立马熬夜研究,修改了好几个版本。

离线版笔记下载地址(已获授权)链接: pan.baidu.com/s/1prMLkr 密码: gjht

离线版笔记下载地址(已获授权): LeetCode – Go 电子书下载

我的专栏:
我的其它高赞回答:

大学四年,算法是我非常注重学习的一门知识。下面是我觉得值得学习的一些算法以及数据结构,当然,并且我也整理一些看过不错的文章给大家,大家也可以留言区补充。如果觉得不错,别忘了点个赞哦。先上图,后详细解说


一、算法最最基础

1、时间复杂度

2、空间复杂度

一般最先接触的就是时间复杂度和空间复杂度的学习了,这两个概念以及如何计算,是必须学的,也是必须最先学的,主要有最大复杂度、平均复杂度等,直接通过博客搜索学习即可。

文章推荐:

算法分析神器—时间复杂度

二、基础数据结构

1、线性表

  • 列表(必学)
  • 链表(必学)
  • 跳跃表(知道原理,应用,最后自己实现一遍)
  • 并查集(建议结合刷题学习)

不用说,链表、列表必须,不过重点是链表。

三分钟基础数据结构:如何轻松手写链表?

以后有面试官问你「跳跃表」,你就把这篇文章扔给他

2、栈与队列

  • 栈(必学)
  • 队列(必学)
  • 优先队列、堆(必学)
  • 多级反馈队列(原理与应用)

特别是优先队列,再刷题的时候,还是经常用到的,队列与栈,是最基本的数据结构,必学。可以通过博客来学习。相关文章:

三分钟基础知识:什么是栈?

二叉堆是什么鬼?

【算法与数据结构】堆排序是什么鬼?

3、哈希表(必学)

  • 碰撞解决方法:开放定址法、链地址法、再次哈希法、建立公共溢出区(必学)
  • 布隆过滤器(原理与应用)

哈希表相关的,推荐通过博客来学习,推荐文章:

Hash冲突之开放地址法

4、树

  • 二叉树:各种遍历(递归与非递归)(必学)
  • 哈夫曼树与编码(原理与应用)
  • AVL树(必学)
  • B 树与 B+ 树(原理与应用)
  • 前缀树(原理与应用)
  • 红黑树(原理与应用)
  • 线段树(原理与应用)

树相关是知识还是挺多的,建议看书,可以看《算法第四版》。相关文章:

高频面试题:什么是B树?为啥文件索引要用B树而不用二叉查找树?

【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。

腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

【面试被虐】游戏中的敏感词过滤是如何实现的?

5、数组

  • 树状数组
  • 矩阵(必学)

树状数组其实我也没学过,,,,

这里给大家推荐一份刷题笔记,里面把各种算法题型以及经验都总结了,把这份笔记突击学习一下,很多算法考察,基本都稳了,给大家看一下目录


下载链接:

三、各种常见算法

1、十大排序算法

  • 简单排序:插入排序、选择排序、冒泡排序(必学)
  • 分治排序:快速排序、归并排序(必学,快速排序还要关注中轴的选取方式)
  • 分配排序:桶排序、基数排序
  • 树状排序:堆排序(必学)
  • 其他:计数排序(必学)、希尔排序

对于十大算法的学习,假如你不大懂的话,那么我还是挺推荐你去看书的,因为看了书,你可能不仅仅知道这个算法怎么写,还能知道他是怎么来的。推荐书籍是《算法第四版》,这本书讲的很详细,而且配了很多图演示,还是挺好懂的。

推荐文章:

必学十大经典排序算法,看这篇就够了(附完整代码/动图/优质文章)(修订版)

2、图论算法

  • 图的表示:邻接矩阵和邻接表
  • 遍历算法:深度搜索和广度搜索(必学)
  • 最短路径算法:Floyd,Dijkstra(必学)
  • 最小生成树算法:Prim,Kruskal(必学)
  • 实际常用算法:关键路径、拓扑排序(原理与应用)
  • 二分图匹配:配对、匈牙利算法(原理与应用)
  • 拓展:中心性算法、社区发现算法(原理与应用)

图还是比较难的,不过我觉得图涉及到的挺多算法都是挺实用的,例如最短路径的计算等,图相关的,我这里还是建议看书的,可以看《算法第四版》。

漫画:什么是 “图”?(修订版)

漫画:深度优先遍历 和 广度优先遍历

漫画:图的 “最短路径” 问题

漫画:Dijkstra 算法的优化

漫画:图的 “多源” 最短路径

3、搜索与回溯算法

  • 贪心算法(必学)
  • 启发式搜索算法:A*寻路算法(了解)
  • 地图着色算法、N 皇后问题、最优加工顺序
  • 旅行商问题

这方便的只是都是一些算法相关的,我觉得如果可以,都学一下。像贪心算法的思想,就必须学的了。建议通过刷题来学习,leetcode 直接专题刷。

4、动态规划

  • 树形DP:01背包问题
  • 线性DP:最长公共子序列、最长公共子串
  • 区间DP:矩阵最大值(和以及积)
  • 数位DP:数字游戏
  • 状态压缩DP:旅行商

我觉得动态规划是最难的一个算法思想了,记得当初第一次接触动态规划的时候,是看01背包问题的,看了好久都不大懂,懵懵懂懂,后面懂了基本思想,可是做题下不了手,但是看的懂答案。一气之下,再leetcdoe专题连续刷了几十道,才掌握了动态规划的套路,也有了自己的一套模板。不过说实话,动态规划,是考的真他妈多,学习算法、刷题,一定要掌握。这里建议先了解动态规划是什么,之后 leetcode 专题刷,反正就一般上面这几种题型。后面有时间,我也写一下我学到的套路,有点类似于我之前写的递归那样,算是一种经验。也就是我做题时的模板,不过感觉得写七八个小时,,,,,有时间就写。之前写的递归文章:为什么你学不会递归?告别递归,谈谈我的一些经验

5、字符匹配算法

  • 正则表达式
  • 模式匹配:KMP、Boyer-Moore

我写过两篇字符串匹配的文章,感觉还不错,看了这两篇文章,我觉得你就差不多懂 kmp 和 Boyer-Moore 了。

字符串匹配Boyer-Moore算法:文本编辑器中的查找功能是如何实现的?

6、流相关算法

  • 最大流:最短增广路、Dinic 算法
  • 最大流最小割:最大收益问题、方格取数问题
  • 最小费用最大流:最小费用路、消遣

这方面的一些算法,我也只了解过一些,感兴趣的可以学习下。

总结

对于上面设计到的算法,我都提供了感觉还不错的文章,建议大家收藏,然后可以利用零碎的时间进行阅读,有些人可能会觉得上面的算法太多,说实话,我觉得不多,特别是对于在校生的,上面涉及到的算法可以不用很懂,但至少得了解。至于书籍的话,如果你连基本数据结构都还不懂的,建议看《数据结构与算法》相关书籍,例如《大话数据结构》、《数据结构与算法分析》。如果你有一定的基础,例如知道链表,栈,队列,那么可以看《算法第四版》,不过这本书是用 Java 实现的,不过我觉得你只要学过 C,那么可以看的懂。

这些算法的学习,虽然你觉得学了没有什么用,但还是那些话,它对你的影响是潜意识的,它可以给你打下很深厚的基础内功,如果你想走的更远,那么我推荐学习,标注必学的,那么我觉得,你是真的需要抽时间来学习下,标注原理与应用的,代表你可以不知道怎么用代码实现,但是必得知道它的实现原理以及应用。

算法的学习没有太多捷径,离不开刷题,刷多了就会有感觉了,这里再给大家推荐一份某大佬的 leetcode 刷题笔记,汇聚了上千道 leetcode 题解,并且代码都是 beat 100%:下载链接:
有收获?希望老铁们来个三连击,给更多的人看到这篇文章

文章来源于互联网:程序员必须掌握哪些算法?

发表评论