算法之 分治法 Divide and Conquer
分治法：
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
使用条件
分治法所能解决的问题一般具有以下几个特征：
- 分解：将大问题的分解成小问题，是这个算法的核心。也是使用分治法的效率保证，如果分解不合理。那么反而会弄巧成拙。
- 解决：解决问题，便是分解之后的小问题。他们的解决步骤是相同，至少是相似的。所以，分治法中经常用到递归，就是基于这样的目的。
- 合并：前面那么麻烦的两步，最终的目的仍然是为了解决这个问题。所以需要将分解问题得到的解，合并成最终需要的终极答案，便是这个算法的结束过程。譬如，你使用递归的时候，也需要最后退出的条件。分治法结束条件，就是合并步骤的结束。
所以可以看出分治法与递归联系紧密，时常一起出现，但也有区别，对于分治法，一定要注意会有和这一步，但有时在递归的过程中自动出现和这一步，不用太区分。要理解分治的思想。
主要应用
- 二分搜索：
- 快速排序：
- 分：找到一个基准数；把小于这个数的数都放到左边，把大于这个数的数都放到右边；
- 解：递归快排
- 组合：因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作
- 大整数乘法：
leetcode题目分析：
-
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));
}
}
-
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;
}
}
-
215. Kth Largest Element in an Array:
这道题就只要先快速排序一下就可以找到了
