程序员必须掌握哪些算法？ 第1页

不 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 缓存淘汰算法 的介绍可以看我之前写的一篇文章。

补充：

为了避免知乎大佬觉得我吹逼，先贴一下自己的 GitHub 地址，目前 70，000 star，全球排名 51 名。

https:// github.com/MisterBooo

算法是一种技能，是可以通过科学合理的方式训练出来的能力。

在想刷题之前，得从心里认识到接受刷题很重要，才能坚持去刷题。

江湖有个传言：国内刷 LeetCode，最多够你吃 1 年老本；湾区刷 LeetCode ，够你吃 10 年老本了。

为什么湾区的刷题性价比这么高呢？

你想想，电面考 4 道题，一道题值 5 万！单位是 Dollar ！

刷到就是赚到！！

想想是不是很刺激，有没有动力开始刷题了！可以提速刷题了！

就目前互联网的情况来说，无论是面国外大厂还是面国内大厂，如果想换工作都要去刷题，一面二面不丢你几道 Hard 题，都对不住你偷偷摸摸找个会议室假装开会实则面试的鸡贼。

同时，还得认识到一点，面试能力和你平时的工作能力其实差别挺大的。

有些人技术挺厉害的，但没有刷题，一面二面都过不了，而某些小镇刷题家，还真就靠刷题拿下了 Google、微软、脸书等大厂offer。

国内大厂也有这种趋势，比如字节，一大半都是面试题。

要不是他提前先看视频刷题，妥妥得凉凉。

所以，刷题很重要。

（PS：感谢大家耐心的阅读，算法是程序员的重中之重，必须攻克，大厂面试必考，顺便送一份阿里大佬刷Leetcode总结的算法笔记，如果你能吃透，那我相信80%的技术面试都会不在话下：

BAT大佬写的Leetcode刷题笔记，看完秒杀80%的算法题！

这本书的目录，非常经典：

刷题大概可以分为 4 个阶段。

1、纯小白，不知道怎么刷题，对很多概念都很陌生，各种数据结构和知识点几乎完全不懂，打开 LeetCode 第一题，满头问号。

有人相爱、有人夜里开车看海、有人 LeetCode 第一题都做不出来。

2、算法上基本已经入门，Easy 可以做出来，Medium 纠结半天也能有头绪，但基础不牢，比如字符转字符串还得 Google 一下。

3、刷了几百道题后，总结了自己的解题模板，参加周赛有时候甚至可以全部完成。

4、开始以 beat 100% 作为 AC 的目标了。

就目前的算法面试大环境来说，能达到第二阶段，中小公司可以应付过去了，到达第三阶段，字节、腾讯算法面试环节妥妥没问题了。

怎么样到达第三阶段？

给一下我的一些小建议吧。

1、如果目标是国内大厂，那么一定要刷足够的题，不需要把 LeetCode 上 2500 道算法题都刷完，但至少刷 200 道算法高频题，这些高频题我都写了题解同时也录制了视频，

在这个链接总结了：https://www.algomooc.com/1659.html

2、面试前一周以看题为主，因为刷题也刷不了几题，多看看自己总结或者别人总结的模板，比如回溯算法模板，掌握后，几十道回溯题都不在话下。

一些模板：

3、刷题过程需要注意难度要循序渐进，算法训练是一个系统工程，需要循序渐进，太过于急功近利，反而容易因做不出难题而产生挫败感，带来反效果。

如果你本身有基础，熟练度高，那你刷简单的 LeetCode 应该是几分钟一题，几分钟一题的，花不了你多少时间。

如果你刷简单都花费很长时间，说明熟练度不够，就更应该从简单开始，然后过度到中等，再过度到困难。

并且，目前国内大厂的算法考察，基本不会超过 LeetCode 中等难度，上限难度基本都是 LeetCode 中等题里面的中等难度，所以不要太去纠结难题怪题偏题。

把高频题掌握就行了：https://www.algomooc.com/1659.html

再退一步，如果你觉得 LeetCode 的题目太难，可以先从《剑指 Offer》上的算法题开始学起。

为了帮助大家更好的入门学习算法，经过半年的积累，我给大家卷了《剑指 Offer》系列的三十道题目，结合动画的形式录制了视频，相信能帮助你更好的刷题。

领取地址：

4、按算法分类来选题，比如一个时间段，只刷链表题，刷得差不多的时候，接下来再刷二叉树的题。

这样做有几个很明显的好处。

一、持续地刷同个类型的题目，可以不断地巩固和加深理解，可以总结出自己的思考路径或者解题模板。

比如链表题目，就会去思考虚拟头节点、双指针、快慢指针。

二、可以更全面地接触这个数据结构，算法的各个变种，这会促使你对这个数据结构，算法的理解更加全面和深刻，学习的效率会更高。

我一直认为读书是世界上性价比最高的成长方式，书很便宜但分量很重，是让我们摆脱平庸走向卓越的方式之一。

对于计算机专业的学生而言，读计算机经典书籍不光能让你快速提升知识和能力，更会让你在校招之际如虎添翼。

书籍下载：计算机必看经典书籍（含下载方式）

最后，再给大家送上点干货！

下面这是一个高赞回答合集，建议大家点赞&收藏，Mark住别丢了，大学期间绝对用得上。

1、怎么学好数据结构，看下面这个回答，已经获得了 21000+ 的赞和 50000+的收藏。

2、如何系统地学习算法，看下面这个回答，已经获得了 11000+ 的赞和 26000+的收藏。

3、新手该如何使用 GitHub，看下面这个回答，如果在大学期间就知道使用 GitHub ，那么能力远超同龄人。

4、想成为一名优秀的程序员，那么这些程序员平时都喜欢逛的论坛怎么说你也得收藏一些吧。

5、无论别人怎么说，我都是坚定不移的选择计算机专业。

6、如何系统地学习 C++ ，这个回答能帮你找到路线。

7、想要准备 Java 面试，那么这些面试题必须掌握。

赶紧点赞和收藏吧~

我觉得两个算法是必须要掌握的。

第一个算法是：怎么算时薪。

第二个算法是：钱以外的东西能带来的幸福度的量化算法

温酒的答案说的好极了，我也发挥下：

第一个算法是计算终身年薪

终生范围的年薪。以下数字都是假的，只是说明算法，无实际意义。

比如26岁可以开始工作，如果40岁就下岗，实际上一年100万，也只有1400万，要除以整个工作年龄（65-26 = 39），平均年薪大概只有30多万。而且累积税率下，高收入年份集中在26-40岁非常吃亏。

但，这没有考虑到房价上涨因素，因为房价上涨时期，前14年的收入会因为房产而大量增值，使得算法更加复杂。

还有比如假设能做到50岁，那么晚工作5年（比如多读个火坑博士）损失的钱是多少呢？假设起薪是100万，50岁下岗时是200万一年，实际上损失的是最后5年的收入，大概200X5 = 1000万。所以写码要趁早。

其次要算地点年薪。比如工作30年同样年薪，在一个房价上涨的地区，会在退休时能提出更多的钱，尤其是50多岁把一线城市或是加州的房子一卖回乡下养老或是环游世界，美滋滋。

第三要算成长年薪，同样100万的工作，有些技能会保证10年后不仅不失业，反而会上涨到150万，而有些技能会在衰退中，10年后可能只有50万甚至失业。

第二个算法是LeetCode一道题的价格

我当年做过粗略计算，很多LeetCode题做一道可以提升年薪300-500美元。假设400道Medium、Hard题可以拿到大厂Offer，那么很可能不刷题的人上限也就是不到20万，而大厂senior上限可以轻松35-40万。差不多20万的差距，除以400 等于 500美元。

所以一道Medium或是Hard题的价值大概是500美元年薪每年。而且这个可怕在于是累积的，每年500, 20年下来就是1万块一道题。这还不算大厂背景对个人的加分、对失业的强抵抗力等，只是单单年薪上的收入（当然，税后会少很多）。

这个“算法”掌握了，你才有动力去学习LeetCode的算法，你就不会觉得它折磨人了。LeetCode这么一看，简直跟金山一样，还不去挖？

第三个算法是算时薪和效率

Google和微软的时薪就比较高，FB亚麻就相对低。这种时薪不光是用hours计算，还用体力计算。比如微软上班干两个小时活，扯六个小时蛋，然后回家精神抖擞，可以去卖房子、创业、炒股票等，相当于一天多出来4个小时有效时间；FB上班干七个小时活，被扯两个小时蛋，通勤再耗去一个半小时，回家就瘫痪了。

千万别看什么华为他们996效率高。我算过，他们效率很低：中午吃饭吃一个小时，还要午休一个小时，加上重新进入状态的时间，中国的12小时一天，实际上也就相当于美国的9小时一天左右，因为我们这里9小时是真的9个小时。

第四个算福利

公司免费三餐大概省多少钱？早饭就算0（因为可以不吃），午饭算10美元，晚饭算15美元，一年工作220天，25X220 = 5500美元。但这是税后的，所以5500 要乘以1.5（税率按33%近似） = 8250美元税前。

还要算时间账：午餐和晚餐大概各省半个小时的话（不需要开车出去或是下楼吃等），一年会省220小时，相当于多出来220/8 = 27天。

还要算健康账：因为公司有大量的蔬菜水果等。食物种类多变更有利于身体。

还要算士气账：免费三餐大概能提升10%-30%的员工士气（我是吃货，所以+30%）。

结论：三餐免费每年带来很大的收益，无论公司还是员工。

第五个算面试大厂的成功概率

假设一个人面一家大厂的成功率是25%，大厂有8家，冷冻期均是一年，连续坚持不懈面5年，一个offer都拿不到的概率是：

（1-0.25）^ (8*5) = 0.75 ^ 40 = 0.00001 = 0.001%

假设这人只有5%的成功率，且一年只面了4家，连续面5年，一个offer都拿不到的概率是：

（1-0.05）^ (4*5) = 0.95 ^ 20 = 0.3584 = 35.84%

可见，一个只有5%成功率的人，坚持面5年也有大概2/3的概率能进大厂。

第二个假设跟我在现实中的观察很相似，也解释了为什么很多看似不强的人也进了大厂。