【数据结构与算法】分治思想经典题总结
为运算表达式设计优先级
LeetCode：为运算表达式设计优先级
题目描述：
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例：
输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
思想：
分治思想。当遍历到某一个运算符opt时，opt左边的算式记为leftStr，右边算式记为rightStr。对这两个算式分别进行同样处理（分而治之，递归），可以得到多个结果，即两个整型List，分别记为leftValues和rightValues。套两层for循环对这两个List进行逐个计算，得到以当前opt为操作符时的结果。
代码
class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> res = new ArrayList<>();
for(int i=0;i<input.length();++i){
char opt = input.charAt(i);
if(opt>41&&opt<46){
List<Integer> leftValues = diffWaysToCompute(input.substring(0,i));
List<Integer> rightValues = diffWaysToCompute(input.substring(i+1));
for(int left : leftValues){
for(int right : rightValues){
res.add(compute(left,opt,right));
}
}
}
}
if(res.size()==0) res.add(Integer.valueOf(input));
return res;
}
private int compute(int m,char opt,int n){
int res=0;
switch(opt){
case 42: res=m*n;break;
case 43: res=m+n;break;
case 45: res=m-n;break;
}
return res;
}
}
不同的二叉搜索树2
LeetCode：[不同的二叉搜索树2]https://leetcode-cn.com/problems/unique-binary-search-trees-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
思想：
用分治的思想很容易想。但是感觉重复遍历了很多相同的子树。细想，其实从结果来看，有很多重复，要重复new很多结点也无可厚非。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generate(int start, int end){
List<TreeNode> tree = new LinkedList<>();
if(start>end){
tree.add(null);
return tree;
}
for(int i=start;i<=end;++i){
for(TreeNode left : generate(start,i-1)){
for(TreeNode right : generate(i+1,end)){
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
tree.add(root);
}
}
}
return tree;
}
public List<TreeNode> generateTrees(int n) {
if(n==0) return new LinkedList<>();
return generate(1,n);
}
}