分治法

算法之 分治法 Divide and Conquer

---

分治法：

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

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

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

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

主要应用

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

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

• 大整数乘法：

leetcode题目分析：

1. 53maximum-subarray:

2. 1 分解：这个数组只能出现在三个位置：从中间分，要么完全在左边，要么完全在右边，要么穿过中间，所以分三部分求最大

3. 2 求解：如果在左边或右边继续分，最后只剩一个数返回，对于穿过中间的，分成两部分求最大，每次都如此。

4. 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));
       }
   }

5. 241. Different Ways to Add Parentheses:

6. 1 分：每次遇到符号，分成前后两部分，并记录该符号

7. 2 解：让左边的运算的所有结果去分别加后边运算的所有结果，分解直到只有两个数子，让他们运算，

8. 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:
   这道题就只要先快速排序一下就可以找到了