分治算法

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

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;        }        //分：左子樹與右子樹        ArrayList<Integer> left = preodertraversal(root.left);        ArrayList<Integer> right = preodertraversal(root.right);       //治：把得到的結(jié)果合并起來        result.add(root.val);        result.addAll(left);        result.addAll(right);        return result;    }}上面的過程可以通過一個(gè)遞推公式來表示T(n) = 2T(2/n)+O(1)2T(2/n) 表示 原來的大問題變成兩個(gè)原來一半的問題O(1)表示 對(duì)二叉樹的每個(gè)節(jié)點(diǎn)只操作一次。上面的公式可以推出 上面前序遍歷的時(shí)間復(fù)雜度是 O(n)

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

兩道題

對(duì)于分治的題目很多，為什么選擇下面這兩道題目呢？因?yàn)樽銐虻湫停瑢W(xué)會(huì)了這兩道題，我們保證，您在與同事、面試官聊起分治算法的時(shí)候，他們會(huì)認(rèn)為您是懂分治算法。
* 接下來祭出第一道題目

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

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

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

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

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

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

代碼實(shí)現(xiàn)

 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);        //結(jié)合上面的圖就是求A+B大還是A+C大呢，       和0做比較就是因?yàn)橛胸?fù)數(shù)的存在        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í)在最初的快排和歸并排序都接觸過了，如果你上面兩道題目都理解，下面給出歸并排序和快排的代碼在重溫一下，看下感覺是不是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è)是歸并的具體具體過程，我們這篇介紹分治的重點(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í)現(xiàn)，有興趣看相關(guān)資料        //分        sort(list,lo,j-1);        sort(list,j+1,hi);    }

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

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

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