阿里朋友的忠告：大廠里算法很重要，先來了解一下分治算法
一、算法介紹
分治算法是用了分治思想的一種算法，什么是分治？
字面上的解釋是“分而治之”，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。
舉個栗子：
二、基本原理
分治模式中，我們遞歸地求解一個問題，在每層遞歸中應(yīng)用如下三個步驟：
分解（Divide)步驟將問題劃分為一些子問題，子問題的形式與原問題一樣，只是規(guī)模更小。
解決(Conquer)步驟遞歸地求解出子問題。如果子問題規(guī)模足夠小，則停止遞歸，直接求解。
合并（Combine）步驟將子問題的解合并為原問題的解。
三、應(yīng)用場景
運用分治策略解決的問題一般來說具有以下特點：
原問題可以分解為多個子問題
這些子問題與原問題相比，只是問題的規(guī)模有所降低，其結(jié)構(gòu)和求解方法與原問題相同或相似。
原問題在分解過程中，遞歸地求解子問題
由于遞歸都必須有一個終止條件，因此，當(dāng)分解后的子問題規(guī)模足夠小時，應(yīng)能夠直接求解。
在求解并得到各個子問題的解后
應(yīng)能夠采用某種方式、方法合并或構(gòu)造出原問題的解。
不難發(fā)現(xiàn)，在分治策略中，由于子問題與原問題在結(jié)構(gòu)和解法上的相似性，用分治方法解決的問題，大都采用了遞歸的形式。
在各種排序方法中，如歸并排序、堆排序、快速排序等，都存在有分治的思想。
四、時間復(fù)雜度
分治算法的時間復(fù)雜度分析我們可以用遞推公式和遞歸樹。
一個分治法將規(guī)模為n的問題分成k個規(guī)模為n/m的子問題去解。
設(shè)分解閥值n0=1，且ADHOC§解規(guī)模為1的問題耗費1個單位時間。
再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。
用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：
T（n）= k T(n/m)+f(n)
通過迭代法求得方程的解：
遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng) mi≤n由此可求得起時間復(fù)雜度為 O（nlogn）。
五、經(jīng)典問題
（1）二分搜索（查找）
（2）大整數(shù)乘法
（3）Strassen矩陣乘法
（4）棋盤覆蓋
（5）歸并排序
（6）快速排序
（7）線性時間選擇
（8）最接近點對問題
（9）循環(huán)賽日程表
（10）漢諾塔
六、算法實戰(zhàn)
二分查詢
二分查找是一種在每次比較之后將查找空間一分為二的算法，通過有序的區(qū)間可以直接確定結(jié)果在哪個區(qū)間，所以分的兩個區(qū)間只需要計算其中一個區(qū)間，然后繼續(xù)進(jìn)行一直到結(jié)束。
public int searchInsert(int[] nums, int target) { if(nums[0]>=target)return 0;//剪枝
if(nums[nums.length-1]==target)return nums.length-1;//剪枝
if(nums[nums.length-1]<target)return nums.length;
int left=0,right=nums.length-1; while (left<right) {
int mid=(left+right)/2; if(nums[mid]==target) return mid; else if (nums[mid]>target) { right=mid;
} else { left=mid+1;
}
} return left;
}快速排序
快排每一趟會選定一個數(shù)，將比這個數(shù)小的放左面，比這個數(shù)大的放右面，然后遞歸分治求解兩個子區(qū)間，當(dāng)然快排因為在分的時候就做了很多工作，當(dāng)全部分到最底層的時候這個序列的值就是排序完的值，這是一種分而治之的體現(xiàn)。
public void quicksort(int [] a,int left,int right){ int low=left; int high=right; //下面兩句的順序一定不能混，否則會產(chǎn)生數(shù)組越界?。?！very important?。?！
if(low>high)//作為判斷是否截止條件
return; int k=a[low];//額外空間k，取最左側(cè)的一個作為衡量，最后要求左側(cè)都比它小，右側(cè)都比它大。
while(low<high)//這一輪要求把左側(cè)小于a[low],右側(cè)大于a[low]。
{ while(low<high&&a[high]>=k)//右側(cè)找到第一個小于k的停止
{
high--;
} //這樣就找到第一個比它小的了
a[low]=a[high];//放到low位置
while(low<high&&a[low]<=k)//在low往右找到第一個大于k的，放到右側(cè)a[high]位置
{
low++;
}
a[high]=a[low];
}
a[low]=k;//賦值然后左右遞歸分治求之
quicksort(a, left, low-1);
quicksort(a, low+1, right);
}歸并排序(逆序數(shù))
快排在分的時候做了很多工作，而歸并就是相反，歸并在分的時候按照數(shù)量均勻分，而合并時候已經(jīng)是兩兩有序的進(jìn)行合并的，因為兩個有序序列O(n)級別的復(fù)雜度即可得到需要的結(jié)果。而逆序數(shù)在歸并排序基礎(chǔ)上變形同樣也是分治思想求解。
private static void mergesort(int[] array, int left, int right) { int mid=(left+right)/2; if(left<right)
{
mergesort(array, left, mid);
mergesort(array, mid+1, right);
merge(array, left,mid, right);
}
}private static void merge(int[] array, int l, int mid, int r) { int lindex=l;int rindex=mid+1; int team[]=new int[r-l+1]; int teamindex=0; while (lindex<=mid&&rindex<=r) {//先左右比較合并
if(array[lindex]<=array[rindex])
{
team[teamindex++]=array[lindex++];
} else {
team[teamindex++]=array[rindex++];
}
} while(lindex<=mid)//當(dāng)一個越界后剩余按序列添加即可
{
team[teamindex++]=array[lindex++];
} while(rindex<=r)
{
team[teamindex++]=array[rindex++];
}
for(int i=0;i<teamindex;i++)
{ array[l+i]=team[i];
}
}漢諾塔
漢諾塔的傳說
漢諾塔（又稱河內(nèi)塔）問題是源于印度一個古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
漢諾塔游戲的演示和思路分析:
考慮最簡單情況n=2，三根柱子分別為A、B、C，此時，在A上有2片金片(假設(shè)從小到大依次為1,2)。
那么我們的解決步驟可以歸結(jié)為如下：
先把A上1號金片移至B。
再把A上2號金片移至C。
再把B上1號金片移至C。
考慮n增大的情況：
先把A上從1到n-1號金片移至B。
再把A上N號金片移至C。
再把B上從1到n-1號金片移至C。
可以看到遞歸的影子，要解決n個，先解決n-1個，可以分治為n=2的最簡單情況并加以解決。
package com.qf.math;public class Hanoitower { public static void main(String[] args) {
hanoitower(4,'A','B','C');
} public static void hanoitower(int num,char a,char b,char c){ if (num==1){ //盤數(shù)為1，做一次搬遷，從A移動到C柱
System.out.println("第1個盤從"+a+"移動到"+c+"盤");
}else{ //盤數(shù)大于1
//先從a盤最上面的盤值最下面的盤之間的所有盤，移動到b盤，C盤作為中間盤
hanoitower(num-1,a,c,b); //把最底下的那個盤，從a盤移動到c盤
System.out.println("第"+num+"個盤從"+a+"移動到"+c+"盤"); //把b盤的所有盤，移動到c盤上
hanoitower(num-1,b,a,c);
}
}
}
最大子序列和
最大子序列和的問題我們可以使用動態(tài)規(guī)劃的解法，但是也可以使用分治算法來解決問題，但是最大子序列和在合并的時候并不是簡單的合并，因為子序列和涉及到一個長度的問題，所以正確結(jié)果不一定全在最左側(cè)或者最右側(cè)，而可能出現(xiàn)結(jié)果的區(qū)域為：
完全在中間的左側(cè)
完全在中間的右側(cè)
包含中間左右兩個節(jié)點的一個序列
給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。
public int maxSubArray(int[] nums) {
int max=maxsub(nums,0,nums.length-1); return max;
}
int maxsub(int nums[],int left,int right)
{ if(left==right) return nums[left];
int mid=(left+right)/2;
int leftmax=maxsub(nums,left,mid);//左側(cè)最大
int rightmax=maxsub(nums,mid+1,right);//右側(cè)最大
int midleft=nums[mid];//中間往左
int midright=nums[mid+1];//中間往右
int team=0; for(int i=mid;i>=left;i--)
{
team+=nums[i]; if(team>midleft)
midleft=team;
}
team=0; for(int i=mid+1;i<=right;i++)
{
team+=nums[i]; if(team>midright)
midright=team;
}
int max=midleft+midright;//中間的最大值
if(max<leftmax) max=leftmax; if(max<rightmax) max=rightmax; return max;
}總結(jié)
分治法實際上就是類似于數(shù)學(xué)歸納法，找到解決本問題的求解方程公式，然后根據(jù)方程公式設(shè)計遞歸程序。一定是先找到最小問題規(guī)模時的求解方法，然后考慮隨著問題規(guī)模增大時的求解方法找到求解的遞歸函數(shù)式后（各種規(guī)?；蛞蜃樱O(shè)計遞歸程序即可。