LeetCode 算法之分治

Question

分治，字面上的解释是 分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

1. 给表达式加括号

241.给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

思路：

对于每个可能都进行尝试。

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = 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 '+':
                                result.add(l+r);
                                break;
                            case '-':
                                result.add(l-r);
                                break;
                            case '*':
                                result.add(l*r);
                                break;
                        }
                    }
            }
        }
        //没有运算符号时,返回自身数值
        if(result.size() == 0){
            result.add(Integer.valueOf(input));
        }
        return result;
    }
}

2. 不同的二叉搜索树

95.给定一个整数 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

思路：

让每个值都尝试成为根节点。

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n < 1){
            return new LinkedList<TreeNode>();
        }
        return generateSubtrees(1,n);
    }

    private List<TreeNode> generateSubtrees(int l, int r){
        List<TreeNode> result = new LinkedList<>();
        //空子树
        if(l > r){
            result.add(null);
            return result;
        }
        for(int i = l; i <= r; i++){
            List<TreeNode> leftSubtrees = generateSubtrees(l,i-1);
            List<TreeNode> rightSubtrees = generateSubtrees(i+1,r);
            for(TreeNode left : leftSubtrees)
                for(TreeNode right : rightSubtrees){
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
        }
        return result;
    }
}