LeetCode专题 分而治之

这几天我再次调整刷题的策略，目前的策略是重新通读认真学习《算法导论》，我曾经无数次看过算法导论，但是都是通读，而没有进行练习，所以知识根本没有掌握，浮于表面的浮光掠影。算法并不困难，但是需要大量的实操代码才能熟练。这是我以前只看不练的策略最大的问题。

我这次使用的是英文版的《 Introduction to Algorithms 》，Kindle版本，这个版本有点不爽，只能在我的Mac看。但是形式好坏不影响内容的好坏。我还有Robert Sedgewick的《 Algorithms 》也是kindle电子书， 他在coursera上的课 我是上完了的，但是不够认真，未来还会把他的书重读一遍。还有Jeff Erickson的算法《 Algorithms 》，这本书是可以免费下载的，作者自己发布的。

这段时间我的主攻方向是算法导论，每一个章节重新阅读，然后针对性的在LeetCode把相关的题目刷一遍。

什么是分而治之？

简单的说，分而治之，就是当问题太大，我们不知道怎么解决的时候，我们可以把原始问题切割成小问题，直到问题小到我们可以轻松解决为止，然后解决它。然后再把小问题的解合起来，形成大问题的解。英文叫做Divide and Conquer，其实分而治之可以是一种战争思想也可以是日常生活中的一种解决问题之道。在现实生活中，如果可以把问题分解，则可以加入更多的人来一起工作，如果子问题之间没有干涉，那么就可以得到非常好的加速效果。

我最爱举的例子是砌墙，如果要砌一段10米的墙，手里面有5个人，那么把问题分解成，5段2米的墙。假设一个人可以在10个小时内砌完2米，那么这段10米的墙，5个人十个小时就可以砌完。但是如果问题不能分解，只能一个人做的话，那就需要50个小时了。

这其实也叫做分工，《人月神话》其实也在讲这个问题，如果一个工程可以良好的被切分成不相互干涉的子项目就可以大大的提高效率，如果不能，则相互依赖效率低下。

算法上的分而治之，跟刚才讲的解决问题之道基本原理相同，但是仍旧有区别。算法上的分而治之，往往谈的是递归的切分问题。分而治之有点难度的问题在于，递归的代码看上去是平铺直叙的，但是实际上是动态的，执行的次数和顺序，都不是一眼就可以看清楚的，而且往往跟具体的数据组成有关系。分而自治的另外一个问题就是在于该怎么切分问题，只有正确的切分才能把问题变得简单。

我想不到什么快速入门分而治之的方法。甚至你会发现，你可以做一个分而治之的题目，不代表就可以做对另外一个题目。我能想到的唯一办法就是多做类似的题目，第一是要强化递归的思维，第二就是增加熟悉程度，多掌握一些切分方法。

《算法导论》一书在2.3.1章节介绍了Merge Sort（归并排序），在第4章“分而治之”介绍了4.1 the maximum-subarray problem（最大子数组问题），4.2 Strassen’s algorithm for matrix multiplication （Strassen的矩阵乘法算法）。

这个系列按照《算法导论》的结构去刷题的好处在于，我们谈到书里面的例子的细节，就可以不讲解具体的算法细节了（人生无难事，只要肯放弃），算法导论讲的够细了。如果还有问题我们可以再讨论。然后刷题的过程中，我们遇到跟算法导论例子类似的题目就跟着算法导论的思路去解。这样学起来比较快。如果你没有算法导论呢，那么我建议你马上买一本。

我把这三个算法书里面的伪代码都翻译成了Java，放在下面。

Merge-Sort的 Java 版本：

github地址： https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/MergeSort.java

Maximum Subarray（最大子数组问题）的代码：

github地址： https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/MaximumSubarray.java

Strassen的矩阵乘法算法

github地址： https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/SquareMatrixMultiply.java

暴力实现

简单的递归解法

简单递归解法所需要的辅助函数（Strassen的算法也需要）

矩阵分解和组合函数

矩阵加减函数

Strassen的矩阵乘法算法