为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？

NoiseFloor · 发表于 2021-7-3 21:55

KaaPexei · 发表于 2021-7-3 21:56

你把前三章弄懂个六七成，就能超越95%的程序员……
不是说这书多难，而是说很多人不了解程序员这行业低水平者占比率有多高。就像去年总理说中国有6亿人月收入不到1000，让很多声称北上广月入两万不如狗的人瞠目结舌。
很多半路出家甚至大学计算机专业出身、干了好几年的程序员，这辈子仅有的认真学技术的经历也就是培训班的三个月（科班四年学了个寂寞最后还得去培训班的情况太常见了）之后就是百度CSDN复制粘贴代码了。
学算法是不可能的，这辈子都不会学算法。用现成的库不香吗？效率低就换一个，最后粘在一起勉强能用就行。反正熬两三年当个主管或转产品或售前，这辈子就再也不会写一行代码了。混不上去的话，宁可转行也不会再浪费时间深造的。
没法子，这是国内现状，既然绝大多数IT企业成功靠的都不是技术超越同行，而是玩金融、骗投资、搞垄断、拼销售、拉关系，那轻视技术就是个普遍现象。愿意提高自己算法能力并真正得到重视的也只是几个技术小圈子，而非广大程序员群体。

至于算法导论这本书么，其实跟大多数公认优秀的技术书籍一样，不是什么武林秘籍，咬着牙反复读几遍就能脱胎换骨。建议初读时跳过太艰深啃不动的细节，多尝试理解一些概念和算法本身要解决的问题，日后遇到刷不懂的算法题或者实际项目中的难点，不妨回来当工具书参考一下，很可能就恍然大悟茅塞顿开了。

kirin77 · 发表于 2021-7-3 22:02

别说算法导论了，当你工作几年就会明白，，以下几个任何一个都可以超过90%程序员：
1.把事情想明白，说清楚，跟别人商量好
2.写代码，注意边界条件和编码规范，写单测，基本做到无bug提测
3.工作中做好计划和进度跟踪，沟通和汇报，不把问题遗留到变成事故
4.思考和分析，如何优化目前的工作流程，引入工具和方法，提升生产效率
5.把自己工作中用到的技术用熟，搞清楚原理，优点短处，适用场景
6.不断接触新技术思想和工具，完善自身知识体系结构
7.深入学习至少一个常用开源项目，源码层面系统掌握这项技术
8.持续坚持学习和技术内容输出，每个星期产出2篇原创技术文章

量子计算9 · 发表于 2021-7-3 22:06

如果只是做一个普通程序员，说的极端一点：《算法导论》根本不用去看。把《算法》那本书上的内容看懂就行了。
如果有志学习算法设计，甚至算法分析，我认为《算法导论》适合做查阅的参考书，因为这本书涵盖的范围很全面，而且过于全面了。
如果想一年甚至一学期把其中所有的知识都消化了，我认为不可能，我看到有知乎网友说博士也会查阅这本书，我是相信的。因为里面有些内容讲的很简略，这本书做了解释，记住可以，想明白怎么回事比较难。
比如，第四章，divide-and-conquer里面讲了解recurrence的方法，到4.5的时候，能只用这本书就搞明白的那真需要不一般的脑子。
这些我都看了，像喝了一碗疙瘩汤，消化不了。例如，我在求解一个ternary tree的剪枝问题的时候我做错了，我看到别人的错误解答也挺有道理。直到我看到Jon Kleinberg写的Algorithm Design，我才明白那个剪枝问题错在哪里了。
那么，跟Algorithm Design对比一下，发现Algorithm Design讲解的很顺畅，回过头来再看 Introduction to Algorithm，确实是“包罗万象”的一本书，不辜负“导论”这个名字，猛的给你打开一扇算法的大门，门外一阵狂风差点把你吹翻了。

简单补充一下，《Algorithm Design》是一本书，就像网友说的，用英文是为了方便大家找这本书，还有著者的名字也是英文，也是为了方便查。
我还是比较推荐这本书的，国内也有出版了。比如， recurrence relation求解的时候，这里讲的substitution method要比导论那本书详细多了，还讲了partial substitution，很实用。另外，这本书讲的算法案例不是那些最常见的程序员要掌握的基本算法，而是开始尝试去解一些经济、社会、管理领域的实际问题。对于自己踏上算法设计这条路应该是有帮助的

xiangtingsl · 发表于 2021-7-3 22:08

算法导论是知乎上经常被拿来CM的书了，关于这本书我回应几点。

可以不看数学证明吗?
看算法导论不看数学推导，犹如下了一部___电影却跳过了___。
算导这本书最大的特点就是对书中几乎所有的算法都给出了正确性的证明和复杂度的分析，这一切其实是深入学习、研究算法的基础。毕竟当算法困难到一定程度你就不太可能直观判断它是否正确、复杂度究竟如何了。比如我最近在看的计算几何，也是通过构造恰当的循环不变式来证明正确性，通过摊还分析等手段给出算法复杂度。
当然对最基本的算法，不通过数学手段，而是直观的理解其正确性、复杂度也是可以的，但是这种情况下算导其实算不上最佳选择；而且事实上某些算法算导的实现会略有区别，就是因为它有一些用于证明推导的辅助变量。

就算啃完了算导也只是学会了算法?
当然指望看完算导一本书就大包大揽的学会一切那是不现实的，但是要说看完算导只学会了算法那也是很扯的。
一个最基本的问题是，算导的后续章节经常把一个问题转化为前面章节的问题，然后说这个问题前面已经研究清楚了，但是你大概率会发现之前写的代码在这种情况下要么根本没法用要么还有一坨bug。在反反复复的修改完善之中，代码的可扩展性、可维护性会得到极大地提升，并且合理的组织代码的能力也会得到很大的提高。

KaaPexei · 发表于 2021-7-3 22:18

上学的时候，跟你一样傻，以为看的书多而全，就肯定比别人强。
我大学时候也很傻，为了校招，看了不下于五本算法书，加上LeetCode，刷了大半年。
总共一两千道题啊……不刷怕考到……忘了刷，刷了忘……毛都快掉没了……
现在工作近十年，辗转几个大厂，由当年的应试者变成了出题人，才知道，完全不必这么辛苦。
任何事情都遵循28原则，我们只要把握住那20%，就能拿到80分！
凡事都讲究性价比！
《算法导论》是一本好书，但是他太难了，就算是现在的我，再不借助资料的情况下，也绝看不完。

如果单纯只是为了应对校招、巩固基础知识，杀鸡何必用牛刀？？？
省下来的时间，谈个女朋友，它不香么？？？！！！
这里把我这些年的出题经验告诉大家，希望大家知道哪些是重点，应该怎么学数据结构和算法。
直接上干货，我花了两天的时间做了一张图，涵盖数据结构和算法书籍中都会讲到的知识点。并给出了常用算法的平均时间复杂度，对于必须要学的内容前面加了星标

这里面涉及到了近二十种数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；超四十种常见算法思想：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
掌握了这些基础的数据结构和算法，再学更加复杂的数据结构和算法，就会非常容易、非常快。
需要高清无水印思维导图源文件的小伙伴，可以点击这里获取：
算法导图及推荐学习资料下载长文预警，以下内容涵盖了十几年来学习算法的心得，总结出来供大家参与。如果看完这篇文章，还学不好算法，尽管来骂我。

收藏是点赞的五倍啊，原创不易，小伙伴们双击屏幕点个赞支持下吧，手动叩谢了。

文章写了很久，我相信它一定能帮到你，也希望大家能给我个赞，以示鼓励，谢谢

目录：

一、数据结构与算法的区别

很多同学搞不明白，数据结构与算法有什么区别，甚至有些同学以为数据结构中就包含了算法。
其实，是字面意思就能知道个大概，数据结构主要讲解数据的组织形式，换句话说，我就是我们要怎样把这些数据存储起来，所以有列表、堆、栈、树、图，这是数据结构的重点。
而算法，则注重的是思想，比如列表里的元素怎么排序、怎么在当前的存储结构中找到最大的数和最小的数？等等，说白了就是解决现实中问题的思想。所以才会有分治思想、贪心思想、动态规划这些经典算法。
二、数据结构怎么学

关于数据结构，我想说的是，它是这四大件中最简单、最基础的一个。离开了数据结构，几乎任何的程序都会失效，所以在讨论数据结构的时候，常常要把算法也连带着说一说。
要单纯地掌握常见的数据结构，就如同拆解一个个精妙的仪器件一样有趣和简单。正因为数据结构这个东西在程序中的作用，和仪器部件特别相像，不同的数据结构有着不同的特性，因此要想学好数据结构，图解是必备武器！
这里强推中国大学上，浙江大学的开设的《数据结构》课程，涵盖了常用的数据结构和算法。
数据结构_浙江大学_中国大学MOOC(慕课)辅以教材参考书，强推《大话数据结构》，光看封面你就知道这本书的风格了
没错，这就是大名鼎鼎的《大话设计模式》的作者出的，绝对顶。
三、怎么学习算法

算法课常常和数据结构课放在一起，在有些高校中，会存在“数据结构与算法”和“算法设计与分析”这样的两门课。
学习算法的套路很简单，多看、多写、多上机，既然是思想的集合，看得多了，自然无师自通。
至于刷题，很多同学都知道要刷LeetCode。
LeetCode题库：（2123题）
题库 - 力扣 (LeetCode)总共两千多道题，而且有些题，非常难，就算每天10题，也至少刷半年。这显然不适合绝大部分同学。
所以，我们要找到最核心、最重要的题集，即可
比如，如果时间紧张，可以先刷《程序员面试宝典》里的题目，总共109题。
《程序员面试宝典》刷完以后，有时间，可以再刷《剑指offfer》的题目，共75题。
《剑指offer》因为这两本书，都是面向面试的高频题汇总，自然有很多题目是重合的。这也正能说明这两本书的重要性。
如果专攻面试的话，还有两本不错的书推荐：
《编程珠玑》这本书的豆瓣评分非常高，有 9 分。
这本书最大的特色就是讲了很多针对海量数据的处理技巧。这个可能是其他算法书籍很少涉及的。面试的时候，海量数据处理的问题也是经常会问的，特别是校招面试。不管是开拓眼界，还是应付面试，这本书都很值得一看。
《编程之美》这本书有多位作者，其中绝大部分是微软的工程师，所以书的质量很有保证。不过，这里面的算法题目稍微有点难，也不是很系统，这也是我把它归到面试这一部分的原因。如果你有一定基础，也喜欢钻研些算法问题，或者要面试 Google、Facebook 这样的公司，可以拿这本书里的题，先来自测一下。
当然，我也有一本谷歌师兄总结的高频面试算法习题集，包含了常见的数据结构和算法汇总，无论是排版还是内容，都是非常棒。
所有这些书，我都为大家找到并下载好了，需要的小伙伴可以直接领取。这回得帮我点赞了吧
算法导图及推荐书籍资料下载四、算法太难懂？那是你不知道有这些模拟网站

算法的难点在于，根本没办法在脑子里抽象出它的步骤啊
对于做个几何题都费劲的男孩子来说，那更是要了他的亲命了。
今天，我就给大家推荐几个算法可视化的网站。
没错，就是写了代码以后，可以看见他们是怎么一步步求出结果的。
1、https://visualgo.net/en
目前网站支持中文，印尼文，日文等多语言版本。
最关键的是，它几乎包含了所有算法！！！！
在搜索选项中你可以根据关键词查找到你想要的算法。
点进去一个具体的算法之后，会有两种方式的可视化呈现方式，一种是电子讲座模式，一种是示例模式。其中示例模式是以动画方式呈现，你可以控制动画的快进与倒退，电子讲座模式是以知识点讲解模式呈现，你可以手动控制页面的进度。两种方式都可以帮助你演示每个步骤的过程代码。
接下来我们演示一下冒泡排序的执行过程，如下图所示：
另外，你还可以创建一组自定义的数，然后让动画显示“你的算法”。
除此之外，还支持在线测试哟~
2、Algorithm Visualizer
在Algorithm Visualizer，大家可以很清楚的看到算法运行的整个过程，很直观，便于大家学习。
大家可以很清楚的看到，网站分为三部分，最左边是算法目录，大家可以选择自己感兴趣的算法，目前已经包括了很多算法了，比如二叉树、图、排序算法、动态规划等等经典算法。中间区域主要是算法演示以及运行log。右侧是代码以及算法运行按钮。
我们用它来演示一下冒泡排序的执行过程，如下图所示：
同时它是开源的，目前有35K个star，足以可见该项目的欢迎程度，这里推荐给要学习算法的各位。
https://github.com/algorithm-visualizer/algorithm-visualizer
3、Data Structure Visualization
目前已经有很多常用的数据结构与算法的可视化，如：常见的数组、链表、队列、二叉搜索树、红黑树、各种排序等，如下图所示：
比如，我们用它来模拟一个二叉搜索树，如下图所示：
我们再用它来演示一下快速排序算法，如下图所示：
把这些内容学会，算法应该说是非常牢固了，无论是校招还是工作，都已经非常够用了。
但程序员的人生不是只有算法的学习，我们还有校招、面试、青春饭等等的困惑，我把我这些年的所知所得，整理成了一本书，开源到github上了。相信会对大家很有帮助，大家可以去看.
目前还在持续更新，欢迎大家star。
地址：https://github.com/harvic/FightingCoder
好了，这篇就到这了，希望大家毕业都能找到好工作。
我是 @启舰，原创不易，帮我点个赞吧。

本人所有文章皆为原创，著作权归@启舰所有，未经授权，转载必究

量子计算9 · 发表于 2021-7-3 22:23

做好自己就行了。有人说就说呗，林子大了，肯定说啥的都有呀。别人说啥，会影响到你拿多少工资么？如果这个人不是你老板的话。
我觉得作为一个爱学习的人，肯定是好习惯。尤其是编程这一行，终生学习真的是要践行的。但学习和经历到了一定的程度之后，咱们应该少把眼光放在别人的身上去。你每多看一点书，就多一点进步。至于其他人看不看，你能不能超过多少人，那么在意干嘛呢？比来比去的多累呀。
这句话看似很对，但说起来也漏洞不少。
首先，值得肯定的是，弄懂《算法导论》90%还是挺不容易的，至少是一个优秀的计算机学习者了，算法和数据结构知识也相当扎实了。
但因为算法和数据结构不错，就说超过了90的程序员，这就不知道怎么推出来的了。
因为众所周知，编程能力和计算机基础知识之间，还是差别不小的。看懂算法导论，看懂上面的伪代码，不代表你的编程能力就一定优秀。
所以这就要看你说的弄懂是什么程度的弄懂了，是看懂并推导书上的公式，但并没有用具体的语言来实现这些算法和数据结构，那编程能力不一定就优秀。
再加上，大部分的工程项目中，不见得需要你掌握方方面面的算法和数据结构知识，只需要你对某一方面很熟悉。比如粗略来说，有前端和后端。
前端和后端对知识的要求也不一样。光算法和基础知识好，并不意味着你就分分钟能写出来好的项目代码。
其次，如果是想当程序员的话，其实最适合的算法书，确实是《算法》第四版，尤其是学习和使用Java的小伙伴们。
因为《算法》提供了高质量的Java可执行的代码，和一般的只提供伪代码的书籍大不一样。里面的很多代码本身就是很优秀的implementation，比如里面的union-find（并查集）数据结构的实现，在刷题的时候，大家都会看到这部分代码的影子。
这本书是很多很多学习算法和数据结构的人真正推荐的，算法导论实在是太大部头了。美帝的算法课，确实喜欢把《算法导论》当教科书，但很多名校却是把《算法》当成教科书，比如大名鼎鼎的CS61B，以及普林斯顿的教程，因为这本书本来就是普林斯顿的大神教授Robert Sedgewick的神作，该书还有配套的MOOC课程，以后有时间再写网课了。该书是特别棒的算法和数据结构的教程，全书提供Java的实现，而且大部分内容也放在了本书的配套网站上：https://algs4.cs.princeton.edu/home/本书的优点是会把算法详细的过程掰开揉碎地讲明白了。书里面有大量的配图，更不说配套网站上的ppt，简直就是艺术。一句话，1万分推荐。
其他的算法和数据结构类的书籍，可以参考下面的回答，但《算法》确实是大家应该吃透的。
哪本《数据结构与算法》最好？

acecase · 发表于 2021-7-3 22:24

（被知乎评为优质内容了，朋友们看完支持一下呀）
说这句话的人，我估计连《算法导论》的20%都还没理解，甚至都还没读完。
读90%，就超过90%程序员，这数字可真有零有整，编的甚至都不走心，两个90%。。。

对程序员来说，学算法只有三个目的：

我倒是相信90%的程序员只需要前两项。

好了，对于前两项，《算法导论》有用吗？有，但作用不大。
真的，真不需要看数学证明的，你不是做理论计算机科学：

然后给一下时间、空间复杂度就OK了。
真需要证明吗？完全不用。以上公司我全都面试过，大多数拿到过offer，所以我能理直气壮的说，真没必要。

所以，你只要找一本算法书入门，按着LeetCode，把常见题目刷完，理解了数据结构，这辈子估计都没啥需要《算法导论》的时候。
<hr/>痛快打脸
下次再有人讲这些话，你可以这样子问他：如何证明一个算法，比如插入排序，是正确的？
我相信，他就会支支吾吾了。
这时候，你学完这个，就可以啪啪啪的狠狠的打醒他，因为算法导论前几章就有教这个：
数学归纳法证明验证以下算法是对的
#define LEN 5
int a[LEN] = { 10, 5, 2, 4, 7 };

void insertion_sort(void)
{
  int i, j, key;
  for (j = 1; j < LEN; j++) {
printf(&#34;%d, %d, %d, %d, %d\n&#34;,
         a[0], a[1], a[2], a[3], a[4]);
key = a[j];
i = j - 1;
while (i >= 0 && a > key) {
   a[i+1] = a;
   i--;
}
a[i+1] = key;
  }
}

如何严格证明这个算法是正确的？换句话说，只要反复执行该算法的for循环体，执行LEN-1次，就一定能把数组a排好序，而不管数组a的原始数据是什么，如何证明这一点呢？我们可以借助Loop Invariant的概念和数学归纳法来理解循环结构的算法，假如某个判断条件满足以下三条准则，它就称为Loop Invariant：

第一次执行循环体之前该判断条件为真。如果“第N-1次循环之后（或者说第N次循环之前）该判断条件为真”这个前提可以成立，那么就有办法证明第N次循环之后该判断条件仍为真。如果在所有循环结束后该判断条件为真，那么就有办法证明该算法正确地解决了问题。

只要我们找到这个Loop Invariant，就可以证明一个循环结构的算法是正确的。上述插入排序算法的Loop Invariant是这样的判断条件：第j次循环之前，子序列a[0..j-1]是排好序的。在上面的打印结果中，我把子序列a[0..j-1]加粗表示。下面我们验证一下Loop Invariant的三条准则：

第一次执行循环之前，j=1，子序列a[0..j-1]只有一个元素a[0]，只有一个元素的序列显然是排好序的。第j次循环之前，如果“子序列a[0..j-1]是排好序的”这个前提成立，现在要把key=a[j]插进去，按照该算法的步骤，把a[j-1]、a[j-2]、a[j-3]等等比key大的元素都依次往后移一个，直到找到合适的位置给key插入，就能证明循环结束时子序列a[0..j]是排好序的。就像插扑克牌一样，“手中已有的牌是排好序的”这个前提很重要，如果没有这个前提，就不能证明再插一张牌之后也是排好序的。当循环结束时，j=LEN，如果“子序列a[0..j-1]是排好序的”这个前提成立，那就是说a[0..LEN-1]是排好序的，也就是说整个数组a的LEN个元素都排好序了。

可见，有了这三条，就可以用数学归纳法证明这个循环是正确的。

unityloverz · 发表于 2021-7-3 22:28

知乎又开始凡了？很多人表示“算法导论也没多难嘛”......真的？
算法导论第三版一共35章，10%不懂就是说最多3章半不懂咯？那看看下面这几章的内容，请在其中选出：完全不懂的（计1分）和大概懂一半的（计0.5分）。全懂可以不计分。注意总数不要超过3.5分哦：

我认识的人里面，没有人明确展现过能搞定90%算法导论的能力。我猜能搞定90%算法导论的几个熟人都在当教授。

zt3ff3n · 发表于 2021-7-3 22:32

刚开始我也是这么认为，直到我花了 100 多块钱买了本《算法导论》，才明白《算法导论》并不合适大家。。
一上来就看算法导论，只会让自己失去学算法的兴趣，算法导论这本书，大篇幅用于证明算法的可行性，一大堆数学公式，但这些，新手是不需要过多关注的。无需死磕算法导论，把我下面总结的学了，就能超越 95% 的程序员。
一、算法最最基础

1、时间复杂度
2、空间复杂度
一般最先接触的就是时间复杂度和空间复杂度的学习了，这两个概念以及如何计算，是必须学的，也是必须最先学的，主要有最大复杂度、平均复杂度等，直接通过博客搜索学习即可。
文章推荐：
什么是时间复杂度？
二、基础数据结构

1、线性表

不用说，链表、列表必须，不过重点是链表。
三分钟基础数据结构：如何轻松手写链表？
以后有面试官问你「跳跃表」，你就把这篇文章扔给他
2、栈与队列

特别是优先队列，再刷题的时候，还是经常用到的，队列与栈，是最基本的数据结构，必学。可以通过博客来学习。相关文章：
三分钟基础知识：什么是栈？
二叉堆是什么鬼？
【算法与数据结构】堆排序是什么鬼？
3、哈希表（必学）

哈希表相关的，推荐通过博客来学习，推荐文章：
Hash冲突之开放地址法
4、树

树相关是知识还是挺多的，建议看书，可以看《算法第四版》。相关文章：
三分钟基础数据结构：如何轻松手写链表？
以后有面试官问你「跳跃表」，你就把这篇文章扔给他
5、数组

树状数组其实我也没学过，，，，
这里给大家推荐一份刷题笔记，里面把各种算法题型以及经验都总结了，把这份笔记突击学习一下，很多算法考察，基本都稳了
两个月斩获 70k star，前字节大神刷题笔记三、各种常见算法

1、十大排序算法

对于十大算法的学习，假如你不大懂的话，那么我还是挺推荐你去看书的，因为看了书，你可能不仅仅知道这个算法怎么写，还能知道他是怎么来的。推荐书籍是《算法第四版》，这本书讲的很详细，而且配了很多图演示，还是挺好懂的。
推荐文章：
1. 漫画：什么是冒泡排序算法？
2. 漫画：什么是选择排序算法？
3. 漫画：什么是插入排序算法？
4. 漫画：什么是希尔排序算法？
5. 漫画：什么是归并排序算法？
6. 漫画：什么是快速排序算法？
7. 漫画：什么是堆排序算法？
8. 漫画：为什么说O(n)复杂度的基数排序没有快速排序快？
9. 什么是计数排序算法？
10. 十大排序算法极简汇总篇
2、图论算法

图还是比较难的，不过我觉得图涉及到的挺多算法都是挺实用的，例如最短路径的计算等，图相关的，我这里还是建议看书的，可以看《算法第四版》。
漫画：什么是 “图”？（修订版）
漫画：深度优先遍历和广度优先遍历
漫画：图的 “最短路径” 问题
漫画：Dijkstra 算法的优化
漫画：图的 “多源” 最短路径
3、搜索与回溯算法

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

我觉得动态规划是最难的一个算法思想了，记得当初第一次接触动态规划的时候，是看01背包问题的，看了好久都不大懂，懵懵懂懂，后面懂了基本思想，可是做题下不了手，但是看的懂答案。一气之下，再leetcdoe专题连续刷了几十道，才掌握了动态规划的套路，也有了自己的一套模板。不过说实话，动态规划，是考的真他妈多，学习算法、刷题，一定要掌握。这里建议先了解动态规划是什么，之后 leetcode 专题刷，反正就一般上面这几种题型。后面有时间，我也写一下我学到的套路，有点类似于我之前写的递归那样，算是一种经验。也就是我做题时的模板，不过感觉得写七八个小时，，，，，有时间就写。
文章推荐：
1. 告别递归算法，谈谈我的一些经验
2. 告别动态规划，谈谈我的一些经验
3. 动态规划优化的一些经验
4. 递归训练一：Leetcode 104.二叉树的最大深度
5. 递归训练二：Leetcode 62.不同路径
6. 递归训练三：剑指 Offer 16. 数值的整数次方
7. 递归训练四：Leetcode 4. 寻找两个正序数组的中位数
8. 动归训练一：Leetcode 198.大家劫舍
5、字符匹配算法

我写过两篇字符串匹配的文章，感觉还不错，看了这两篇文章，我觉得你就差不多懂 kmp 和 Boyer-Moore 了。
字符串匹配Boyer-Moore算法：文本编辑器中的查找功能是如何实现的？
6、流相关算法

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

对于上面设计到的算法，我都提供了感觉还不错的文章，建议大家收藏，然后可以利用零碎的时间进行阅读，有些人可能会觉得上面的算法太多，说实话，我觉得不多，特别是对于在校生的，上面涉及到的算法可以不用很懂，但至少得了解。至于书籍的话，如果你连基本数据结构都还不懂的，建议看《数据结构与算法》相关书籍，例如《大话数据结构》、《数据结构与算法分析》。如果你有一定的基础，例如知道链表，栈，队列，那么可以看《算法第四版》，不过这本书是用 Java 实现的，不过我觉得你只要学过 C，那么可以看的懂。
书籍推荐看这里，可以少走一些弯路：
少走弯路，必读计算机经典书籍推荐（含下载方式）这些算法的学习，虽然你觉得学了没有什么用，但还是那些话，它对你的影响是潜意识的，它可以给你打下很深厚的基础内功，如果你想走的更远，那么我推荐学习，标注必学的，那么我觉得，你是真的需要抽时间来学习下，标注原理与应用的，代表你可以不知道怎么用代码实现，但是必得知道它的实现原理以及应用，更多算法的学习。
算法的学习没有太多捷径，离不开刷题，刷多了就会有感觉了，这里再给大家推荐一份某大佬的 leetcode 刷题笔记，汇聚了上千道 leetcode 题解，并且代码都是 beat 100%：下载链接：
清华学霸的刷题笔记(leetcode最优解)顺便讲解一些算法技巧吧

说到算法技巧，必须再给大家再讲一波好用的算法技巧，不信，你继续往下看
1. 巧用数组下标

数组的下标是一个隐含的很有用的数组，特别是在统计一些数字，或者判断一些整型数是否出现过的时候。例如，给你一串字母，让你判断这些字母出现的次数时，我们就可以把这些字母作为下标，在遍历的时候，如果字母a遍历到，则arr[a]就可以加1了，即  arr[a]++;
通过这种巧用下标的方法，我们不需要逐个字母去判断。
我再举个例子：
问题：给你n个无序的int整型数组arr，并且这些整数的取值范围都在0-20之间，要你在 O(n) 的时间复杂度中把这 n 个数按照从小到大的顺序打印出来。
对于这道题，如果你是先把这 n 个数先排序，再打印，是不可能O(n)的时间打印出来的。但是数值范围在 0-20。我们就可以巧用数组下标了。把对应的数值作为数组下标，如果这个数出现过，则对应的数组加1。代码如下：
public void f(int arr[]) {

   int[] temp = new int[21];
   for (int i = 0; i < arr.length; i++) {
         temp[arr]++;
   }
   //顺序打印
   for (int i = 0; i < 21; i++) {
         for (int j = 0; j < temp; j++) {
            System.out.println(i);
         }
   }
}利用数组下标的应用还有很多，大家以后在遇到某些题的时候可以考虑是否可以巧用数组下标来优化。
2. 巧用取余

有时候我们在遍历数组的时候，会进行越界判断，如果下标差不多要越界了，我们就把它置为0重新遍历。特别是在一些环形的数组中，例如用数组实现的队列。往往会写出这样的代码：
for (int i = 0; i < N; i++) {
   if (pos < N) {
      //没有越界
      // 使用数组arr[pos]
      else {
      pos = 0;//置为0再使用数组
      //使用arr[pos]
      }
      pos++;
}实际上我们可以通过取余的方法来简化代码
for (int i = 0; i < N; i++) {
  //使用数组arr[pos] (我们假设刚开始的时候pos < N)
  pos = (pos + 1) % N;
}3. 巧用双指针

对于双指针，在做关于单链表的题是特别有用，比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题，我们就可以使用双指针了，会方便很多。我顺便说下这三个问题怎么用双指针解决吧。
例如对于第一个问题
我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点，而快指针一次移动两个节点，如果该链表没有环，则快指针会先遍历完这个表，如果有环，则快指针会在第二次遍历时和慢指针相遇。
对于第二个问题
一样是设置一个快指针和慢指针。慢的一次移动一个节点，而快的两个。在遍历链表的时候，当快指针遍历完成时，慢指针刚好达到中点。
对于第三个问题
设置两个指针，其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候，第二个指针正好处于倒数第k个节点。
你看，采用双指针方便多了吧。所以以后在处理与链表相关的一些问题的时候，可以考虑双指针哦。
4. 设置哨兵位

在链表的相关问题中，我们经常会设置一个头指针，而且这个头指针是不存任何有效数据的，只是为了操作方便，这个头指针我们就可以称之为哨兵位了。
例如我们要删除头第一个节点是时候，如果没有设置一个哨兵位，那么在操作上，它会与删除第二个节点的操作有所不同。但是我们设置了哨兵，那么删除第一个节点和删除第二个节点那么在操作上就一样了，不用做额外的判断。当然，插入节点的时候也一样。
有时候我们在操作数组的时候，也是可以设置一个哨兵的，把arr[0]作为哨兵。例如，要判断两个相邻的元素是否相等时，设置了哨兵就不怕越界等问题了，可以直接arr == arr[i-1]?了。不用怕i = 0时出现越界。
当然我这只是举一个例子，具体的应用还有很多，例如插入排序，环形链表等。
5. 与递归有关的一些优化

（1）.对于可以递归的问题考虑状态保存
当我们使用递归来解决一个问题的时候，容易产生重复去算同一个子问题，这个时候我们要考虑状态保存以防止重复计算。例如我随便举一个之前举过的问题
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？
这个问题用递归很好解决。假设 f(n) 表示n级台阶的总跳数法，则有
f(n) = f(n-1) + f(n - 2)。
递归的结束条件是当0 <= n <= 2时, f(n) = n。因此我们可以很容易写出递归的代码
public int f(int n) {
   if (n <= 2) {
         return n;
   } else {
         return f(n - 1) + f(n - 2);
   }
}不过对于可以使用递归解决的问题，我们一定要考虑是否有很多重复计算。显然对于 f(n) = f(n-1) + f(n-2) 的递归，是有很多重复计算的。如

就有很多重复计算了。这个时候我们要考虑状态保存。例如用hashMap来进行保存，当然用一个数组也是可以的，这个时候就像我们上面说的巧用数组下标了。可以当arr[n] = 0时，表示n还没计算过，当arr[n] != 0时，表示f(n)已经计算过，这时就可以把计算过的值直接返回回去了。因此我们考虑用状态保存的做法代码如下：
//数组的大小根据具体情况来，由于int数组元素的的默认值是0
//因此我们不用初始化
int[] arr = new int[1000];
public int f(int n) {
   if (n <= 2) {
         return n;
   } else {
         if (arr[n] != 0) {
            return arr[n];//已经计算过，直接返回
         } else {
            arr[n] = f(n-1) + f(n-2);
            return arr[n];
         }
   }
}这样，可以极大着提高算法的效率。也有人把这种状态保存称之为备忘录法。
(2).考虑自底向上
对于递归的问题，我们一般都是从上往下递归的，直到递归到最底，再一层一层着把值返回。
不过，有时候当n比较大的时候，例如当 n = 10000时，那么必须要往下递归10000层直到 n <=2 才将结果慢慢返回，如果n太大的话，可能栈空间会不够用。
对于这种情况，其实我们是可以考虑自底向上的做法的。例如我知道
f(1) = 1;
f(2) = 2;
那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此，我们可以考虑使用自底向上的方法来做。
代码如下：
public int f(int n) {
   if(n <= 2)
         return n;

   int f1 = 1;
   int f2 = 2;
   int sum = 0;

   for (int i = 3; i <= n; i++) {
         sum = f1 + f2;
         f1 = f2;
         f2 = sum;
   }
   return sum;
}我们也把这种自底向上的做法称之为递推。
总结一下
当你在使用递归解决问题的时候，要考虑以下两个问题
(1). 是否有状态重复计算的，可不可以使用备忘录法来优化。
(2). 是否可以采取递推的方法来自底向上做，减少一味递归的开销。
6、找出不大于N的最大的2的幂指数

传统的做法就是让 1 不断着乘以 2，代码如下：
int findN(int N){
int sum = 1;
while(true){
      if(sum * 2 > N){
         return sum;
      }
      sum = sum * 2;
}
}这样做的话，时间复杂度是 O(logn)，那如果改成位运算，该怎么做呢？如果要弄成位运算的方式，很多时候我们把某个数拆成二进制，然后看看有哪些发现。这里我举个例子吧。
例如 N = 19，那么转换成二进制就是 00010011（这里为了方便，我采用8位的二进制来表示）。那么我们要找的数就是，把二进制中最左边的 1 保留，后面的 1 全部变为 0。即我们的目标数是 00010000。那么如何获得这个数呢？相应解法如下：
1、找到最左边的 1，然后把它右边的所有 0 变成 1

2、把得到的数值加 1，可以得到 00100000即 00011111 + 1 = 00100000。
3、把得到的 00100000 向右移动一位，即可得到 00010000，即 00100000 >> 1 = 00010000。
那么问题来了，第一步中把最左边 1 中后面的 0 转化为 1 该怎么弄呢？我先给出代码再解释吧。下面这段代码就可以把最左边 1 中后面的 0 全部转化为 1，
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;就是通过把 n 右移并且做或运算即可得到。我解释下吧，我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后，那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算，那么得到的结果中第 k 和第 k + 1 位必定是 1;同样的道理，再次把 n 右移两位，那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算，那么就能得到第 k, k+1, k+2, k+3 都是 1，如此往复下去....
最终的代码如下
int findN(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;// 整型一般是 32 位，上面我是假设 8 位。
return (n + 1) >> 1;
}这种做法的时间复杂度近是 O(log(logn))，重点是，高逼格。
推荐一个算法视频吧：
直通BAT算法精讲视频最后，给大家推荐一个编程学习网站：
帅地玩编程

		自动登录	找回密码
密码			立即注册

为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？

本帖子中包含更多资源

本帖子中包含更多资源