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)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10题解：分治
class Solution {public List<Integer> diffWaysToCompute(String input) {List<Integer> res = new ArrayList<>();
if (input == null || input.length() == 0){return res;}
// 字符串全为数字时转化为数字并返回
int num = 0;
// 思考是全数字的状况
int index = 0;
while (index < input.length() && !isOperation(input.charAt(index))) {num = num * 10 + input.charAt(index) - '0';
index ++;
}
// 将全数字的状况间接返回
if (index == input.length()) {res.add(num);
return res;
}
for(int i=0; i<input.length(); i++){if (isOperation(input.charAt(i))){List<Integer> res1 = diffWaysToCompute(input.substring(0,i));
List<Integer> res2 = diffWaysToCompute(input.substring(i+1));
for (int j = 0; j < res1.size(); j++){for (int k = 0; k < res2.size(); k++){num = calculate(res1.get(j), input.charAt(i), res2.get(k));
res.add(num);
}
}
}
}
return res;
}
// 计算两个数的运算值
public int calculate(int num1, char op, int num2){switch(op){
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
}
return -1;
}
public boolean isOperation(char ch){return ch == '+' || ch == '-' || ch == '*';}
}递归分治优化：Map 保留计算过的后果
Solution {public List<Integer> diffWaysToCompute(String input) {List<Integer> res = new ArrayList<>();
Map<String, Integer> map = new HashMap<String, Integer>();
// 如果 map 曾经寄存 input 对应的后果，间接将值增加到 res，并返回。if (map.containsKey(input)){res.add(map.get(input));
return res;
}
if (input == null || input.length() == 0){return res;}
// 字符串全为数字时转化为数字并返回
int num = 0;
// 思考是全数字的状况
int index = 0;
while (index < input.length() && !isOperation(input.charAt(index))) {num = num * 10 + input.charAt(index) - '0';
index ++;
}
// 将全数字的状况间接返回
if (index == input.length()) {res.add(num);
return res;
}
for(int i=0; i<input.length(); i++){if (isOperation(input.charAt(i))){List<Integer> res1 = diffWaysToCompute(input.substring(0,i));
List<Integer> res2 = diffWaysToCompute(input.substring(i+1));
for (int j = 0; j < res1.size(); j++){for (int k = 0; k < res2.size(); k++){num = calculate(res1.get(j), input.charAt(i), res2.get(k));
res.add(num);
map.put(input, num);
}
}
}
}
return res;
}
// 计算两个数的运算值
public int calculate(int num1, char op, int num2){switch(op){
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
}
return -1;
}
public boolean isOperation(char ch){return ch == '+' || ch == '-' || ch == '*';}
}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
提醒：
0 <= n <= 8
题解：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) {this.val = val;}
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {public List<TreeNode> generateTrees(int n) {List<TreeNode> res = new ArrayList<>();
if (n<=0){return res;}
return help(1, n);
}
public List<TreeNode> help(int start, int end){List<TreeNode> list = new ArrayList<>();
if (start > end){list.add(null);
return list;
}
if (start == end){list.add(new TreeNode(start));
}
else if (start < end){for (int i = start; i<=end; i++){List<TreeNode> leftTrees = help(start, i-1);
List<TreeNode> rightTrees = help(i+1, end);
for (TreeNode left: leftTrees){for (TreeNode right: rightTrees){TreeNode root = new TreeNode(i, left, right);
list.add(root);
}
}
}
}
return list;
}
}