当前位置:   article > 正文

原创 | 初学者友好!最全算法学习资源汇总(附链接)

初学者leetcode和牛客

在计算机发展飞速的今天,也许有人会问,“今天计算机这么快,算法还重要吗?”其实永远不会有太快的计算机,因为我们总会想出新的应用。虽然在摩尔定律的作用下,计算机的计算能力每年都在飞快增长,价格也在不断下降。可我们不要忘记,需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面,随着研究手段的进步,数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别,都需要极大的计算量。在网络时代,越来越多的挑战需要靠卓越的算法来解决。

总之,算法是计算机科学领域最重要的基石之一,算法工程师也是数据科学领域最重要的岗位之一,对于一些只掌握新的语言、技术、标准而不掌握算法的小伙伴,是不可能成为高手的。因此,今天我们整理出一些经典算法以及相关学习资源,欢迎大家收藏并转发哦。

 

一、经典算法

 

1、排序算法

 

冒泡算法

 

冒泡排序,有时也称为下沉排序,是一种简单的排序算法,它反复遍历要排序的列表,比较每对相邻的项目,如果它们的顺序错误则交换它们。重复传递列表,直到不需要交换,这表明列表已排序。

用python代码实现:

https://www.toptal.com/developers/sorting-algorithms/bubble-sort

 

归并排序

归并排序(Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

用python代码实现:

https://www.toptal.com/developers/sorting-algorithms/merge-sort

 

鸡尾酒排序

鸡尾酒排序,也叫双向冒泡排序(Bidirectional Bubble Sort)等。这是冒泡排序的一种变体。不同之处在于,冒泡排序是从低到高比较序列里的每个元素,而鸡尾酒排序从两个方向(低到高、高到低)来回排序,效率更高。

用python代码实现:

https://en.wikipedia.org/wiki/Cocktail_shaker_sort

 

插入排序

 

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

用python代码实现:

https://www.toptal.com/developers/sorting-algorithms/insertion-sort

 

快速排序

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),简称快排,最早由Tony Hoare爵士设计,它的基本思想是将待排序列分为两半,左边的一半总是“小的”,右边的一半总是“大的”,这一过程不断递归持续下去,直到整个序列有序。说起这位Tony Hoare爵士,快速排序算法其实只是他不经意间的小小发现而已,他对于计算机贡献主要包括形式化方法理论,以及ALGOL60 编程语言的发明等,他也因这些成就获得1980 年图灵奖。

用python代码实现:

https://www.toptal.com/developers/sorting-algorithms/quick-sort

 

堆排序

堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。

用python代码实现:

https://www.toptal.com/developers/sorting-algorithms/heap-sort

 

归并排序

归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

用python代码实现:

https://www.toptal.com/developers/sorting-algorithms/merge-sort

 

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

用python代码实现:

https://www.toptal.com/developers/sorting-algorithms/selection-sort

 

希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的:插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

用python代码实现:

https://www.toptal.com/developers/sorting-algorithms/shell-sort

 

2、搜索算法

 

二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半,时间复杂度为Ο(logn) 。

 

BFPRT(线性查找算法)

 

BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。

 

算法步骤:

1.将n个元素每5个一组,分成n/5(上界)组。

2.取出每一组的中位数,任意排序方法,比如插入排序。

3.递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

4.用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。

5.若i==k,返回x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k小的元素。

 

终止条件:n=1时,返回的即是i小元素。

 

DFS(深度优先搜索)

 

深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

 

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

 

深度优先遍历图算法步骤:

1.访问顶点v;

2.依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

3.若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

 

上述描述可能比较抽象,举个实例:

 

DFS在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;再从w1出发,访问与w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。

 

接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。

 

BFS(广度优先搜索)

 

广度优先搜索算法(Breadth-First-Search),是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。

 

如果所有节点均被访问,则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

 

算法步骤:

1.首先将根节点放入队列中。

2.从队列中取出第一个节点,并检验它是否为目标。如果找到目标,则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。

3.若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

4.重复步骤2。

 

Dijkstra算法

 

戴克斯特拉算法(Dijkstra’salgorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

 

该算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E表示G中所有边的集合,而边的权重则由权重函数w:E→[0,∞]定义。因此,w(u,v)就是从顶点u到顶点v的非负权重(weight)。

 

边的权重可以想像成两个顶点之间的距离。任两点间路径的权重,就是该路径上所有边的权重总和。已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低权重路径(例如,最短路径)。

 

这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。对于不含负权的有向图,Dijkstra算法是目前已知的最快的单源最短路径算法。

 

算法步骤:

1.初始时令S={V0},T={其余顶点},T中顶点对应的距离值,若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值;若不存在<V0,Vi>,d(V0,Vi)为∞。

2.从T中选取一个其距离值为最小的顶点W且不在S中,加入S。

3.对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值。

重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止。

 

动态规划算法

 

动态规划(Dynamicprogramming)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。

 

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。关于动态规划最经典的问题当属背包问题。

算法步骤:

1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。

最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。

动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。

 

朴素贝叶斯分类算法

 

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理,就是在各种条件的存在不确定,仅知其出现概率的情况下,如何完成推理和决策任务。

 

概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的,即假设样本每个特征与其他特征都不相关。朴素贝叶斯分类器依靠精确的自然概率模型,在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中,朴素贝叶斯模型参数估计使用最大似然估计方法,换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。尽管是带着这些朴素思想和过于简单化的假设,但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

 

二、算法学习资源项目推荐

 

1、和小浩一起学算法

项目介绍:该项目包括作者小浩撰写的一本三十万字的算法题典,以及他收集整理的编程类思维导图、大厂面经,和不同语言编程电子书等。在这本算法题典中,作者对一些经典算法做了讲解。讲解的形式是首先给出一道应用该算法的题目,先给出一段文字情境描述,然后给出输入和输出的示例。在给出题解之前,作者建议读者自己思考实现一下,最后,作者还给出了解决原题目的代码。算法题解这部分适用于计算机科学的初学者阅读,用题目和图画的方式讲解算法,易于理解,且能让初学者印象深刻。读者借助编写代码实现算法还能做到举一反三,这是打好算法基础的关键;项目中另一个很吸引人的部分是大厂面试题目汇总。作为拿到大厂 offer 的敲门砖,大厂面试经验一直受到追捧。但大部分的面试经验和算法教程一样,在网络上零散分布,且不按话题分类。而在本项目中,作者整理了 100 篇面试经验,并且按照面试题目涉及的知识点进行分类。不仅适合求职者临阵磨枪,也适合在校生阅读学习。

项目地址:

https://github.com/geekxh/hello-algorithm

 

2、算法面试集合

项目介绍:该项目涵盖2018、2019 的校招/春招/秋招/算法/机器学习(机器学习)/深度学习(深度学习)/自然语言处理(NLP)/ C / C ++ / Python /面试笔记。

项目地址:

https://github.com/yuquanle/Algorithm_Interview_Notes-Chinese

 

3、Competitive-Programming-Docs

项目介绍:这个项目是一个总资源集,内容非常全面,包含算法竞赛论文,课件,文档,笔记,平台等资料。

项目地址:

https://github.com/LzyRapx/Competitive-Programming-Docs

 

4、【算法与数据结构】+一点点ACM从入门到进阶吐血整理推荐书单(珍藏版)

项目介绍:该项目收集了关于算法与数据结构的多本电子书。

项目地址:

https://pymlovelyq.github.io/posts/32a7f0eb/

 

5、负重前行,前端工程师如何系统练习数据结构和算法?【上】

项目介绍:作者详细提供了系统练习数据结构和算法的方法论。

项目地址:

https://juejin.im/post/6844904061947346957

 

6、五分钟学算法:算法与数据结构文章详细分类与整理!

项目介绍:该项目包含10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树,以及10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

项目地址:

https://www.cxyxiaowu.com/7072.html

 

7、算法与面试之-如何准备算法面试

项目介绍:主要介绍算法面试的一些问题、以及如何准备算法面试。

项目地址:

https://juejin.im/post/6844903621105041416

 

三、算法练习网站

1、LeetCode

估计 leetcode(力扣)大家都很熟悉了,很多国内外的程序员在上面刷题,难度从 Easy、Medium 至 Hard 都有,据说很多面试官都会从中挑选各种题目,号称大厂的筛码工。

2、LintCode

国外算法练习网站

3、Educative

国外算法练习网站

4、牛客网

牛客网作为国内内容超级丰富的 IT 题库,各种东西看的我眼花缭乱,题库+面试+学习+求职+讨论 360 度无死角服务,堪称"互联网求职神器"。它好就好在不只是一个刷题的平台,还是一个交流学习的平台。

5、hihoCoder

网站的技术团队来自于原北大 POJ 的开发团队,至于 POJ 会在后面的篇章中介绍,反正膜拜就完事了。一些知名的大厂比如微软、百度、腾讯、网易等会在上面举办在线编程比赛,风格倒是和 ACM 比赛类似。

6、HDU

杭电(杭州电子科技大学)的 OJ 大概是国内最火的几个 OJ 之一了,现在上面大概有接近 6k 的题量,网上有很多的刷题顺序,刷题指南。

7、POJ

作为国内最火的几大 OJ 之一,现在上面有 3k+ 的题量,关于 POJ 的刷题指南网上更是很多。

 

四、网络视频课程

1、300分钟搞定数据结构与算法

LeetCode 官方国内唯一合作课程,leetCode刷题秘籍独家揭秘,专注于面试场景,全程动态动画教学。

2、数据结构精讲:从原理到实战

Google资深工程师带你玩转数据结构,搞懂数据结构底层原理,打败 97% 的程序员。

3、机器学习入门21讲

中科院博士带你轻松入门AI。

4、麻省理工学院公开课:算法导论

课程主题包含了:排序、搜寻树、堆积及散列;各个击破法、动态规划、偿还分析、图论算法、最短路径、网络流、计算几何、数字理论性算法;多项式及矩阵的运算;高速缓存技术及并行运算。

5、中国大学MOOC-数据结构

国内关于数据结构非常经典的课程。

 

五、算法书籍推荐

1、啊哈!算法(豆瓣评分7.7)

这是一本充满智慧和趣味的算法入门书。没有枯燥的描述,没有难懂的公式,一切以实际应用为出发点,通过幽默的语言配以可爱的插图来讲解算法。你更像是在阅读一个个轻松的小故事或是在玩一把趣味解谜游戏,在轻松愉悦中便掌握算法精髓,感受算法之美。

2、算法图解(豆瓣评分8.4)

图文并茂,以让人容易理解的方式阐释了算法,旨在帮助程序员在日常项目中更好地发挥算法的能量。书中的前三章将帮助你打下基础,带你学习二分查找、大O表示法、两种基本的数据结构以及递归等。余下的篇幅将主要介绍应用广泛的算法,具体内容包括:面对具体问题时的解决技巧,比如,何时采用贪婪算法或动态规划;散列表的应用;图算法;K最近邻算法。

3、大话数据结构(豆瓣评分7.9)

《大话设计模式》作者程杰潜心三年推出的扛鼎之作,以一个计算机教师教学为场景,讲解数据结构和相关算法的知识。通篇以一种趣味方式来叙述,大量引用了各种各样的生活知识来类比,并充分运用图形语言来体现抽象内容,对数据结构所涉及到的一些经典算法做到逐行分析、多算法比较。与市场上的同类数据结构图书相比,本书内容趣味易读,算法讲解细致深刻,是一本非常适合自学的读物。

4、算法帝国(豆瓣评分7.2)

本书是《纽约时报》畅销书作者的又一力作,通过一个又一个引人入胜的故事,向读者介绍了算法掌控世界的真实情况,揭示了“机器人革命”是如何悄悄地在我们身边发生的。本书适合任何对科技史、信息革命、算法原理、数据分析感兴趣的读者。

5、算法之美(豆瓣评分7.5)

这本书告诉我们如何更有效地利用直觉、什么时候应该把选择权交给命运、无所适从的时候应该如何做出选择,以及如何有效地与他人保持联系。从找配偶到找停车位,从组织管理个人邮箱的收件箱到理解人类记忆的作用原理,这本书把计算机科学的智慧转化为人类生活的策略,引导我们做出明智的选择。

6、编程珠玑(豆瓣评分9.1)

本书是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley 以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程生涯中至关重要的。本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序,对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述,为复杂的编程问题提供了清晰而完备的解决思路。本书对各个层次的程序员都具有很高的阅读价值。

7、算法谜题(豆瓣评分7.5)

本书可以为对算法感兴趣的广大读者提供系统丰富而实用的资料,能够帮助读者提升高阶算法思维能力。本书适合计算机专业的高校教师和学生,想要培养和训练算法思维和计算思维的IT专业人士,以及在准备面试的应聘者和面试官阅读参考。

8、算法设计与分析基础(豆瓣评分8.7)

本书十分适合用作算法设计和分析的基础教材,也适合任何有兴趣探究算法奥秘的读者使用,只要读者具备数据结构和离散数学的知识即可。

9、数据结构与算法分析(豆瓣评分8.5)

本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。随着计算机速度的不断增加和功能的日益强大,人们对有效编程和算法分析的要求也不断增长。本书把算法分析与最有效率的Java程序的开发有机地结合起来,深入分析每种算法,内容全面、缜密严格,并细致讲解精心构造程序的方法。

10、算法详解(卷1)——算法基础(豆瓣评分8.8)

本书为对算法感兴趣的广大读者提供了丰富而实用的资料,能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生,想要培养和训练算法思维和计算思维的IT专业人士,以及在准备面试的应聘者和面试官阅读参考。

11、算法导论(原书第3版)(豆瓣评分9.2)

本书将严谨性和全面性融为一体,深入讨论各类算法,并着力使这些算法的设计和分析能为各个层次的读者接受。

12、计算机程序设计艺术(豆瓣评分9.8)

这本书首先介绍编程的基本概念和技术,然后详细讲解信息结构方面的内容,包括信息在计算机内部的表示方法、数据元素之间的结构关系,以及有效的信息处理方法。此外,书中还描述了编程在模拟、数值方法、符号计算、软件与系统设计等方面的初级应用。此第3版增加了数十项简单但重要的算法和技术,并根据当前研究发展趋势在数学预备知识方面做了大量修改。

13、算法第 4 版(豆瓣评分9.3)

《算法(英文版•第4版)》作为算法领域经典的参考书,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行了论述。第4版具体给出了每位程序员应知应会的50个算法,提供了实际代码,而且这些Java代码实现采用了模块化的编程风格,读者可以方便地加以改造。本书配套网站提供了本书内容的摘要及更多的代码实现、测试数据、练习、教学课件等资源。

14、算法引论(豆瓣评分9.1)

这本书是国际算法大师乌迪·曼博(Udi Manber)博士撰写的一本享有盛誉的著作。本书的特色有二,旨在提高读者的问题求解能力,使读者能够理解算法设计的过程和思想:一是强调算法设计的创造性过程,注重算法设计背后的创造性思想,而不拘泥于某个具体算法的详细讨论;二是将算法设计类比于定理归纳证明,揭示了算法设计的基本思想和本质。

15、剑指offer(豆瓣评分8.3)

这本书剖析了50个典型的程序员面试题,从基础知识、代码质量、解题思路、优化效率和综合能力五个方面系统整理了影响面试的5个要点。是面试必读书籍之一。

16、编程之美(豆瓣评分8.4)

这本书收集了约60道算法和程序设计题目,这些题目大部分在近年的笔试、面试中出现过,或者是被微软员工热烈讨论过。作者试图从书中各种有趣的问题出发,引导读者发现问题,分析问题,解决问题,寻找更优的解法。

 

编辑:于腾凯

校对:林亦霖


恭喜微信名称为 贾恩东、C@1M1n9、sober  的三位读者获得赠书《集成学习:基础与算法》!(留言点赞数量统计截止时间为2020年8月24日16:30)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/算法创新者/article/detail/62315
推荐阅读
相关标签
  

闽ICP备14008679号