算法思想 - 分治算法
分治算法的基本思想是将一个规模为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] @pdai: 代码已经复制到剪贴板
1
2
3
4
5
6
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; }
