算法之 分治法 Divide and Conquer

---

分治法：

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

使用条件
分治法所能解决的问题一般具有以下几个特征：

• 1. 分解：将大问题的分解成小问题，是这个算法的核心。也是使用分治法的效率保证，如果分解不合理。那么反而会弄巧成拙。
• 2. 解决：解决问题，便是分解之后的小问题。他们的解决步骤是相同，至少是相似的。所以，分治法中经常用到递归，就是基于这样的目的。
• 3. 合并：前面那么麻烦的两步，最终的目的仍然是为了解决这个问题。所以需要将分解问题得到的解，合并成最终需要的终极答案，便是这个算法的结束过程。譬如，你使用递归的时候，也需要最后退出的条件。分治法结束条件，就是合并步骤的结束。

所以可以看出分治法与递归联系紧密，时常一起出现，但也有区别，对于分治法，一定要注意会有和这一步，但有时在递归的过程中自动出现和这一步，不用太区分。要理解分治的思想。

主要应用

• 二分搜索：
• 快速排序：

1. 分：找到一个基准数；把小于这个数的数都放到左边，把大于这个数的数都放到右边；
2. 解：递归快排
3. 组合：因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作

• 大整数乘法：

leetcode题目分析：

1. 53maximum-subarray:
   1.1 分解：这个数组只能出现在三个位置：从中间分，要么完全在左边，要么完全在右边，要么穿过中间，所以分三部分求最大
   1.2 求解：如果在左边或右边继续分，最后只剩一个数返回，对于穿过中间的，分成两部分求最大，每次都如此。
   1.3 组合：每次返回左边，右边，中间这三个中最大的

class Solution {
    public int maxSubArray(int[] nums) {
        return findMax(nums,0,nums.length-1);
    }
    public static int findMax(int []num,int left,int right){
        if (left>=right)return num[left];
        int mid=(left+right)/2;
        //寻找左边最大
        int lmax=findMax(num,left,mid-1);
        //寻找右边最大
        int rmax=findMax(num,mid+1,right);
        //寻找中间最大，并分成两部分，找从中间左边连续最大，中间到右边连续最大，最后加起来
        int mmax=num[mid],t=mmax;
        for (int i=mid-1;i>=left;i--){
            t+=num[i];
            mmax=Math.max(mmax,t);
        }
        t=mmax;
        for (int i=mid+1; i<=right; i++){
            t+=num[i];
            mmax=Math.max(mmax,t);
        }
        //合并
        return Math.max(mmax,Math.max(lmax,rmax));
    }
}

2. 241. Different Ways to Add Parentheses:
   2.1 分：每次遇到符号，分成前后两部分，并记录该符号
   2.2 解：让左边的运算的所有结果去分别加后边运算的所有结果，分解直到只有两个数子，让他们运算，
   2.3 组合：每次的结果都计入数组返回。

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<Integer>();  
        for (int i=0; i<input.length(); i++) {  
            char ch = input.charAt(i);  
            if (ch == '+' || ch == '-' || ch == '*') {  
                List<Integer> left = diffWaysToCompute(input.substring(0,i));  
                List<Integer> right = diffWaysToCompute(input.substring(i+1,input.length()));  
                for (int l : left) {  
                    for (int r : right) {  
                        switch(ch) {  
                        case '+' :  
                            res.add(l+r);  
                            break;  
                        case '-' :  
                            res.add(l-r);  
                            break;  
                        case '*' :  
                            res.add(l*r);  
                            break;  
                        }  
                    }  
                }  
            }  
        }  
        if (res.size() == 0) res.add(Integer.valueOf(input));  
        return res;  
    
    }
}

3. 215. Kth Largest Element in an Array:
   这道题就只要先快速排序一下就可以找到了