登录加入知乎
人工智能
学习方法
程序员应该如何学习算法?
15,857
2,038,542
关注问题
邀请回答
好问题 18
5 条评论
134 个回答
默认排序
知乎用户
2,930 人赞同了该回答
建议千万不要一开始就看《算法导论》,这本书有太多关于算法的数学证明(如果你喜欢这种,那么你就看这本)
我强烈推荐你看看这本:算法(第4版) (豆瓣),作者是高德纳的学生:塞奇威克 (Robert Sedgewick)
去年我在准备校招面试的时候偶然发现这本书,我越看越着迷,书中算法代码主要是用Java编写,里面有大量的图来让你明白例如:排序,查找,树和图的算法运行过程。
这本书的目录编排也很清晰,他就告诉你算法主要就可以分为:排序,查找,图和字符串。从这4个方面可以演化出很多算法。
我觉得最关键是:这本书的作者不但是在告诉你what,而且告诉你why(分析各种算法的优缺点)
—
补充一些我觉得这本书好的地方
比如讲到快速排序,很多书可能讲了快速排序的原理就完了。但这本书就直接讲了原始的快速排序可以改进的地方:1. 在小数组上,切换到插入排序;2. 三取样切分;3. 三向切分的快速排序。
优先队列怎么和排序算法扯上关系呢?其实优先队列就是可以用堆排序来实现,堆排序的时间复杂度和快速排序是一样的,但是实际中为什么堆排序的运行时间要比快速排序多呢?因为这和CPU的Cache命中率有关系,堆排序不符合算法运行的局部性原则
还比如书中2.5节,讲了排序算法的实际用途。
这本书不光告诉你算法的原理,还告诉你算法的用途。
编辑于 2014-08-24
赞同 2930
211 条评论
喜欢收起
继续浏览内容
发现更大的世界
量子位
2020 新知答主
3,603 人赞同了该回答
推荐一份资源:
一位从1998年就开始讲课的老教授Jeff Erickson,把他20年来在UIUC讲课的内容整理成了一本算法书,名字简单粗暴,就叫《算法》(Algorithms)。
这本书在网上公布后,很快就成了国外计算机系学生讨论的热门话题,在Hacker News已经收获超过1000赞。
原因当然是他在学生当中的名气。Jeff是计算机视觉领域知名学者,有扎实专业知识。难能可贵的是,他教学风格轻松愉快,广受学生欢迎,甚至一位20年前的学生也亲自发帖为他打call。
书本内容
《算法》总共有448页除去前言和简介部分,总共包含了12个章节的内容,主要谈到了以下一些算法:
递归、回溯、动态编程、贪心算法、基本图算法、深度优先搜索、最小生成树、最短路径、全局最短路径、最大流最小割、流量与切割的应用、NP困难等。
Jeff把这本书称作出版印刷前的“第0版”,你可以去他的GitHub页下载到《算法》这本书的PDF版,帮忙找排版和内容上的bug。
喜欢看纸质书的小伙伴也不用着急,《算法》的纸质版即将发行。至于电子版也会一直提供下去。
既然是讲义的整理,除了基本教学内容外,当然还有习题和考卷,每年都会根据教学内容实时更新。如果你想要随附习题的答案,Jeff本人是拒绝的,还是自己动手吧。这本书没有习题答案!
Jeff教师认为,教材有时候在大学教学和自学者之间有不可调和的矛盾。Jeff显然更看重课堂上的学生,如果提供标准答案,只会让学生死记硬背,忽略了答案背后的逻辑。
而且,Jeff说那些想要答案的学位往往是爱作弊的学生。学渣们你们颤抖了吗?
关于作者
如果仅凭以上内容,就认为Jeff是一个不讲情面的大学教授就完全错了。
在考试方面,Jeff对待学生可以说是相当“宽松”。学生在考试题下面写“我不知道”,就能得到25%的分数。
这么做是为了鼓励学生承认自己的缺点,助教也不必为审阅垃圾答案浪费时间。
有趣的是,这位Jeff教授不是一个唯成绩论的人。
因为他自己当初就是一个不折不扣的学渣,GPA得分只有2.4(满分4.0)。他却靠自身努力成为知名教授。
对那些成绩很差却想继续深造的学生,Jeff传授了一点他自己过往的人生经验:
让导师看到你的努力和在专业方面的技能,比如你曾经在计算机领域的就业经历。让导师相信,你出色的能力让他愿意承担风险。(Jeff自己在攻读硕士前就曾是软件工程师。)
最后,Jeff有个幸福的家庭,上面的画像就是他12岁女儿所画。
资源汇总
电子书地址:
http://jeffe.cs.illinois.edu/teaching/algorithms/#book
Github地址:
https://github.com/jeffgerickson/algorithms
作者论文汇总:
http://jeffe.cs.illinois.edu/pubs/index.html
量子位 · QbitAI
վ'ᴗ' ի 追踪AI技术和产品新动态
量子位
www.zhihu.com
欢迎大家关注我们,以及订阅我们的知乎专栏
编辑于 2019-04-03
赞同 3603
23 条评论
喜欢收起
继续浏览内容
发现更大的世界
盐选推荐
知乎 官方帐号
5 人赞同了该回答
常言道「算法才是编程的灵魂」,不管是 Java,python,还是 PHP,都跨不过算法这个门槛。
算法确实不好学,但算法也是真必要。盐选君为大家整理了一系列经典的算法书籍,让你既能 get「冒泡排序」,也能「手撸红黑树」!
经典必看
示例丰富,图文并茂,这是一本像小说一样的算法入门书。
无论你是专业程序员,还是编程爱好者,亦或是需要重温算法的计算机专业学生,这本书都是你不二的选择。
算法领域的经典参考书,包含了经过几十年演化而成的算法核心知识体系。书中讲解了多种算法和数据结构,让你能够在各种计算机环境下实现、调试并应用它们。
进阶必需
JavaScript 是当下最流行的编程语言,它的应用范围非常广泛,不仅用于前端开发,也被应用到服务器和数据库环境中。
想学习实现常用的 JavaScript 数据结构和算法?你需要的这里都有。
面试必备
这里有超过 100 道机器算法工程师的面试题目和解答,其中大部分源于 Hulu 算法研究岗位的真实场景。
在人工智能技术如火如荼的时代,这本书或许可以帮你前进一步。
一「网」打尽程序员面试笔试过程中的各类算法类真题,近 3 年来 IT 企业面试笔试算法高频题目大集合。
这是一份不可多得的求职宝典,快来一键解锁:
哇哦~赶紧跟着盐选君学习起来吧,没有困难的工作,只有勇敢的「编程人」!
发布于 2020-11-05
赞同 5
添加评论
喜欢收起
继续浏览内容
发现更大的世界
知乎用户
266 人赞同了该回答
看了一圈貌似没人推荐这个以动画形式展现数据结构和算法的网站: VisuAlgo – visualising data structures and algorithms through animation
以动画的形式展现数据结构和算法,同时还有代码的运行过程,详细到每一个步骤,值得大家看看,应该是新加坡国立大学的人搞的。
发布于 2014-08-25
赞同 266
14 条评论
喜欢收起
继续浏览内容
发现更大的世界
慕课网
已认证的官方帐号
213 人赞同了该回答
回答前,我们先来举个例子:如何实现“把大象装进冰箱”?
先来看看丹丹老师的“算法”:
https://www.zhihu.com/video/984853200297431040
在这个“程序”中,大象、冰箱,是数据,而“如何把大象装进冰箱”,就是这个程序的算法。所以,我们可以理解:程序,由数据和算法有机地结合而成,其中,算法,即“计算方法”,是程序的灵魂。作为程序员修炼的“内功”,算法是计算机科学领域最重要的基石之一,是程序员进阶的必修课程,特别是面试时,算法是必不可少的一部分。
当然,丹丹老师说的这三步,我们可以更细致地分解
算法一:把大象放在冰箱前,把冰箱门打开,把大象装进去。
算法二:把冰箱门打开,把大象放在冰箱门前,然后把大象装进去。
算法三:把大象放在冰箱前,把冰箱门打开对准大象,然后把冰箱向着大象推动直至把大象装进去。
算法四:……
由以上可以看到,实现一种需求,可以设计出多种算法,并且,算法在很大程度上决定了你写出的程序漂不漂亮、巧不巧妙,所以我们学习算法的目的是为了在写程序时能够设计出更优化的方案。
说完What和Why,我们着重来说一下How。对于初学者来说,可以分成三个阶段进行算法的学习,循序渐进,逐步深入。
第一阶段:基于语言去学习数据结构
首先从最熟悉的编程语言入手,推荐Java或C++,去初窥算法。所谓初窥算法,本质上就是要对数据结构有一定的了解。数据结构,就是把数据和算法联系起来的桥梁,比如排序、搜索、回溯、贪心、动态规划、树、链表、队列、栈等等,这些属于计算机科学基础,每位准程序员都应该掌握。同样的数据,如果选择的数据结构不同,就会把我们引导到不同的算法上面。
继续举大象的例子。一个“把十头大象装进冰箱”的程序,首先要解决的问题是:如何存放这十头大象。你可以把这十头大象用绳子挨个串起来,这样即使大象会乱跑,但只要你一直抓着绳子头,就可以顺藤摸瓜,把十头大象都找到;或者,你可以制作十个紧挨着的格子,然后把每头大象依次放到格子中,这样大象就不会乱跑。在这里我们可以看到,同样是存放十头大象,我们设计出了两种不同的方式,这两种对大象(数据)的存放方式,就是“数据结构”。
同时可以很容易发现,这两种数据结构是各有利弊的。比如用绳子的数据结构,你想增加一头大象很容易,只要再串一个大象即可,但是指定某一头大象却很麻烦,因为你不得不从绳子头开始依次查找;而用格子的数据结构,可以很容易找到任意一头大象,但增加一头大象却很麻烦,因为更改格子数量对计算机来说并不是一件容易的事情。所以,不同的数据结构,由于优缺点不同,会直接影响与之适配的算法的好坏。
每种语言都有一些数据结构,因此可以通过自己熟悉的语言先对数据结构进行了解。初学者如果非常想看书的话推荐《大话数据结构》,这本书比较浅显易懂,实在看不懂的东西也不必深究,简单过一遍有个大体概念就可以了,随着积累,之前不懂的东西自然而然就明白了。至于名气极大的《算法导论》和官方课本《数据结构》,细节方面有些琐碎,小白看的话易头痛,易伤自尊,易被劝退,所以不建议小白看。
如果你恰好聪明如谢耳朵,则可以自由选择相关书籍
第二阶段:基于数据结构去学习基本的算法
在对数据结构有了一定了解的基础上,就可以对常用的算法进行学习了。比如最基本的各种不同的排序方法:冒泡排序法、选择排序法等等。在此期间,可以加强对“时间复杂度”这一概念的了解,同时开始学习一些更高级的数据结构。
这些更高级的数据结构所适用的场景更为简单,因此与它们相匹配的算法基本都固定了,比如红黑树、二叉堆等,这些数据结构是否会被使用,完全取决于其时间复杂度的情况。因此熟记它们的时间复杂度可以让你在不同场景下选择最优的数据结构。
同时,你还需要学习与“图”相关的算法,如广度优先遍历、深度优先遍历、最短路径等等。这个阶段,你可以尝试学习经典书籍《算法导论》了。
另外,在这个阶段,建议找个OJ(Online Judge) 尝试做题,遇到问题可以更有针对性的学习。Online Judge会给你一个简单的问题,然后让你编程解决,系统会有很多测试样例。如果你的代码可以通过所有的测试样例,那么说明你的代码逻辑上是正确的。同时OJ都会有一定的内存使用与运行时间限制,过于低效或耗费大量非必要空间的算法将不会通过测试。
选择OJ直接上手做题的好处是它可以给你正反馈。在OJ上,你可以为了解决一个小目标而学。前期可能要用自己没见过的数据结构、没听说过的算法去解决具体问题,这段时间测评系统不会迁就你,你的理解上有一点小小的偏差,OJ都会狠狠的甩你一脸wrong answer。
但同样的,每一个Accept都会让你的大脑奖励自己一份多巴胺,能够让你更快更精准地融会贯通。随着做题越来越多,你的算法熟练度会被锤炼的越来越高,能够更完美的解答新的题目,后期还可以参加一些比赛小试身手。
PS:在OJ上遇到不能通关的算法或数据结构,建议优先找相关视频来学习,其次是技术博客(不过,博客要挑靠谱的来看)。
当然,除以上方法途径之外,你也可以通过课程高效学习算法,从基础出发,强化算法知识,啃完《算法导论》可能要1年,学习这一门课程你只需要1~2个月就能在算法面试脱颖而出了,适合想打好基础与提升自身高度的同学! 精选了几门liuyubobobo老师的算法课程,都在这个专题里面了:走进Google最强AlphaGo Zero算法背后的智能时代 各取所需吧~
第三阶段:基于具体需要和个人兴趣进阶
如果只是要满足基本使用或大多数工作中的需求,那么完成第二阶段基本就足够了(除非你是专门研究算法的)。
到了进阶阶段,更多的是对算法能力的拔高与探索。在此期间,你会触及到人类目前在算法领域的瓶颈区以及一些更为高级的数据结构。在这一步,建议你除了熟读《算法导论》外,还要继续阅读其他书籍,包括一些学术论文。
你可以继续深入探索基础算法,参加ACM比赛获得奖项;也可以用你练就的扎实编程基础去实现一些高级点的思想型算法,比如遗传算法,模拟退火等去解决实际的一些问题;还可以读个研究生深入某个方向去研究计算机视觉,自然语言处理、数据挖掘、分布式等等对数学要求较高的算法,这些都可以让你成长为一名优秀的算法工程师。
祝君学有所成!~
推荐阅读:
为什么有面试官喜欢让面试者用纸笔写代码?
半路学编程,可以成为大牛吗?
编辑于 2018-06-22
赞同 213
16 条评论
喜欢收起
继续浏览内容
发现更大的世界
HUI SONG
269 人赞同了该回答
不知道你学算法是为什么,目的不同,学法不同侧重不同。
可能性1: 如果你对算法理论和精髓感兴趣,数学推理能力也不错,不急着看完刷题接面试抢offer,你可以去仔细研究下《算法导论》。
可能性2: 如果你和我一样,半路出家,时间紧迫,看书看不进去,你可以试着看视频。
我当年看的是princeton的算法公开课。刷一遍视频,有了基本的感觉,去刷题。
以面世为目的,我用的“cracking the coding interview”,题目是按照array, stack&queue, 链表,树图,递归这种章节安排的,每章节题目7-8个,不多,难度中等,找感觉很有帮助。第一遍自己写不出来的话(我就是,这么弱!),画图分析,抄背默。一遍做完再做一遍,第二遍就快很多,理解也深刻了,所谓读书百遍,其意自现,算法也一样。
刷完这些有点信心了,就去leedcode上给自己浇浇冷水,看看面经。
这些都做完了,你就等着点钱选offer吧,算法学的好不好你早不在乎了,因为你会用了。
(鄙人也觉得上来就推荐《算法导论》的,不是大大牛就是装13!!!)
编辑于 2014-08-25
赞同 269
25 条评论
喜欢收起
继续浏览内容
发现更大的世界
告诉我,缪斯
242 人赞同了该回答
把读《算法》和《算法导论》的笔记贴在这里,仅供参考。
首发在好书一起读(85):算法笔记,欢迎点击~
《算法笔记》
这阵子看了两本算法书,《算法》和《算法导论》。
前一本读着很轻松,内容基本与大学数据结构课程重叠,示例代码用java编写,学习曲线平缓,对应用程序员来说,读它就挺好。
后一本我是边看麻省理工的《算法导论》公开课边读的,力不从心,因为我数学基础不好(详下),如果不看数学证明,其内容跟前一本就差不多了,数学基础比较好、对算法感兴趣的朋友,可以尝试之。
强烈建议各公开课平台的学习资源,质量非常高,相见恨晚!足不出户,就能学习名校的课程。但学习时别忘了跟着做习题、做笔记、预习复习。
下面是我的《算法》笔记。
零、思想
重中之重。算法真正的精髓。内功心法所在。相比之下,后面讲到的都是具体招式。
内功心法的意义就在,有朝一日你遇到一个没有既有经验的问题,能自己设计出适当的数据结构和算法,而不是只会用别人的轮子。
算法的根本思想,是大问题化为多个小问题,逐渐解决之。(《孙子兵法》:治众如治寡,分数是也;斗众如斗寡,形名是也。)
1.分治
如果能将大问题拆为同性质的小问题,当小到一定程度,能直接解决之。
则采用分治法,递归解决。
2.贪心
如果为小问题找到的最优解,能通过增加一点步骤,解决一个大一点的问题,并依然是最优解。
则采用贪心法,从0开始,逐步蚕食掉大问题。
3.动态规划
如果用分治法拆出的小问题中常见到相同问题,重复计算它们,成本太高。
则采用备忘法,计算完每个小问题的结果后,记录之,下次见到同一小问题,不再重复计算。
一、数学基础
《算法导论》在附录中给出了4项必备的数学基础。
我看了之后,很羡慕考研的同学,他们这几门课都很扎实。
这4门数学除了是考研数学科目、算法的基础外,其实更是观察世界、指导生活(不仅仅是生产!)的工具,我决定要以看公开课的方式,逐步重新学之。
1.微积分
2.离散数学
3.概率论
4.线性代数
二、线性表
1.按实现分类
顺序表:随机访问方便,插入删除成本高,因为一侧的元素要「哒哒哒」依次移动一格。
链表:随机访问麻烦,因为要从头「一二三」数过去,插入删除方便,将特定两三个节点的指针「咔吧」重新接一下就好了。
2.按作用分类
栈:后进先出,直观理解就是坐电梯。用处主要在处理大问题时,细化为小问题,小问题解决完再继续处理大问题的时候。计算机的函数调用的核心数据结构。如果不幸小问题没完没了,如无限递归,则stackoverflow。
队列:先进先出,讲「先来后到」的数据结构。典型使用就是「任务队列」,先到的先处理。如果允许「插队」,就是「优先级队列」了,让领导先走!
三、排序
假设有一个初始队列4132,目标是从小到大排序成1234。
1.冒泡排序
最简单也最慢的算法,慢到不少书都不讲了。
思想是让最后一个元素尽力向上爬,遇见比它大的就压过之(交换次序),如果遇到比它小的就停下,由小的继续往上爬。爬到第一个元素时,就保证了第一个元素是全部元素中最小的一个。
不再考虑第一个元素,重复这一过程。4132,1/423,12/43,123/4。
2.选择排序
每次都从队列中选出一个最小的元素,放到「已排序队列」里,直到选完。
/4132,1/432,12/43,12/34。
3.插入排序
每次都从「未排序队列」中选第一个元素,插到「已排序队列」的适当位置,直到插完。
我玩扑克时理牌就用这法。
4/132,14/32,134/2,1234
4.希尔排序
先把「相距较大间距」的元素们排序一遍,再适度减小间距再排一遍,最后一次相距零间距排。
4132,先间隔较大间距(这个简陋例子,姑且间隔1),4与3排序,1与2排序,得3142,再间隔较小间距(本例中直接到0了)排序。
5.快速排序
最被喜欢的排序,既容易理解,又快。
选一个数字为轴,比它小的放左边,比它大的放右边,然后对其两边各进行这一变化即可。
4132,第一步选4,第二步选1,都是把全部剩余元素放到同侧,不划算,所以随机选择轴元素很关键。
假设第一步选了3,12放左侧,4放右侧,右侧完结,左侧继续,假设选2为轴,1放左侧,右侧没有,即得结果1234。
6.归并排序
所谓归并,比如一班和二班已经各排成了从矮到高的有序队列,想归并成一队,怎么办?比较一班和二班的排头,更矮的选出来站到「结果队列」里,该班的新排头再跟对方排头比,以此类推。
归并成一个新队列后,再跟别的队列归并,直到统统归并为一队。
14/23 – 1
4 – 1234
7.堆排序
所谓堆,就是一棵每个父节点数值都大于其一切子孙节点数值的完全二叉树,如果看不懂,先跳到下面看树那节。
为方便说(放图太麻烦了,我相信纯文字能说清),这次咱们从大到小排序,道理当然是一样的。
分两步,一是从无序队列构造树,二是从树输出有效队列,结合起来,就是从无序队列,得到了有序队列。
第一步,拿一个新节点,放到原树的最后一个位置,然后使之尽力向上冒泡,直到冒不动为止,再拿下一个新节点。如处理4132:
4 – 4左下1 – 4左下1右下3 – 4左下1右下3,1左下2 -(2冒泡)- 4左下2右下3,2左下1
第二步,取出根节点放到结果队列,把最后一个节点僭越到根位置,然后考察其两个叶子节点,如果有更有实力的,则向最有实力的退位让贤,交换位置,到新岗位后继续考察下属能力,直到降到自己胜任的位置。
4左下2右下3,2左下1 -(取出4,1上位)- 1左下2右下3 -(3篡位)- 3左下2右下1 -(取出3,1上位)- 1左下2 -(2篡位)- 2左下1 -(取出2)- 1孤家寡人 -(取出1)- 结果4321
若干节点,及若干连接节点的无向边,构成的图,如果从每个节点出发,都能到达任意一个节点(强连通),同时图中不存在环,即称为树。
数据结构中说的树,在此基础上再严格点,分为若干层。如某团长手下有若干连长,每个连长手下有若干班长,画组织结构图,把直接领导和直接下属连接起来。直接领导称为父节点,如团长是连长的父节点,连长是其属下每个班长的父节点;直接下属称为子节点;最高长官称为根节点,即没有父节点的节点;没有子节点的节点称为叶子节点,比如《士兵突击》里钢七连只剩老七(连长)和三多(班长)的时候,三多是叶子节点,如果这时三多被老A挖走(实际剧情是老七先走,不赘),则老七堂堂连长,将不幸成为叶子节点。
1.二叉树
如果树的每个父节点最多只有两个子节点,该树即称为二叉树。
最典型用途是二叉查找,即如果每个根节点数值都比其左子树(此概念望文生义,不赘)任意节点数值更大,比其右子树的任意节点数值更小,该树即称为二叉排序树。在想寻找某个数值时,可以先将该数值与根节点比,如果比根节点大,则去与其右子树根节点比,如果比根节点小,则去与其左子树根节点比,直到找到或比到叶子节点为止。
好像「猜数字」游戏,一本好书价值1元到256元之内,假设你蠢到看不出那书不可能1元,又聪明到知道采用二叉查找,则该先猜128元,根据主持人说「高了」「低了」再决定猜64还是192元,假如64还是「高了」,则该继续猜32,以此类推。
2.红黑树
强烈推荐看《算法》中红黑树的章节,从2-3树开始讲,讲到红黑树,学习曲线非常平滑。
二叉树和红黑树都有着清晰的用于保持树平衡的逻辑,限于篇幅不多讲。平衡的目的是保持最差情况下的查找程度为logN(以2为底,总节点数的对数)。
3.散列表
这个不是树……但在逻辑上放在这里最好,因为都是用于「查找」的数据结构。
编程中最基本的两种数据结构,list和map,list就是上文说的线性表,核心是有顺序,map就是这里说的散列表(hashmap)或树(treemap),核心是键值对。set呢,多以map做底层结构。
树上面说了,这里说散列表。
散列表又叫字典,从这字面可知,主要用途是查找,通过键(key)查找值(value),首先,要把键算成一个数字,这算法(散列函数)就是java里类们都要实现的hashcode方法。
然后,有两种可选的实现方式,一是链接法,首先有个主list装着键们,比如123,然后1对应一个list,2对应一个list,3对应一个list,我把键算出是1之后,就到1对应的list元素里去找元素。显然,1对应的list长度越短,查找时间越短,那似乎主list的键们越多越好,比如1到30,那每个子list的长度将变为原长度的十分之一,但主list的键们也不能太多,比如1到30000,那大部分键对应的其实是空,里面一个元素都没有,就浪费空间了,所以要权衡。
另一种实现方式是散列法,不存在次list,把键算成数字后,直接往主list对应的位置存,如果该位置已经被别的元素占了(碰撞)怎么办?则用某种算法,算出一个新数,再尝试往新位置放(再散列),以此类推。显然,这种方法,主list的长度也很关键,如果太短,则碰撞太多,插入、查找都麻烦,如果太长,又浪费地方。
对两种方法,散列函数都,如果所有元素的散列函数都计算出同一个值,散列表就毫无意义了。
终于到图了!这是我最喜欢的部分,好玩,而且熟悉,因为我认识一个同学,数据结构年年挂,直到大四,所以我每年都陪他复习备考一次,老师考卷中的高分的题目,就是考图的几个算法,迪杰斯特拉,普里姆,克鲁斯卡尔……好怀念那段日子。
什么是图?一堆节点,及若干边,就构成了图,根据线路是否有方向性,分为有向图、无向图,根据图中是否有环,分为有环图、无环图。
如果任意两个节点都有线路连接,则称为强连通图,这里主要聊的都是这种。
1.深度优先、广度优先遍历
A连B,B连C,B连D,C连E
想把图里所有节点都研究一遍,怎么办?
从一个节点开始,走向下一个节点,然后再走向下一个节点的下一个节点,直到「眼前无路想回头」,就是「深度优先遍历」。在例子里,从A到B,从B到C,从C到E,E回头到C,C回头到B,从B到D,完成遍历。
「广度优先遍历」则是,从一个节点开始,先扇面状把能到的节点都扫一遍(广嘛),然后再「移步」到子节点们。在例子里,从A到B,从B到C,从B到D,从C到E,完成遍历。
2.最小生成树
如果树的每条边都有个权值,要求选出总权值最小的一些边,让所有节点都能互相连通,怎么办?
这就是「最小生成树」问题,显然,选出的结果肯定是一棵树,树的两个条件,连通和无环,连通不必讲,为什么无环?如果有环,去掉任意一条边,节点们依然相互连通,权值变小了,由此反证,必然无环。
解此问题,两种方法,一是普里姆算法,二是克鲁斯卡尔算法,好专业,终于有点算法的感觉了。
其实都很简单,先说普里姆,将图划为「已解决」和「未解决」两个部分,一开始「已解决」为空,「未解决」是全集,首先,任选一个点放到「已解决」,然后考察所有从「已解决」连向「未解决」的边,哪条最短,就把该边连向的「未解决」节点纳入「已解决」集合,如此反复,直到全部节点都「已解决」,结果就是最小生成树。
再说克鲁斯卡尔,一开始,把每个节点视为一个「分量」,寻找全部「连接两个不同分量的边」中最短的一条,将其连接的两个分量合并为一个分量,并重复这一行为,直到全部节点都属于同一分量,结果就是最小生成树。
3.单源最短路径
最小生成树研究的是无向图,最短路径则研究有向图。
顾名思义,最短路径是要求给出从某地到另外某地的最便捷走法,这有两个算法,一是迪杰斯特拉算法,二是贝尔曼福特算法。
先说迪杰斯特拉,这是类似普里姆的「贪婪算法」,从一个极小的「已解决」开始,逐步蚕食,直到将「未解决」吃掉。差别在这回每个节点上都有个数字,代表其到起点的距离,每次都选全部「从已解决到未解决的边」指向的「未解决」节点中,数字最小的一个。比如起点是家,家距离学校500米,家距离市场600米,学校距离公园200米,根据算法,把学校标注500,市场标注600,500小于600,把学校纳入「已解决」,学校进入「已解决」之后,公园也变成了从「已解决」可以到达的「未解决」的节点,用学校的500加200,公园标注为700,与市场的600米相比,600较小,把市场纳入「已解决」。注意,这个步骤,如果是普里姆算法,纳入的是公园而非市场,因为普里姆不存在起点,都连上就ok,只考虑哪条边最短,但迪杰斯特拉有起点,要比较的是「从起点出发直到这里的距离」。
再说贝尔曼福特,这算法是把每个节点赋予一个表示「距离起点有多远」的数值,除了起点外,其他起点一开始都是无穷大,然后依次考察每条边,如果这条边能让指向的节点的数值变小,就将该节点数值变小(收缩),把所有边都考察一遍之后,如果这一遍中执行了「收缩操作」,则再把所有边都考察一遍,直到某一遍完全没收缩为止。上面的例子,比如考察次序是200-500-600,则第一遍200啥用没有,500将学校的+∞变为500,600将市场的+∞变为600,这遍进行了收缩,再来一遍,这回200有用了,将公园的+∞变为700,500和600都没有,这遍也收缩了,再来一遍,200/500/600都没用,完结。
六、字符串
字符串本质是字符数组。说到算法,最常说的就是字符串查找的KMP算法。
比如想从「子龙子龙世无双」里寻找「子龙子翼」,「子」等于「子」,「龙」等于「龙」,「子」等于「子」,「龙」不等于「翼」,糟糕!这时源文本的「已搜索序列」的「后缀们」有「子龙子龙」「龙子龙」「子龙」「龙」四个,而目标文本的「前缀们」有「子龙子翼」「子龙子」「子龙」「子」四个,考察两个「们」,发现有个相同元素,即「子龙」,长度为2(如果有多个相同元素,则取最长的),意味着源文本的「已搜索序列」中最后两个字与目标文本的前两个字相同,下次用源文本的下一个字「世」与目标文本的第三个字「子」相比即可。如果是朴素算法,则要用「子龙子龙世无双」的第一个「龙」字与「子龙子翼」的第一个「子」字相比,KMP算法比朴素算法快多了!
七、写在后面
算法的水太深,我仅仅入了个门,回头看看,上面所写,全是大学《数据结构》的内容,长叹一声。
也有更深入学习的意愿,但在这之前要巩固数学基础,我在看网易公开课上的《线性代数》和《微积分》的公开课。
好在,这些「入门知识」,平日工作倒也够用,而数学、计算机基础的巩固和学习,是一辈子的事,不用太急。
不要哀叹过去的荒芜,唯一的方法是立足于现在的状态,选取最优的进步路线,勤勉地躬行之。
学过一点点经济学基础的人,不会为「沉没成本」沮丧。
数学太美,逻辑太美,算法太美。
我却近来才发现。读书的时候全没省得。
不省得也没关系,老老实实听话就好,现在想想,是「独立思考」得过于早了。
这是我的人生历程,没什么可后悔,写这只是想规谏还在念书的朋友。
别急着自行其是,以后的人生里,有的是机会让你自行决策,还在念书的时候,请听话。
听老师的话,好好学习,天天向上。
编辑于 2016-09-11
赞同 242
14 条评论
喜欢收起
继续浏览内容
发现更大的世界
牛客网
已认证的官方帐号
139 人赞同了该回答
大家好,我是左程云。我本科就读于华中科技大学、硕士毕业于在芝加哥大学。先后在IBM、百度、GrowingIO和亚马逊工作,是一个刷题7年的算法爱好者,也是牛客网的老师。2014年起专职做程序员算法和数据结构培训,代码面试培训,刷题交流等相关工作。
我是《程序员代码面试指南–IT名企算法与数据结构题目最优解》的作者 ,书籍涉及算法与数据结构编程题目240道以上,并且个人实现出最优解,大部分题目为面试高频。
这篇我想写写算法的重要性、我个人是如何学习算法以及一些如何学习算法的建议。
算法在求职以及工作后的重要性
求职面试必考(校招+社招),且国内工资越高的面试中算法比重就越大。
我分别说一下国内和国外的行情。
国内的话,一般来讲,工资高的公司在面试时算法和数据结构题目的比重较大,工资一般的公司比重较小。当然同样公司的不同岗位,要求也会不同,但总体趋势就是 国内好公司爱考算法和数据结构 。这是目前国内互联网公司的情况。国外的互联网公司呢,几乎只考算法和数据结构,很多年前就是这样了,一直如此。我相信国内会逐渐变得像国外一样,并不是崇洋媚外,而是算法和数据结构题目真的能考出东西。
先抛开算法,我们来说说面试以及如何准备。
面试中都会考什么呢?
面试中会考察算法,操作系统,数据库,计算机网络,编程语言,项目(校招涉及)/经历(社招中涉及的更多)
如何准备?
操作系统,数据库,计算机网络,编程语言这些都是平时学习,记住了,理解了,不忘记就可以了项目或者经历是平时准备的,如果马上面试了再去准备也是很难的,作假在面试中会直接被面试官看穿,所以这个平时就要准备好,如果是校招,那平时就要做一做有用的项目,如果是社招,平时在工作中就要用心做。算法和数据结构,是真的需要好好写代码才能掌握,不是说看了理解了就真正会的了。算法笔试面试的特点就是没有特点,什么样的题都可能遇到,因为根本没有考纲,面试官就是普通的程序员,他们在工作中或者在网络上遇到什么题不错,就可能考,所以内容真的太多了,而且也无穷尽。这不是一个标准考试,这是能力考试。
所以,我建议大家面试或者笔试前抽出20%的时间去理解和记忆非算法和数据结构的题目,剩下的时间就是去刷题。
今天学习算法变得越来越重要,虽然每个公司行业不同、岗位复杂,但算法能力强是分析能力和解决问题能力的提现。虽然计算机的处理能力越来越强,但好算法的代码执行效率相比起没有优化的代码,已经不能用快多少倍来描述了。计算机科学有自己的衡量标准,也就我们常说的复杂度标准。同时,学习算法对理解底层实现是的,优秀的程序员专注细节和底层,具备算法能力是起点更是基础。包括今天很多的领域,比如机器学习,深度学习,还有大热的AI领域,想要研究透彻,都离不开算法好的大脑。还有很重要的,加薪和跳槽,算法都起着的作用。学习算法可不仅仅是刷题,这一过程中自己的思维和想法的提升才是学习算法的最大好处。
我是如何学习算法的?
本科在华中科技大学计算机学院,这一期间能在学业上让自己满意的可能就是没有挂科而已。硕士在芝加哥大学,出国之前就了解到想要在国外找工作的话,面试时几乎只考算法和数据结构的题目,于是开始了刷题,也就是搜集这方面的题,并且用代码实现出来,不断看题解和与高手讨论。 就这样从2010年到今天,刷了7年算法和数据结构的面试题。刚开始其实只是为了找工作才开始刷题,但是半年之后就变成了兴趣。
刚开始刷题的过程中很不顺利,因为很多算法和数据结构,教材也不会讲。而且去网上搜各种各样的分析文章也读不懂,感觉基础差的很远。当时网上的分析文章,也不会像今天这么易懂,高手都是把最核心的点说出来,但是我没摸到人家想说的点之前,就已经不会了。于是就把很多很厚的书拿来啃,书上也看不懂就尽可能的找到高手向人家请教。对书上的题目实现了好几遍,才发现入了门,头脑也开始活泛起来。遇到不会的就查,发现一大片知识不知道就练。在网上发帖被嘲笑的日子,其实非常的涨见识,我很珍视那段岁月。当时在国外,学费也贵,因为钱的刺激和好胜心,居然没有让我变态,而是变成了一种斗志,用了大量的时间好好刷题。刚开始代码实现算法和数据结构的题目真的非常痛苦,因为这部分的内容相比其他方面的知识绝对算高门槛,而我最开始的基础也并不好。现在我经常在网上给同学们讲题,看到同学们表达的抱怨,那简直就是当年的我。暗暗发下心愿,如果有一天讲课,绝对做一个人人都能听懂的好老师。但不管怎么引导,算法学习都是一个脱皮换骨的痛苦过程,但好在会迅速上瘾,坚持半年之后就能一直坚持下去了。
算法和数据结构问题的技术累积需要长时间的投入,因为内容又多又杂又难,很多算法是那种你很怀疑自己再来一辈子也可能想不到的解法。当时作为一个小白,一个算法的意思看懂了,实现起来是如此的难,测试用例总能指出我的幼稚;写了很多代码终于过了这一题,看到高手写的实现,自己又幻灭了,高手写的好棒,自己写的……然后收拾起碎裂一地的三观,重新出发。解了很多题目之后,类似的题目出现,自己还是会想很久。这让我意识到,自己缺乏总结,于是开始了总结的过程,也萌生了写书的冲动。刷完一道题其实是一件很难的事情,因为普通解法很容易,但是最优解真得去耐着性子研究好久,去查资料,去做优化,这个过程很漫长但是足够迷人。
到底应该怎样学习算法,作为过来人,给大家的建议
先跟大家聊聊算法吧。
在网络上流行一句话:算法分三种,竞赛的算法、面试的算法、算法。虽然我觉得这么分非常让人无语,但其实可以去这么理解,因为竞赛、面试和纯理论的要求和限制是不同的,所以算法在不同的要求中展现了不同的样子。
对于竞赛来说,每道题对输入参数和样本量的要求都是非常明确的,同时规定的非常明确的还有空间的限制和运行时间的限制。每一个竞赛选手都非常熟练怎么根据这些提前给好的限制,反推出自己需要实现一个什么样复杂度的解法才能通过。每一行代码包含着前辈和自己思考过的优化。
而对于面试来说,限制往往并不明确,造成这个现象的原因也很好理解。竞赛中当然是分数最重要。在面试的过程中,与面试官的交流和体现自己想事情的方式、体现自己逻辑的严密更重要。所以同一道题,在竞赛中必须写清楚限制,而在面试中一道题刚开始的限制没那么多,目的就是缩短你理解题目的时间,让面试者先写出一点什么,然后和面试官展开讨论,随着讨论的深入,再逐渐的把限制聊清楚。总之在面试的场合就是想看看你想问题的习惯、轨迹以及表达能力是否符合要求。
当然,不管是什么要求下的算法,经常练习算法和数据结构题目对一个人在逻辑上的提升都是显而易见的,在学校参加ACM并取得很好成绩的同学,如果不是表达能力特别差的话,是一定会收获很多offer的,因为思维被锻炼的很好
对于算法,我给大家的建议:
先找到线团,然后进入线团里学着怎么玩。为了进入线团,需要先把基础知识掌握好。《算法和数据结构》(教材),你一定要看完+理解。这里面讲的都是不能再基础的东西了,觉得讲得不好,自己搜维基百科。没办法,如果坚持不下来,你后面就受罪去吧。
然后有一些很经典的书可以迅速让你进入状态,比如我这本《程序员代码面试指南》,还有《剑指offer》,配合在线练习:https://www.nowcoder.com/ta/coding-interviews,《程序员面试金典》配合在线练习:https://www.nowcoder.com/ta/cracking-the-coding-interview,这些好书。我在牛客网上还有一个针对小白的扫盲的课程https://www.nowcoder.com/courses/semester/algorithm。
对于线上刷题平台的题目,先不找解答,先自己实现,实现的多烂,复杂度多差,都坚持写完。然后分析出复杂度。接下来去网上找答案,看到复杂度和你一样或比你低的,直接略过。看到比你好的,重点看,一定要理解,然后分析为什么比你的好,如果你真的理解了,你一定能找到别人优化的点。这个过程可能是最奇妙的过程,不要给自己太大压力,这个过程其实可以很欢乐,你有想法并创造出来,练习了自己的coding能力。别人有更好的实现,推翻了你的所有模型和幻想,你幻灭了,却也因此找到了让你血脉喷张方法。这个阶段看似苦,实际上其乐无穷。你在学习别人解法的过程中,又了解了很多算法和数据结构。而且你付出的每一滴汗水,都是结果导向的,可量化的,实实在在的。写写简单的测试函数就可以发现自己方法的运行时间和更好的解法就是没法比。这是一个非常培养自驱力的阶段,这是一个只追求解法更快更强的阶段。你看到很多经典的结构,你学到很多细思极妙的优化。比读那些让你吃力的书更加快乐,也能够一直启发你走下去。你苦苦寻找啊,觉得好的不能再好的方法啊,直到有一天,你突然看到一个更优的解法,相信我,你一定会一整天都在贤者时间里。
我不建议刚开始刷题的人就直接在网络上搜集文章开始学习,因为太散了,而且需要花很多时间去鉴别正确与否。当这些内容都掌握之后,再开始在网上搜集各种各样的题,并与网友参加各种各样的讨论,会比较高效。把底子打好之后,对于专项算法的学习就得心应手了,而且会学的很快。 对于很庞大的算法,我个人的习惯是找例子来引导自己的思路,一点一点的接近算法的核心。唯一需要注意的是,一定要写代码,光看没有用的。对于经典算法的学习,大体上分成几个阶段:
第一阶段:对于某一个具体的算法,首先要搞清楚这个算法解决的问题是什么,可能是实现一个具体的功能,也可能是在某些方面,比如时间复杂度或者空间复杂度方面很卓越,总之搞清楚这个算法被研究出来的目的是什么。第二阶段:然后就要弄清楚这个算法的生存环境了,也就是看看你此时研究的东西是不是对别的知识有依赖,应该先把底层依赖的知识理解并掌握。这些问题都解决之后,就进入到算法本身的学习,理解一个算法是一件辛苦的事情,刚开始看必然会产生很多的困惑,比如经常会怀疑作者讲述的内容的重要性?这些内容和这个算法有什么联系呢?经常会有这种摸不着头脑的感觉,其实作者做的铺垫都是为了建立起描述算法主要内容的基础,只有接受和理解这些基础,才能逐渐触碰到算法的精髓,所以耐心是很重要的。第三阶段:算法的主要过程看完之后,往往还是会感到困惑,主要是不知道这个过程好在哪,这就进入了下一个阶段,理解作者对这个过程在功能性或者效率卓越这件事上的解释和证明。这才真正触碰到算法最精髓的部分,也就是深度的理解算法的主要过程所带来的好处,这才是最锻炼人理解能力的地方。第四阶段:上面几点是算法学习阶段的过程了,接下来就是研究算法的代码实现,自己设计测试用例亲自跑一下代码,以及从代码运行时间的角度分析这个算法的优势,这也是加深对算法的理解的过程。第五阶段:最后是配合相应的题目练习,让自己通过题目练习的方式,会用、善用学习到的算法,并对这个算法产生一定的敏感程度,具体是指看到某些题目时,能够根据题目的特点,产生与该算法的对应,也就是具备举一反三的能力。
学习永无止境,不管是算法小白,还是有一定的算法基础,提升算法永远都是刚需,我正好要在牛客网即将开一个算法班,针对算法小白的基础班和有一定算法基础的刷题班,如果你想跟我一起学习,也欢迎你报名跟我一起探讨算法,希望所有努力和上心的人都能成为大牛。
原文:《左程云:程序员该如何学习算法?》
作者:左程云
另外,左老师在牛客有几门算法课,如果觉得左老师说得还不错,可以来了解一下~~
牛客算法基础入门班_牛客网
www.nowcoder.com牛客算法基础提升班_牛客网
www.nowcoder.com求职算法真题精讲-中级班_牛客网
www.nowcoder.com求职算法真题精讲-高级班_牛客网
www.nowcoder.com
最后,其实这个问题下,也有左老师自己的回答~也欢迎大家来“勾搭”左老师鸭~~
程序员应该如何学习算法?左程云的回答
www.zhihu.com
编辑于 2019-12-27
赞同 139
3 条评论
喜欢收起
继续浏览内容
发现更大的世界
761 人赞同了该回答
不请自来。
结合自己学习算法时的一些经历来说,下面一句话要始终记得:
自己之前也是个技术渣,但好在是一直没放弃学习,一方面坚持看书听课学习理论,另一方面自己动手去写、去实践,积累了很多方法和心得,简单地说就是一定要做到看书、听课、做题相结合,缺一不可。
下面上干货了。
(一) 参考书目
推荐几本书,都是我当时学习的时候看的书,个人感觉很好,内容充实,讲解细致。
1、《Algorithms》一本很经典的算法书
Algorithms(中文翻译的书名叫 算法概论)
2、刘汝佳的《算法竞赛入门经典(第二版)》
内容比较基础,适合初学者
算法竞赛入门经典(第2版)-刘汝佳(清晰非扫描版) – 下载频道 – CSDN.NET
3、《程序员代码面试指南:IT名企算法与数据结构题目最优解》左程云
书中都是一些IT名企真实代码面试题,很全面地覆盖了算法与数据结构题型。
程序员代码面试指南-IT名企算法与数据结构题目最优解 – 下载频道 – CSDN.NET
(二)课程
自己之前学习算法时一直在听下面这2个算法课程,是左程云主讲的,
这两个课程都是的。
讲得挺细致的, 像我这种算法、数据结构较为薄弱的同学都能听得很明白。
并且还有课后配套练习题,大部分是名企面试真题,听完课后练习很好地巩固了学习效果。
当时听完课后收获挺大。
牛课堂算法精讲直播讲座(2015)_牛客网
牛课堂算法精讲直播讲座(2016)_牛客网
(三)课后练习题
我当时做的是这几个题库的题,结合使用,效果不错。
1、 专项练习
可以随意设置难度,选择知识点,题目挺全面的,知识点也很细。
智能专项练习_C++Java前端经典笔试面试题库_牛客网
2、在线编程题
(1)《剑指offer》
66道在线编程题,支持js,php,java,c/c++,python,c#等多种语言。
程序员求职必刷。
剑指Offer_编程题_牛客网
(2)leetcode在线编程
leetcode在线编程_牛客网
(四)算法网站
Jeff Erickson 算法课程网站,有许多课程讲义 Erik Demaine 算法课程网站,有许多特殊专题 GeeksforGeeks 程序设计、数学、算法益智问题 Algorithms Notes 算法益智问题 VisuAlgo 数据结构可视化
Jeff Erickson
(五)数学网站
1、Matrix67 一直十分仰慕M67。数学爱好者的天堂。 Wolfram Math World 这个网站收集了丰富的数学资料。 如果遇到数学问题,可以到这里查询资料
Matrix67.com – Home
2、http://planetmath.org 这个网站的目标是称为数学的百科全书,有很多好读的数学文章 The On-Line Encyclopedia of Integer Sequences 收集了几乎世界上所有出现过的数列。找规律题神器!
http://www.planetmath.org/
编辑于 2016-12-14
赞同 761
28 条评论
喜欢收起
继续浏览内容
发现更大的世界
C++等 3 个话题下的优秀答主
558 人赞同了该回答
推荐我的一位朋友写的 Book of Elementary Algorithms and Data structures 《初等算法》
虽然书是用英文写的,但我这位朋友是中国人,正式的工作是软件工程师和项目经理,业余时间对算法很有兴趣,他花了数年时间,把自己对算法的心得体会写成了这本书,把全部的内容以及相关源代码都开源了。
他对算法和编程语言有深入的研究,能熟练使用十余种编程语言。这本书中的算法的参考实现都提供了 C, C++, Haskell, Python, Scheme/Lisp的版本。
项目开源:
liuxinyu95/AlgoXY · GitHub
这本书还在,几天前还有修改。
下面的引用来自他正式发布本书时写的一篇blog,这是我认识的最有情怀的程序员了。
有两本书对《初等算法》影响最大。一本是Chris Okasaki的《Purely functional data structure》另外一本是《算法导论》。写作过程中还参考了一些其他书籍,包括Knuth的《计算机程序设计艺术》,Richard Bird的《Pearls of functional algorithm design》,Bentley的《编程珠玑》以及一些论文。
写这本书的六年中,我总是想起法国数学天才伽罗瓦最后写的那句话:“我没有时间了!”,我原计划用10年写完这本书,结果提前了4年。这样的代价 很大。为了避免翻译,过滤“噪声”,我直接用英文写作。由于不是native speaker,书中的英文语法和拼写难免贻笑大方。为了赶时间,proof reading被压缩,许多结论采取了“拿来主义”,没有进行严格的数学证明。一些章节的课后习题也没有给出答案。
理想情况下,一本严肃的算法书应该在稳定、宽松的环境下精雕细琢。可是在社会剧烈发展的今天,在日新月异的中国,在人们习惯快餐而不再享受大餐的 快节奏生活中,在微博、取代文章、书信的手机网络大潮下,这样的理想环境根本不存在。未来不可预知。对于《初等算法》这本书,开放给社区是最好的选择。需要做的工作很多:
* 翻译中文版
* 社区proof reading和review,修正内容上的错误和英文上的不足
* 提供一本习题集
* 补足数学证明
* 采用强大的数学工具,对形式化的算法进行分析
一些数据:
《初等算法》黄金分割0.618版本,历时6年,在github上总共提交1680次commit。全书600多页,19万字(word)。2万2千行示例代码。
《初等算法》在GNU FDL许可协议下发布,所有代码在GNU GPLv3协议下发布。
编辑于 2014-08-25
赞同 558
46 条评论
喜欢收起
继续浏览内容
发现更大的世界
九章算法
美帝代码搬运工,资深面试官,-九章算法
471 人赞同了该回答
正如其他答主所说,学习算法,不要一上来就开始啃《算法导论》,毕竟这本书并不适合新手学习,如果你之前的算法基础比较薄弱,只会一直陷在“拿起来又放下”的循环里。
可以怎么入门呢?建议还是看书+实战,实战当然也不是说要去肝ACM或者是topcoder什么的,基本上来我们LintCode刷刷题也就够了。
如何学习算法?
算法,其实可以分为三种。算法、面试算法、竞赛算法。
也就是算法本身,推荐一些书籍。
1.入门系列:
《算法图解》:“像小说一样有趣的算法入门书”,主打“图解”,通俗易懂
《大话数据结构》:把理论讲得有趣不枯燥;每个数据结构和算法,作者都结合了生活中的例子,能让你有非常直观的感受。
2.教科书系列:
《数据结构与算法分析》:很多大学都拿它当作教材,非常系统、全面、严谨,适合掌握了至少一门编程语言的同学。
作者也很贴心,这本书有三种语言的版本:《数据结构与算法分析 : C 语言描述》《数据结构与算法分析 : C++ 描述》《数据结构与算法分析 : Java 语言描述》。
3.进阶之旅:
《算法导论》:有了一定基础之后,就可以开始啃这本大部头了。
5.扩展阅读:
《算法之美》:算法科普,从生活中的各种问题说起:租房、谈恋爱、老虎机、拍电影、面试、买彩票、各种排序、找停车位、寻找新药、临床试验、奥巴马拉赞助、预估电影票房等等,非常生活化,可以作为补充阅读。
《算法帝国》:同样是科普类书籍,并无涉及算法的原理与实现细节,也可以作为补充阅读。
6.殿堂级
《计算机程序设计艺术》:包含很多卷,深度、广度、系统性、全面性是其他所有数据结构和算法书籍都所无法相比。可以当做一种挑战~
图源网络,侵删面试算法
要说最快掌握面试算法的捷径,还是脚踏实地着多动手去刷题,多刷题。
当然,在LintCode开始刷题,首先你也也得具备一定的基础,这些基础包括:
算法部分
二分搜索 Binary Search 分治 Divide Conquer 宽度优先搜索 Breadth First Search 深度优先搜索 Depth First Search回溯法 Backtracking 双指针 Two Pointers 动态规划 Dynamic Programming 扫描线 Scan-line algorithm快排 Quick Sort
数据结构部分
栈 Stack队列 Queue链表 Linked List 数组 Array 哈希表 Hash Table二叉树 Binary Tree 堆 Heap并查集 Union Find字典树 Trie
对算法题来说有两大法宝,“拿到题选什么算法”和“如何实现这个算法”,后者会更容易一些,所以可以先从实现算法开始练起(LintCode的分类阶梯训练)。
然后当一些标准算法数据结构都不陌生后,再去训练新题,尝试用各种算法解决各种不同的问题。
当然,针对面试准备,也有一些书:
《剑指 Offer》:几乎包含所有常见的、经典的面试题,是应对面试的必读书籍
《编程之美》:适合准备面试FLAG大厂时候用来刷题
ps:这两本书都可以配合在LintCode上刷题
竞赛算法
算法学习最好由浅入深,先了解算法思维,再去理解实际应用;
当逐步全面的掌握相关知识体系,有一定实践经验后,可以去参加一些竞赛提升自己的算法能力。
竞赛算法是比较锻炼人的,对于竞赛来说,每道题对输入参数和样本量的要求都非常明确,包括对空间的限制和运行时间的限制也规定的非常明确。每一个竞赛选手都非常熟练怎么根据这些提前给好的限制,反推出自己需要实现一个什么样复杂度的解法才能通过。所以对思维和逻辑上的锻炼是非常有效的。
献上一些面试常考算法类型和经典题,愉快地刷起来吧~
尾部的零
斐波纳契数列
x的平方根
x的平方根 2
大整数乘法
骰子求和
最多有多少个点在一条直线上
超级丑数
比特位操作
将整数A转换为B更新二进制位
二进制表示
O(1)时间检测2的幂次
二进制中有多少个1
动态规划
编辑距离正则表达式匹配
交叉字符串
乘积最大子序列
二叉树中的最大路径和
不同的路径
通配符匹配
滑动窗口的中位数数据流中位数
最高频的K个单词
排序矩阵中的从小到大第k个数
二叉树中序遍历二叉树的序列化和反序列化
最近公共祖先
二叉树的层次遍历
将二叉树拆成链表
在二叉查找树中插入节点
经典二分查找问题二分查找
两数组的交
区间最小数
寻找旋转排序数组中的最小值
搜索排序区间
寻找峰值
快速幂两个排序数组的中位数
合并K个排序链表
变形词子串哈希函数
复制带随机指针的链表
最小子串覆盖
搜索二维矩阵旋转图像
岛屿的个数
螺旋矩阵
宽度优先搜索
克隆图被围绕的区域
拓扑排序
单词接龙
实现一个链表的反转链表求和 II
删除链表中的元素
LRU缓存策略
合并两个排序链表
两个链表的交叉
翻转链表 II
复制带随机指针的链表
带环链表
统计数字名人确认
最长连续上升子序列
最大子数组差
最长公共前缀
快排摆动排序
最大间距
最接近零的子数组和
四数之和
数组划分
第K大元素
深度优先搜索
N皇后问题图是否是树
带重复元素的排列
分割回文串
数组划分逆序对
合并区间
搜索旋转排序数组
最大子数组
删除排序数组中的重复数字
第二大的数组
先递增后递减数组中的最大值
两数和 – 输入的数据是有序的
两个排序数组的中位数
在大数组中查找
颜色分类
合并排序数组
无序数组K小元素
奇偶分割数组
主元素寻找缺失的数
买卖股票最佳时机
删除数字
落单的数
最大子数组差
线段树查询线段树的构造
线段树的修改
区间求和
统计比给定整数小的数的个数
带最小值操作的栈用栈实现队列
有效的括号序列
简化路径
反转整数将整数A转换为B
整数排序
字符串处理
罗马数字转整数回文数
乱序字符串
有效回文串
翻转字符串
最长无重复字符的子串
字符串压缩
比较字符串编辑距离II
看完这篇文章后,有3件小事,能帮助你快速提升自己哟:
1、试听九章基础算法班(Java),国内TOP1名校毕业、资深Java工程师、ACM算法竞赛金牌获得者张三疯老师讲授。
2、点赞+关注 九章算法,让更多人能看到这篇文章,同时你的点赞也鼓励我创作更多优质内容。
编辑于 2020-11-09
赞同 471
12 条评论
喜欢收起
继续浏览内容
发现更大的世界
学数学的
535 人赞同了该回答
做人做事就要喝最烈的酒,日最野的狗。
我不明白为什么有那么多说被《算法导论》打击到的。我倒是很喜欢这本书,并且推荐初学者或者看过其他不那么“难”的算法书的同学好好看看这本书。
讲讲我学习算法的经历吧。大一刚进入大学时就对算法感兴趣,我是数学类专业的,专业课里没有算法课,就打算看书自学一下。咨询学校ACM校队学长该看什么书,他们都推荐刘汝佳的《算法竞赛入门经典》,还说《算法导论》里都是伪代码不利于初学者学习。但是这本书我看名字就把它pass掉了,因为我不打算搞ACM,只想凭兴趣随便学学算法吧。当时在知乎上看到大家推荐的这本Sedgewick的《Algorithm》,就买了一本英文影印版来看,感觉一般。可能是因为学数学的吧,总觉得写的不“严谨”,几乎不讲算法的证明。于是翻了几页就放下了。这之后在图书馆里看到一本《算法技术手册》,感觉挺薄的可以拿来入门。结果看了三十业都是在讲作归并排序,选择排序者如何处理一个小bug的故事,最后三十页左右终于涉及到了排序算法但只是给出归并排序与选择排序的运行速度随输入规模的变化情况比较图,还是没开始正经讲算法。第二天我就还了这本书,然后中断了算法学习。终于到大一的暑假想要重新开始学习算法,这时捧出久仰大名早早买好而吃灰已久的《算法导论》。这之前翻过几页,但觉得不容易沉浸入作者讲解知识的模式中,然而这时再看觉得字字珠玑,引人入胜,在清晰地讲解知识的同时注重了严谨性。这就是我一直期待的算法书呀!那个暑假有实习,但我还是每天抽时间看《算法导论》。然而它篇幅的确太大,我这个寒假还在看它。不过看这本书对我来说已经是一种享受了,多看一段时间也无妨,嘿嘿。
根据我学习算法的经历,我列一些不成熟的小建议吧:
《算法导论》,读中文英文都行。中文翻译质量尚可,个别读不通顺的地方仔细想一下或者对照英文就能明白。读《算法导论》时不做习题就失去了一半的意义。不过在做题苦思冥想而不得时,可以参考这个repository:gzc/CLRS
github.com
3. 斯坦福Tim Roughgarden教授的算法专项课程。教授人长得帅,声音好听,尤其是课讲得超棒!下面链接是专项课程第一门课 Divide and Conquer, Sorting and Searching, and Randomized Algorithms。这门课是收费的,但是点开专项课程中单独一门课的主页。可以找到申请助学金的选项,按要求填好申请,15天后就会100%通过申请,然后就可以访问课程的全部资源了。
Coursera
Online Courses From Top Universities. Join for Free
www.coursera.org
4. 一本机械工业出版社影印的书《算法概论》,因为三位作者分别叫Dasgupta,Papadimitriou,Vazirani,人称这本书为DPV。它在不长的篇幅里(大概只有《算法导论》的四分之一)涵盖了基本的算法知识,同时兼顾了严谨性,是本不错的入门书。
最后,快过年啦,给我看过的算法书来张全家福,嘿嘿
编辑于 2018-02-14
赞同 535
102 条评论
喜欢收起
继续浏览内容
发现更大的世界
知乎用户
470 人赞同了该回答
我第一次学算法直接看《算法导论》,结果信心大受打击。后来发现Robert Sedgewick在Coursera上出了一系列算法视频教程,把一个算法以动画的形式展现出来,非常适合新手。课程名字就叫Algorithm,普林斯顿大学的,分为Part 1和Part 2。
看视频一边看一边做笔记,看完一个单元跟着把代码写一遍。看完整个教程之后把所有算法都默写一遍,忘记的算法复习一遍。就酱。
编辑于 2014-08-26
赞同 470
31 条评论
喜欢收起
继续浏览内容
发现更大的世界
Linux C/C++ 开发,:编程珠玑
45 人赞同了该回答
推荐几个算法可视化的网站!!!
其他答主已经回答了很多方法或者推荐了书籍,我在这里推荐几个算法可视化的网站
Data Structure Visualizations
网站地址为:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
目前已经有很多常用的数据结构与算法的可视化,例如常见的栈,队列,递归,二叉树等等。
我们点一个二叉查找树进去看看:
开始时,是一片空白,左上角有几个按钮,为insert,delete,find,print,分别用于二叉查找树的插入,删除,查找和遍历。而这些过程的每一步都在你的掌控之中,你可以看到每一个节点是如何插入或者删除的。
还有很多其他算法的可视化,非常简洁直观,值得一试。
该网站特点:
算法可视化界面简洁直观过程可控制
VisuAlgo
网址地址为:https://visualgo.net/zh/。这个网站涉及的算法就更加全面了。从首页就可以看出来不一样了,不仅支持多种算法可视化,还支持搜索。
而它除了提供和前面一个网址类似的算法动画以外,还提供大量的文字讲解:
而在执行动画的时候,旁边仍然会有文字描述当前步骤,并且左下角还有算法复杂度的注释说明。
该网站特点:
算法可视化文字讲解复杂度备注图形可操控调整
algorithm-visualizer
网址地址:https://algorithm-visualizer.org/
它支持的算法种类也很多,除此之外,它还提供java,c++,js代码。而控制台也输出着整个过程来帮助你理解算法。
来看一个冒泡排序:
该网站特点:
算法可视化有代码有控制台输出帮助理解算法种类丰富
原文地址:算法可视化网站助你学算法
[编程珠玑]:专注但不限于计算机编程基础,Linux,C语言,C++,数据结构与算法,工具,资源等编程相关[原创]技术文章。
编辑于 2019-07-16
赞同 45
添加评论
喜欢收起
继续浏览内容
发现更大的世界