程序员必须掌握哪些算法？
不 BB，直接上干货，非科班出生，毕业工作后才开始学算法，到目前学了 4 年 ！！！ 为了让你对数据结构和算法能有个全面的认识，我画了一张图，里面几乎涵盖了所有数据结构和算法书籍中都会讲到的知识点。  这里面有10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。 掌握了这些基础的数据结构和算法，再学更加复杂的数据结构和算法，就会非常容易、非常快。 这里也给大家推荐一个特别适合新手免费刷题的网站  算法相关内容非常全面，从基础入门到进阶提升，所有必备知识点都包含了，而且牛客不光是一个刷题网站，还是一个交流学习平台，发个问题总有热心的大佬帮助！ 如果觉得不错，别忘了双击点个赞哦。 在这里也送大家一本帮助我拿到BAT 等一线大厂 offer 的算法笔记，是一位阿里大神写的，对于算法薄弱或者需要提高的同学都十分受用，算法一定是计算机学习的重中之重： 貌似手机端打开连接有的会出现问题，可以点击这个总结看看： 这里补充一下，无论是学习算法还是学习编程的任何一个技术点，想要得到提升，最好的一个方法就是去阅读，阅读优秀牛人的分享，目前主流的程序员习惯阅读的博客网站中，掘金社区属于质量不错的一个，内容包括前端、后端、Android、iOS、人工智能等等，各个方向，各个技术点都有，C++程序员需要的知识都能找到。 喜欢在掘金社区阅读的小伙伴可以通过下方链接了解。 看动画轻松理解时间复杂度（一） 看动画轻松理解时间复杂度（二） 冰与火之歌：「时间」与「空间」复杂度 每个程序员都应该收藏的算法复杂度速查表 五分钟了解一下什么是「贪心算法 」 有了四步解题法模板，再也不害怕动态规划！ （进阶版）有了四步解题法模板，再也不害怕动态规划！ （再进阶版）有了四步解题法模板，再也不害怕动态规划！ 浅谈什么是分治算法 看动画轻松理解「递归」与「动态规划」 浅谈什么是动态规划以及相关的「股票」算法题 深度解析「正则表达式匹配」：从暴力解法到动态规划 「多图警告」手撕排序算法 – iOS进阶必备 十大经典排序算法动画与解析，看我就够了！（配代码完全版） 这或许是东半球分析十大排序算法最好的一篇文章 几道和「广度优先搜索」有关的算法面试题 初识广度优先搜索与解题套路 从简单二叉树问题重新来看深度优先搜索 二分查找算法详解 一网打尽！二分查找解题模版与题型全面解析 面试官，我会写二分查找法！对，没有 bug 的那种！ 动画：BM 算法中的坏字符规则与好后缀规则 动画：七分钟理解什么是KMP算法 动画：什么是 BF 算法 ？ 动态规划之 KMP 算法详解（配代码版） 如何高效对有序数组/链表去重？ 超详细！详解一道高频算法题：数组中的第 K 个最大元素 一道简单的数组遍历题，加上四个条件后感觉无从下手 数组特性的妙用！如何找到「缺失的第一个正数」 剑指 offer 第一题：二维数组中的查找 动画：什么是单调栈？ 在数据结构中穿针引线：链表实现栈和队列 从简单的线性数据结构开始：栈与队列 五分钟学算法小知识：用栈实现队列/用队列实现栈 几道和「堆栈、队列」有关的面试算法题 超详细！图解「合并 K 个排序链表」 动画：面试如何轻松手写链表？ LeetCode 上最难的链表算法题，没有之一！ 链表算法面试问题？看我就够了！ 看动画轻松理解「链表」实现「LRU缓存淘汰算法」 从简单的线性数据结构开始：穿针引线的链表（一） 在数据结构中穿针引线：链表实现栈和队列 五分钟速读：什么是散列表（哈希表）？ 什么是哈希洪水攻击（Hash-Flooding Attack）？ 几道和散列（哈希）表有关的面试题 如何判断一个元素在亿级数据中是否存在？ 面试前准备：二叉树高频面试题和答案 懵逼树上懵逼果：学习二分搜索树 LeetCode 二叉树问题小总结 从简单二叉树问题重新来看深度优先搜索 几道和「二叉树」有关的算法面试题 详解什么是平衡二叉树（AVL）（修订补充版） 【面试现场】为什么 MySQL 数据库要用B+树存储索引？ 字典树概念与题型解析 面试官：为什么 MySQL 的索引要使用 B+ 树，而不是其它树？比如 B 树？ 心里没点 B 树。。。 数据结构与算法——最小生成树 植树节，程序猿种的那些树 数据结构与算法——2-3-4树 数据结构与算法——2-3树 看动画轻松理解「Trie树」 浅谈什么是图拓扑排序 数据结构与算法——图论基础与图存储结构 数据结构与算法：三十张图弄懂「图的两种遍历方式」 数据结构与算法——图最短路径 学习数据结构和算法的过程，是非常好的思维训练的过程，所以，千万不要被动地记忆，要多辩证地思考，多问为什么。 如果你一直这么坚持做，你会发现，等你学完之后，写代码的时候就会不由自主地考虑到很多性能方面的事情，时间复杂度、空间复杂度非常高的垃圾代码出现的次数就会越来越少。 你的编程内功就真正得到了修炼。 2020 年 01 月 13 日补充： 入门的同学，我建议你不要过度追求上去就看经典书。 不要一来就拿着《算法导论》开始啃，初学就去啃这些书肯定会很费劲。你一旦啃不下来，挫败感就会很强。 然后就放弃学算法了。 所以，入门的同学，我建议你找一些比较容易看的书来看，比如《大话数据结构》和《算法图解》。 不要太在意书写得深浅，重要的是能不能坚持看完。 《大话数据结构》 这本书最大的特点是，它把理论讲得很有趣，不枯燥。而且每个数据结构和算法，作者都结合生活中的例子进行了讲解， 能让你有非常直观的感受。 虽然这本书有 400 多页，但是花两天时间读完，应该是没问题的。 如果你之前完全不懂数据结构和算法，可以先从这本书看起。 《算法图解》 跟《大话数据结构》走的是同样的路线，就像这本书副标题写的那样，“像小说一样有趣的算法入门书”，主打“图解”，通俗易懂。它只有不到 200 页，所以内容比较少。 作为入门，看看这本书，能让你对数据结构和算法有个大概的认识。 当然，这些入门书共同的问题是，缺少细节，不够系统，也不够严谨。 所以，如果你想要系统地学数据结构和算法，看这两本书肯定是不够的。 通过基本入门算法书的调教，你已经逐渐体会到了算法的魅力，现在正是时候踏入基础系列算法的领域！！！ 这些书籍需要你费点心思去阅读。 很多同学在学习的过程中，看到一篇算法科普文章经常会有这样的想法。 哎呀，要是文章的代码是 Java 语言就好了呀。 哎呀，要是文章的代码是 Python 语言就好了呀。 虽然代码并不会很严重影响阅读，但还是有很多强迫症的同学喜欢看到文章的解释代码是自己擅长的。 我这里推荐《数据结构和算法分析》，这本书非常系统、全面、严谨，而且又不是特别难，适合对数据结构和算法有些了解，并且掌握了至少一门编程语言的同学。而且，这个作者也很用心。 他用了三种语言，写了三个版本，分别是：《数据结构与算法分析 ：C 语言描述》《数据结构与算法分析：C++ 描述》《数据结构与算法分析：Java 语言描述》。 大家都知道，对于程序员来说很大程度上算法就是为了应付面试的。 所以，推荐三本有益于面试的书籍，分别是：《剑指 offer》《编程珠玑》《编程之美》。 《剑指 offer》这本书的目的非常明确，就是为了面试。 这本书几乎包含了所有常见的、经典的面试题。如果能搞懂这本书里的内容，应付一般公司的面试应该不成问题。 面试之前也可以去牛客看看笔面经，知己知彼百战不殆！ 我做了一个 图解《剑指 offer》的小程序，应该能帮助你学习，感兴趣的可以在微信搜索 图解剑指offer。 我也在 B 站录制了一些图解剑指 offer 的免费视频课程，感兴趣的也可以看看，每个视频控制在5分钟以内。   《编程珠玑》这本书的豆瓣评分非常高，有 9 分。 这本书最大的特色就是讲了很多针对海量数据的处理技巧。这个可能是其他算法书籍很少涉及的。面试的时候，海量数据处理的问题也是经常会问的，特别是校招面试。不管是开拓眼界，还是应付面试，这本书都很值得一看。 《编程之美》这本书有多位作者，其中绝大部分是微软的工程师，所以书的质量很有保证。不过，这里面的算法题目稍微有点难，也不是很系统，这也是我把它归到面试这一部分的原因。如果你有一定基础，也喜欢钻研些算法问题，或者要面试 Google、Facebook 这样的公司，可以拿这本书里的题，先来自测一下。 正如 N.Wirth 教授所说的： 数据结构+ 算法＝程序。 遇到一个实际问题，充分利用所学的数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效实现。 这句话可能有点抽象，我举个例子给你们解释一下。 在工作过程中，我们多多少少都接触过 OAuth2 ，在使用 OAuth2 授权的时候，通常应用会弹出一个类似这样的信息： 1) 获取用户基本信息接口  2) 获取用户列表接口  3) 用户分组管理接口  。。。 思考一下，如果让你设计数据库，应该怎么设计信息存储权限？ 如何你熟练掌握了各种数据结构的特点的话，那自然而然想到使用 bitmap 来存储权限。 我们把权限划分成最小粒度之后，每一个 bit 都它的含义， 例如我们把权限划分为以下几种： 每勾选一个选项，就代表着这个权限被授权，为了保证可扩展性，我们使用一个 uint64 来保存这些 bit ，也就是说，我们一共可以划分 64 种细分权限，然后对这些权限进行组合。 例如，第一个 bit 如果设置了，那么就代表可以获取你的昵称、头像、地区、性别等基本用户信息， 第二个 bit 如果设置了，就可以用你的身份发状态。 数据结构的实际作用还有挺多，感兴趣的可以搜索以下知识点： 上面这些例子是关于数据结构的，我再举一个算法的例子，如果有帮助，不妨点个赞收藏一下，好的内容值得肯定。 同样的也来思考一个问题：计算机的缓存容量无论再大，缓存满了还是要删除一些内容，给新内容腾位置。 那么删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？ 这个时候采取的策略就是 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 面试，那么这些面试题必须掌握。 赶紧点赞和收藏吧~