2_分治思想.md

分治思想

1、为运算表达式设计优先级（241）

241. 为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
(2*((3-4)*5)) = -10 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(((2*3)-4)*5) = 10

public List<Integer> diffWaysToCompute(String input) {
	List<Integer> res = new ArrayList<>();

	for(int i=0;i<input.length();i++){
		char c = input.charAt(i);
		if( c =='+' || c=='-' || c=='*'){ //根据运算符进行分治
			List<Integer> left = diffWaysToCompute(input.substring(0,i));
			List<Integer> right = diffWaysToCompute(input.substring(i+1));
			System.out.println(input);
			System.out.println("left:"+left+"，right:"+right);
			System.out.println("==================");
			for(int l : left){
				for(int r : right){
					switch (c){
						case '+' :
							res.add(l+r);
							break;
						case '-' :
							res.add(l-r);
							break;
						case '*' :
							res.add(l*r);
							break;
					}
				}
			}
		}
	}

	if(res.size() ==0){ //说明input 是一个数字
		res.add(Integer.valueOf(input));
	}
	return res;
}

2、最大子序和（53）

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

//思路：分治法
//如果把数组分成左右两段，那么加和最大的连续子序列，
//要么出现在数组的左半部分，
//要么出现在数组的右半部分，
//要么出现在中间，即从左半部分和右半部分相邻的地方各取一段。
public int maxSubArray(int[] nums) {
	return maxSubArray(nums,0,nums.length-1);
}

private int maxSubArray(int[] nums,int l,int r){
	if(l==r){
		return nums[l];
	}
	int mid = l + (r-l)/2;
	int leftSubMax = maxSubArray(nums,l,mid);
	int rightSubMax = maxSubArray(nums,mid+1,r);

	int subMax = nums[mid];
	int sum = subMax; //中间元素必然在该最大连续子序列中

	//从中间向左半数组遍历
	for(int i=mid-1;i>=l;i--){
		sum += nums[i];
		subMax = Math.max(subMax,sum);
	}
	sum = subMax;
	//从中间向右半数组遍历
	for(int i=mid+1;i<=r;i++){
		sum += nums[i];
		subMax = Math.max(subMax,sum);
	}
	return max3(leftSubMax,subMax,rightSubMax);
}

private int max3(int a,int b,int c){
	int tmp = (a>b) ? a:b;
	return (tmp>c? tmp : c);
}

3、不同的二叉搜索树 II（95）

95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

public List<TreeNode> generateTrees(int n) {
	if(n==0){
		return new LinkedList<>();
	}
	return generateSubTrees(1,n);
}

public List<TreeNode> generateSubTrees(int s,int e){
	List<TreeNode> res = new LinkedList<>();
	if(s>e){
		res.add(null);
		return res;
	}
	for(int i=s;i<=e;i++){
		List<TreeNode> left = generateSubTrees(s,i-1);
		List<TreeNode> right = generateSubTrees(i+1,e);
		for(TreeNode l : left){
			for(TreeNode r : right){
				TreeNode root = new TreeNode(i);
				root.left = l;
				root.right = r;
				res.add(root);
			}
		}
	}
	return res;
}