分治算法

分治,”分而治之”。從字面上理解就是分—治，把大的問(wèn)題分成小問(wèn)題，解決一個(gè)一個(gè)小問(wèn)題，之后把問(wèn)題的答案合并起來(lái)，就得到大問(wèn)題的結果。您肯定會(huì )在想，這思想這么簡(jiǎn)單，你不說(shuō)我也是知道。歷史上，秦國通過(guò)遠交近攻的策略，逐個(gè)擊破，最后統一六國不也是分治思想的體現嗎？
以下用一個(gè)二叉樹(shù)的前序遍歷為例，對分治思想在代碼上的體現進(jìn)行說(shuō)明。

public class PreoderTraversal {    public class TreeNode{        private int val;        public TreeNode left,right;        public TreeNode(int val){            this.val = val;            this.left = this.right = null;        }    }    public ArrayList<Integer> preodertraversal(TreeNode root){        ArrayList<Integer> result = new ArrayList<Integer>();        //退出的條件        if(root == null){            return null;        }        //分：左子樹(shù)與右子樹(shù)        ArrayList<Integer> left = preodertraversal(root.left);        ArrayList<Integer> right = preodertraversal(root.right);       //治：把得到的結果合并起來(lái)        result.add(root.val);        result.addAll(left);        result.addAll(right);        return result;    }}上面的過(guò)程可以通過(guò)一個(gè)遞推公式來(lái)表示T(n) = 2T(2/n)+O(1)2T(2/n) 表示 原來(lái)的大問(wèn)題變成兩個(gè)原來(lái)一半的問(wèn)題O(1)表示 對二叉樹(shù)的每個(gè)節點(diǎn)只操作一次。上面的公式可以推出 上面前序遍歷的時(shí)間復雜度是 O(n)

從以上代碼，可以看出，分治算法在代碼實(shí)現上有以下兩點(diǎn)好處：
1.前序遍歷的結果可用通過(guò)一個(gè)函數內的ArrayList返回不需要創(chuàng )建全局變量，來(lái)存放結果。
2.對于拆分后的問(wèn)題，運算量大，采用多并發(fā)，多核來(lái)處理，也是很容易的。具體結合上面代碼來(lái)說(shuō)，對于left、right結果求解，可以分別啟用一個(gè)線(xiàn)程。

兩道題

對于分治的題目很多，為什么選擇下面這兩道題目呢？因為足夠典型，學(xué)會(huì )了這兩道題，我們保證，您在與同事、面試官聊起分治算法的時(shí)候，他們會(huì )認為您是懂分治算法。
* 接下來(lái)祭出第一道題目

分析：
既然我們使用分治來(lái)解決，那就看看問(wèn)題怎么拆分呢？
這道題目中是求兩個(gè)節點(diǎn)的公共的祖先，很顯然，問(wèn)題的拆分可以依據：兩個(gè)節點(diǎn)在二叉樹(shù)的位置來(lái)拆分問(wèn)題：
都在左子樹(shù)上、都在右子樹(shù)上、一個(gè)邊一個(gè)、有一個(gè)節點(diǎn)就是根節點(diǎn)

一個(gè)大的問(wèn)題拆分四個(gè)問(wèn)題，逐個(gè)解決，求出大問(wèn)題，下面給出 實(shí)現代碼

public TreeNode getAncestor(TreeNode root,TreeNode node1,TreeNode node2){        if (root == null)        {            return null;        }        //如果有一個(gè)節點(diǎn)就是根節點(diǎn)        if(root == node1 || root == node2){            return root;        }        TreeNode left = getAncestor(root.left,node1,node2);        TreeNode right = getAncestor(root.right,node1,node2);        //節點(diǎn)一邊一個(gè)        if(left == null && right == null)        {            return  root;        }       //節點(diǎn)都在左子樹(shù)        if (left != null) {            return left;        }       //節點(diǎn)都在右子樹(shù)        if (right != null) {            return right;        }        return null;    }

如果您還不太明白，沒(méi)關(guān)系，對著(zhù)分析和代碼多看幾次，就會(huì )打通任督二脈的。

• 第二道（這道題，有點(diǎn)小難度）

為什么說(shuō)這道題有點(diǎn)難度呢？原因在于二叉樹(shù)上有負值的存在。而且最關(guān)鍵的是題目只是說(shuō)遍歷二叉樹(shù)，求最大和，并沒(méi)有說(shuō)是從哪里出發(fā)，如果從根出發(fā)就是求：
root—->anyNode 根到任意節點(diǎn)的最大和
明顯這題目的意思是
anyNode—->anyNode 任意節點(diǎn)到任意節點(diǎn)的最大和。
采用分治，怎么拆分呢？
為三種情況：左子樹(shù)、右子樹(shù)、左子樹(shù)–>根–>右子樹(shù)。不明白，沒(méi)關(guān)系，看下圖分析。
分析：

代碼實(shí)現

 public class returnType{        int root2any,any2any;        returnType(int root2any,int any2any){            this.root2any = root2any;  //存放上面分析的root-->anyNode            this.any2any = any2any;  // anyNode-->anyNode        }    } public returnType maxSum(TreeNode root){       //如果二叉樹(shù)不存在，直接設置成最小值        if(root == null){            return new returnType(Integer.MIN_VALUE,Integer.MIN_VALUE);        }        returnType left = maxSum(root.left);        returnType right = maxSum(root.right);        //結合上面的圖就是求A+B大還是A+C大呢，       和0做比較就是因為有負數的存在        int root2any =Math.max(0,Math.max(left.root2any,right.root2any))+root.val;       //R=Math.max（D，E）        int any2any = Math.max(left.any2any,right.any2any);        //Math.max(R,A+B+C)        any2any = Math.max(any2any,Math.max(0,left.root2any)+Math.max(0,right.root2any)+ root.val);        return  new returnType(root2any,any2any);    }

小福利

分治算法其實(shí)在最初的快排和歸并排序都接觸過(guò)了，如果你上面兩道題目都理解，下面給出歸并排序和快排的代碼在重溫一下，看下感覺(jué)是不是so easy??！
歸并排序

  private static Comparable[] aux;   public static void sort(Comparable[] list){        aux = new Comparable[list.length];        sort(list,0,list.length-1);   }    public static void sort(Comparable[] list,int lo,int hi){        if(lo < hi){            return;        }        int mid = lo +(hi-lo)/2;       //分        sort(list,lo,mid);        sort(list,mid+1,hi);        //治        meger(list,lo,mid,hi);    //這個(gè)是歸并的具體具體過(guò)程，我們這篇介紹分治的重點(diǎn)，在此忽略了    }

快速排序

   public static void sort(Comparable[] list){        Collections.shuffle(list);  //消除輸入的影響        sort(list,0,list.length-1);   }    public static void sort(Comparable[] list,int lo,int hi){        if(lo < hi){            return;        }        int j = patition(list,lo,hi);    //快排中重要的切分，典型有三取樣切分。找出大小為中間的點(diǎn)                                                  在此忽略了具體實(shí)現，有興趣看相關(guān)資料        //分        sort(list,lo,j-1);        sort(list,j+1,hi);    }

快排和歸并排序的可以歸納的遞推公式

T(n) = 2T(2/n) +O(n)時(shí)間復雜度是 ）O(NlogN)

由于本人水平有限，有什么問(wèn)題可以評論，喜歡的可以關(guān)注。