IDEA激活码算法思想 - 分治算法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。@pdai
分治相关题目
给表达式加括号
241. Different Ways to Add Parentheses (Medium) (opens new window)
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output : [0, 2]
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ways = 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));
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;
}
