021

指导学习（一）

date: 2020-07-01

我自己有个很喜欢的话，叫做 “练习 - 坚持 - 总结 - 提高”，我们已经练习了 70 天，如果不进行一些问题的总结，永远只低头看路，恐怕就会迷路。所以今儿咱们不讲算法题，而是讲一讲到底如何“解决问题”，本文非常非常非常重要，是我很长一段时间的心血与积累，大家一定要耐心看完，共包含3节：

• 算法对个人的意义
• 解决问题的策略
• 算法问题汇总

01、算法对个人的意义

在实际项目中，算法的使用场景有很多，如“Java8中Hashmap使用红黑树来实现”、“Redis底层使用LRU来进做淘汰策略”、“大数据领域很多问题都基于TopK”、“JS原型链里使了类似链表的成环检测”、“特别复杂的业务逻辑经常涉及到DAG”、“MySql为什么索引要用B+树”、“Oracle里的开窗函数如何实现” 等等等等，这些今天我们统统不谈。而我，更多的是想和大家聊一聊，算法对个人有什么意义？

市面上大部分的算法书籍，第一章介绍算法，都会给大家列一列类似上面的那些话，或者就是使用栈或队列来做一个引子，告诉大家算法很重要，你得需要去学，吧啦吧啦....但是不知道大家有没有想过这样一个问题，算法对于个人而言到底有什么意义呢？如果这个问题大家陌生，那你一定会听到有写了几年业务逻辑的老程序员，说过“我这些年从来没有用过算法，除了出去面试的时候”之类的话。其实，我这里真想说一句脏话，这些思想真的是TMD害人不浅啊。甚至我怀疑大多数说这句话本身的人，有两种：一种就是严重缺乏自信心，觉得自己一辈子都没办法学好算法了，所以就这样吧。第二种就是故意误人子弟，驱动来源于自己不会，方式采用侃大山，反正忽悠一个是一个，再来身边也没有其他这方面厉害的朋友，说完之后自己都没意识到哪里有问题，却对别人带去很不好的影响。所以如果你今天看到我的这篇文章，我希望你能记住一世，这辈子都不要说出这种类似的话来，保持对这个学科基本的尊重，哪怕多一点点匠心精神。算法对个人的意义如下：

• 算法题目的程序规模大多都是比较小的，也就意味着切入点很小。使得每一个做题人，可以最大化的投入时间研究问题的本身。而在工作中，稍大一点的项目，基本上是没办法随意改变代码结构的，甚至还会为了整体性能牺牲程序的简洁与优雅。所以算法题是可以让你通过练习编写出好代码的最好的方式，没有之一。
• 算法题目中基本不会有图形化界面，只利用文本进行输入和输出。你可以相当专注的去解决问题。而在工作中，你能获得专注去研究一个问题的机会，几乎很难。想一想，假如你用JAVA写一个后台功能，其核心代码不到10行逻辑，但是MVC得占据你三分之一工作量，定义接口占据你三分之一工作量，公司假如没前端，再占据你三分之一工作量。整个这个过程，我有一个Amazon的朋友形容的很贴切，“掏粪”。
• 预测能力的构建，在大多数算法练习平台中，因为会将运算时间和内存使用状况等信息实时提供给做题人，所以做题人甚至可以一边修改代码，一边观察修改对程序产生的影响。这个是不得了的，在工作中，绝对不可能有这样的机会。而在这个过程中，做题人可以提高对逻辑结构复杂程序进行性能预测的能力，该能力将伴随其一身。
• 提升coding能力的最好方式。假如我们打王者荣耀，你要上王者，不开排位，一直打电脑，能上的去吗？在工作中，你来回接触的就那么几个人，有几个能写出特别优秀的代码，见到了，那说明老天眷顾你，大部分人都见不到。但是在算法平台的练习中，基本上我们每一个问题，我们都能看到全世界最优秀的人提交的代码。没有对比，虽然不成伤害，却更难成为进步！只有我们去阅读别人优秀的逻辑，读懂别人思考的过程，与全世界顶尖的程序员编写代码的能力进行比较，才可以成为真正的大牛。
• 算法题让你难受。用脚指头想一个问题，在各行各业中，想成为其行业的佼佼者，是不是一定有一个难受的过程。假如天天写CRUD，并且还得意洋洋，我用一套Generator生成只需要5分钟，其他时间就可以打打炉石，勾搭勾搭妹子。不经历一个难受的过程，如何可以进步？就连郭德纲出名之前，也在玻璃窗里被关过两天两夜。罗马不是一天建成的，但是如果不修，那就永远建不成。难受就是真理，说明你正在进步。
• 单测都是“骗人的”。请大家不要高估工作中QA的能力（当然，也有牛逼的QA，我见过...），大部分的公司里，QA来做单测时，基本上是重新走了一遍开发者的逻辑。更有甚者，开发直接说出“我写完都已经测完了，要QA有什么用处”，其实这并不是一个段子，因为大部分QA是做不到完美的cover业务逻辑的，换句话说，也就不可能构建出完美的测试用例测出你代码的问题。但是算法不是，大部分的算法平台，都提供了实时反馈的机制，如果自己编写的代码可以得到快速，客观的意见反馈，这绝对是有如神助。就好像是你打王者，旁边有个小精灵，总是会在合适的时机告诉你，“去下路，中路没人”，“小心草丛”。那如果不被带飞，你信吗？

总之，正是因为算法题目中只保留了必备的要素，舍弃了其他无关紧要的部分，所以可以对每一位做题人都构建一个学习解决问题的最佳环境，而在这个环境中的成长与提高，将对一个软件工程师的生涯产生深远影响，乃至一世。所以，请大家能有一颗匠心，你可以选择不去了解学习掌握算法，但是请不要耽误他人进步。山高水长，江湖路远，珍重万千，有缘再见！

02、解决问题的策略

解决简单的问题时，直接利用已知的技术便可轻松解决问题。但是如果遇到难题，恐怕就需要用各种手段。管他是花猫野猫，抓住耗子都是好猫。在解决问题的策略构建中，我们首先要对问题和答案结构有一个直观的感受，或者说猜测。如果可以把控住当前算法的问题，具备一个什么样的形态，然后就可以把毫无头绪的事情，变得有迹可循。在这样一个过程中，一点点的积累经验，最终就可以提升自己。

上面说的内容，玄而又玄，那到底如何来构建策略。假如我们遇到一个问题，让我们找一个国家铁路网中，两个城市的最短路径。这种问题，大家肯定首先想到的就是使用迪杰斯特拉算法。但是如果问题变成“换乘火车次数少于N次，寻找最短路径”，这种问题将不能直接套用最短路径的算法。有时候只是改变题中条件，就可以让整个题目完全走向另一个逻辑，这就需要大家对原算法的原理和执行过程特别了解，并且熟读题意。所以这里我们抽象出两个步骤：

• 读题
• 重构

读题的目的，就是阅读并理解问题。不管是是不是算法老手，在这上面栽跟头的绝对不是一个两个，审题不清是所有人的共性（绝不是你的个人问题），人的天性就期望可以快速得到反馈，这是身体欲望导致的，和你看到漂亮的妹子下半身竖立本质没有什么区别。所以这就引出我们的解决方法 - 重构。

什么是重构，重构其实就是一个抽象化的过程。借用我们已经掌握的数学/计算机知识，将其表达成现实世界概念。大部分的现实世界概念都是比较复杂的，我们对其抽茧剥丝，保留本质，表述成易于理解的形式。而对其重构的过程，就可以决定其程序设计的方向。举一个最简单的例子，比如我们要用代码实现一个整数平方根的开方，可以选用牛顿法或者二分法，那这两种方法是如何被想到的。假如我们把问题重构成图形的表达方式，就比较容易会推出牛顿法。假如我们把问题重构成已有的知识概念，自然就可以想到二分法。而如果我们把问题抽象成公式，甚至可以通过数学法来进行解题。划重点，不同的重构方式，决定最终程序的走向。

在重构的基础上，其实我们就可以来进行解题了。但是这里我还要对其加一个步骤，化简。什么又是化简，如何化简？假如我们有一个题，我们有一个二维网格，里边有N个点，两点的距离是X坐标和Y坐标的的和。比如坐标(5,1)和(4,7)的点间距就是1+6=7。我们要找到给出的N个点距离之和最小的新点的坐标。

题目因为本身是二维的，我们写代码其实不是很好写。所以我们可以将其化简为一维。我们把每一个点的左边，通过映射的方式，分别映射到 x轴 和 y轴。然后我们把问题转化成在直线上寻找到给出点的距离之和最小的点。这就是化简。万物之始，大道至简，至拙至美。生活中咱们也说透过现象看本质，放在算法里你就不会了？

读题-重构-化简，下来自然就是解题了。那如何解题？这个范畴虽然很大，但也不是无迹可寻，下面两点：

• 基本数据结构和算法的掌握（略）
• 常见算法问题的汇总

基本数据结构和算法的掌握，这个自不必说，是人都知道，那么常见算法问题的汇总又是什么，我们看下一节。

03、算法问题汇总

写算法最怕什么？当然是出错。与其重复相同的错误，不如从错误中吸取教训。与其从自己的错误中吸取教训，不如从别人的错误中学习经验。总结常见的算法问题，我总不能和你去说我们需要掌握数组、链表、二叉树、Map等这些数据结构。我认为的总结，就是错误的总结。所以为了快速拔高大家的水准，我准备了以下这些错误，请一定耐心看完，反复阅读。

• 递归，防止死循环和内存泄露。由于递归需要堆栈，所以内存消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。内存会存在突然飙升的情况。如果是数据错误导致无限循环，那问题就大了。所以这方面问题在开发的时候需要注意。
• 访问数组越界，绝大多数的数组越界，根本原因在于对定义混淆。比如定义的时候想的是“以0起始”，但是写的时候写成了“以1起始”。究其根本，数组越界的问题，其实是对区间把控的问题。
• 区间表意不明。 大部分的语言中，数组都以0为起始元素，但是人的思维习惯于以1为起始。那为什么数组要以0为起始元素，历史原因有很多，咱不说。对咱们有用的，3个。第一，因为我们选择左闭右开区间，比如 [0,n)，我们可以很容易通过 n-0 得到数组中元素个数。这点大家要形成条件发射，看到数组，明确其个数。第二，闭区间很难去表示一个空数组，不信你试试，非常难受。第三，左闭右开的区间，迭代器只需要最少的操作符。可以让代码写起来非常的舒服，STL的算法和容器中基本都是如此。
• 差一问题（栅栏错误）。 建造一条直栅栏（即不围圈），长30米、每条栅栏柱间相隔3米，需要多少条栅栏柱? 求数组 A[i]到 A[j] 的平均值，A[i] 到 A[j] 的和应该除以多少，是 j-i+1，还是 j-i？二分法中的 while 条件，到底是用 <= 还是 < ？这些都是差一问题，这类问题如何解决。利用最小的的输入值测试代码的执行过程，长期反复，达到条件反射。这个过程一定是在大量的题目练习中掌握的，如果你到目前还在纠结这个问题，请先扣心自问，是否刷过至少200道算法题。如果没有，请不要纠结，干就对了。如果有，来找我。
• 内存溢出问题。分为两种，一种是因为运算超出变量取值范围发生的内存溢出，比如二分法中的mid，就要使用 left+(right-left)>>1。另一种就是因为代码不严谨，比如递归没有退出条件，while死循环，等等导致内存溢出。
• 初学者定义问题。 比如统计26个字母出现的次数，初学者会用hashmap，其实这种已知值范围的，定义成数组就可以了。其他类似数字0-9，每个月的天数，都是一样的
• 写一半忘记题意。 这个根本原因还是因为思维脉络不清晰导致的，有时候初学者还会遇到一个问题。定义一个函数，比如叫做 juge() 返回 bool 值，本来应该是判断某条件成立时返回true，但是用的时候却以为，在条件不成立的时候返回true，最终导致结果错误。
• 变量名错误。 不管是和方法参数中的变量名称冲突，还是因为本身表意不明，最终出现赋值错误，或者编译不通过。
• 运算优先级错误。 比如位运算，各个语言中的优先级定义是略有不同的。有时候需要加括号，有时候不需要加。
• 特殊值的处理。 一些找规律的题目，往往在等于0，等于1的时候，规律和其他的数不同，所以这种题目，需要对这种特殊值进行特殊处理。

以上就是我挑选过的一些具有代表性的错误示例（后续还会补充），同时，算法指导篇我打算出一个系列，包括算法中常用技巧，常见错误，题目常见误导 等等，都是我的珍藏。今天的文章呕心泣血，希望大家可以帮我转发，我想如果你身边有学习计算机的朋友看到，他一定会感谢你。支持我的朋友们，还没有关注的，快点来个关注。最后，山高水长，江湖路远，珍重万千，下期再见！