算法-分治法
分治法将一个难以直接解决的大问题划分成一些规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。
概述
设计思想
- 大问题划分成一些规模较小的子问题，以便各个击破，分而治之
- 最好使子问题的规模大小相等
- 最好使各子问题之间相互独立。如果子问题不独立，分治法需要重复的求解公共的子问题，此时虽然也可以用分治法，但一般用动态规划法较好
求解过程
- 划分：即分治，划分为小问题
- 求解子问题：一般用递归的方法求解各个子问题，有时递归也可以用循环来实现
- 合并：把各个子问题的解合并起来
递归
分治与递归就像一对孪生兄弟
递归：就是子程序（或函数）直接调用自己或者通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法
递归通常用来解决结构自相似的问题。
递归有两个基本要素：
- 边界条件：确定递归到何时终止，也称为递归出口
- 递归模式：大问题是如何分解为小问题的，也称为递归体
递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
排序问题中的分治法
归并排序
二路归并的分治策略是：
-
划分：将待排序序列r1，r2……rn划分为两个长度相等的子序列r1，……rn/2和rn/2+1，……rn
-
求解子问题：分别对这两个子序列进行归并排序，得到两个有序子序列
-
合并：将这两个有序子序列合并成一个有序序列
快速排序
归并排序是按照记录在序列中的位置对序列进行划分的，而快速排序是按照记录的值对序列进行划分的。
快速排序的分治策略是：
- 划分：选定一个记录作为轴值，以轴值为基准将序列划分为两个子序列r1，……，ri-1和ri+1，……，rn，轴值的位置i在划分的过程中确定，前子序列都小于等于轴值，后子序列都大于等于轴值
- 求解子问题：分别对划分后的每一个子序列递归处理
- 合并：因为子序列的排序是在当前数组中，所以合并不需要执行任何操作
注意，轴值不需要选定，核心在于划分出两个子序列，前子序列都小于等于某个值，后子序列都大于等于某个值
- 面试题 16.16. 部分排序 - 中等 代码 使用快速排序超时，然后使用另一种算法完美解决
组合问题中的分治法
最大子段和问题
给定由n个整数（可能有负数）组成的序列(a1,a2,……,an)，最大子段和问题要求该序列某个区间范围之内和最大，当所有整数均为负整数时，其最大字段和为0。如(-20,11,-4,13,-5,2)，最大子段和为11-4+13=20
用分治策略求解最大子段和：
- 划分：按照平衡子问题原则，将序列(a1,a2,……,an)划分成长度相同的两个子序列(a1,……,a[n/2])和(a[n/2+1],……,an)，会有三种情况
- a1,a2,……,an的最大字段和等于a1,……,a[n/2]的最大子段和
- a1,a2,……,an的最大字段和等于a[n/2+1],……,an的最大子段和
- a1,a2,……,an的最大字段和等于ai+……+aj, 1<=i<=2/n，n/2+1<=j<=n
- 求解子问题：对于划分中情况1和情况2可以递归求解，情况3需要分别计算s1=max(a1+……+a[n/2])，s2=max(a[n/2+1]+……+a[n])，则s1+s2为情况3的最大子段和
- 合并：比较在划分阶段的三种情况下的最大子段和，取三者中较大者为原问题的解
这种类型的题，能考虑使用分治法，感觉已经领悟了分治的核心：划分-求解子问题-合并。蛮力法做差不多是O(n^2)，分治法时间复杂度O(nlog2n)。
另外感觉这种题目，可能使用动态规划效果会更好一些。
棋盘覆盖问题
在一个2k*2k个方格组成的棋盘，恰有一个方格和其他方格不同，称该方格为特殊方格。棋盘覆盖问题要求用图4.11(b)所示的4种不同形状的L型骨牌股改给定棋盘上除特殊方格以外的所有方格，且任何两个L型骨牌不得重复覆盖。
使用分治法求解这个问题的技巧在于如何划分棋盘，使划分后的子棋盘大小相同，并且每个子棋盘都包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。
我当时在思考这个题的时候，已经发现可以用L骨牌覆盖较小棋盘汇合处，但是不知道怎么处理才能是程序更加简单。作者提供的思路：将汇合处设置为特殊方格，不但使递归的操作完全相同，而且很容易标记骨牌形状。
分治法在划分-求解子问题-合并这三个方面还是有很多技巧的。
在乐扣上没有找到这样的题目，可能是因为说明和判断都过于困难，但是我找到了一道相似而且容易一些的题目，就拿这道题练手吧。
- 240. 搜索二维矩阵 II - 中等 代码
循环赛日程安排问题
设有n=2^k个选手进行网球循环赛，要求设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他n-1个选手各赛一次
(2)每个选手一天只能赛一次
可以将比赛日程表设计为一个n行n-1列的二维表，行代表选手，列代表第几天。
这个问题的解法是执行递归分割，最终分割为只有两个人的小方块，安排两个人的日程。我们以上图c为例讲解，最左上角为1号2号选手，其对应的右下角方位为左上角完全拷贝，左下角为3号和4号选手，右上角为完全拷贝。
算法核心是先确定了一个比赛日程规则，前半程比赛完了后，人员参加后半程比赛。
此处有两个点要说明一下
- 第0列没什么意义，主要是为了二维表能够对称
- 该算法的一个前提是有2^k个选手
在乐扣上找了一下对应的算法题，感觉应该是下面这道，但是没有充会员，看不了，如果有哪位同学有这道题内容的话，可以提供一下。
- 输出比赛匹配对 - 中等
几何问题中的分治法
最近对问题
设p1=(x1,y1)，p2=(x2,y2)，……，pn=(xn,yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。严格地讲，最接近点对可能多余一对，简单起见，只找出其中的一对作为问题的解。
先考虑一维情况。此时S中的点退化为x轴上的n个点x1,x2,……,xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同。递归地在S1和S2上求出最接近点对(p1,p2)和(q1,q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min{(p1,p2),(q1,q2)}即为所求，如果集合S中的最接近点对都在子集S1或S2中，则一定是(p3,q3)，其中p3是子集S1的最大值，q3是子集S2的最小值。
m选取一般采用集合S的中值，可以分割的比较平衡一些。
对于二维情况，思路也类似。
递归求出S1和S2的最小距离为d后，则S1和S2之前的最小距离必然位于P1和P2之间。
如果p的位置确定，则S2中与p距离小于d的点位于以p为圆心，以d为半径的圆中。为了便于计算，符合条件的点最多位于d*2d区域范围内。而且因为S1和S2的最小距离为d，所以这个区域内，这种点不会超过6个。如下图所示：
没有找到二维的题目，一维的题目找到一个，使用该题目进行验证
- 1200. 最小绝对差 - 简单 代码
凸包问题
用分治法解决凸包问题的方法和快速排序类似，这个方法称为快包。
设p1=(x1,y1),p2=(x2,y2),……,pn=(xn,yn)是平面上n个点构成的集合S，并且这些点按照x轴坐标升序排列。几何学中有这样一个明显的事实：最左边的点p1和最右边的点pn一定是该集合的凸包顶点。p1pn连成的直线把S分为两个子集S1和S2。
首先找到S1中的顶点pmax，它是距离直线p1pn最远的订单，则三角形pmaxp1p2的面积最大。S1中所有在直线pmaxp1左侧的点构成集合S1-1，S1中所有在直线pmaxpn右侧的点构成了集合S1-2，包含在三角形pmaxp1pn之考虑了。递归处理集合S1-1和S1-2，将求解过程中得到的所有最远距离的点连接起来，就可以得到集合S1的凸包。同理可以求S2的凸包。
如何判断一个点是否在给定直线的左侧还是右侧呢？
|x1 y1 1|
|x2 y2 1| = x1y2+x3y1+x2y3-x3y2-x2y1-x1y3
|x3 y3 1|
当且仅当点p3=(x3,y3)位于直线p1p2左侧时，该式的符号为正。
在乐扣上没有凸包的习题，所以这个就先不做了。
使用二分法求解凸包问题，还是需要我们有一定的几何知识和观察能力的，能够判断出凸包顶点有哪些特征，也需要能够快速判定点位于直线哪一侧，只有这两个问题解决了，该算法才能比较好的实现。
总结
分治法能够极大的提高算法速度，而且分治法和迭代几乎是孪生关系。
使用分治法，需要完全领悟划分-求解子问题-合并的核心。推导出递归时需要设定的边界条件和迭代模式。
这里面比较重要的类型有
排序问题：归并排序、快速排序
组合问题：最大子段和问题、棋盘覆盖问题、循环赛日程安排问题
几何问题：最近对问题、凸包问题
归并排序、快速排序、最大子段和问题、棋盘覆盖问题建议自己尝试一下，因为排序算法是必须要练习的，最大子段和问题涉及到子问题有关联，棋盘覆盖问题涉及到二维数组。
最后
大家如果喜欢我的文章，可以关注我的公众号（程序员麻辣烫）
往期文章回顾：
算法
技术
- 浅谈微服务
- TCP性能优化
- 限流实现1
- Redis实现分布式锁
- Golang源码BUG追查
- 事务原子性、一致性、持久性的实现原理
- CDN请求过程详解
- 记博客服务被压垮的历程
- 常用缓存技巧
- 如何高效对接第三方支付
- Gin框架简洁版
- InnoDB锁与事务简析
读书笔记
思考