Leetcode题解——算法思想之分治
2020-12-13 01:45
标签：算法 string break 思想 null div highlight eof parent 241. Different Ways to Add Parentheses (Medium) 95. Unique Binary Search Trees II (Medium) 给定一个数字 n，要求生成所有值为 1...n 的二叉搜索树。 Leetcode题解——算法思想之分治 标签：算法 string break 思想 null div highlight eof parent 原文地址：https://www.cnblogs.com/daimasanjiaomao/p/11009084.html
1. 给表达式加括号
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output : [0, 2]
public ListInteger> diffWaysToCompute(String input) {
ListInteger> ways = new ArrayList();
for (int i = 0; i .length(); i++) {
char c = input.charAt(i);
if (c == ‘+‘ || c == ‘-‘ || c == ‘*‘) {
ListInteger> left = diffWaysToCompute(input.substring(0, i));
ListInteger> right = diffWaysToCompute(input.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch (c) {
case ‘+‘:
ways.add(l + r);
break;
case ‘-‘:
ways.add(l - r);
break;
case ‘*‘:
ways.add(l * r);
break;
}
}
}
}
}
if (ways.size() == 0) {
ways.add(Integer.valueOf(input));
}
return ways;
}
2. 不同的二叉搜索树
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST‘s shown below:
1 3 3 2 1
\ / / / \ 3 2 1 1 3 2
/ / \ 2 1 2 3
public ListTreeNode> generateTrees(int n) {
if (n 1) {
return new LinkedListTreeNode>();
}
return generateSubtrees(1, n);
}
private ListTreeNode> generateSubtrees(int s, int e) {
ListTreeNode> res = new LinkedListTreeNode>();
if (s > e) {
res.add(null);
return res;
}
for (int i = s; i ++i) {
ListTreeNode> leftSubtrees = generateSubtrees(s, i - 1);
ListTreeNode> rightSubtrees = generateSubtrees(i + 1, e);
for (TreeNode left : leftSubtrees) {
for (TreeNode right : rightSubtrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}
上一篇：php 字符串函数详解