刷题-分治

关于分治的题，就记住吧

1. 力扣241

class Solution {
    //空间换时间，防止重复计算
    private Map<String, List<Integer>> map = new HashMap<>();

    public List<Integer> diffWaysToCompute(String expression) {
        if(map.containsKey(expression)){
            return map.get(expression);
        }
        List<Integer> list = new ArrayList<>();
        int len = expression.length();
        if(len == 0){
            list.add(0);
            return list;
        }
        for(int i=0; i<len; ++i){
            char c = expression.charAt(i);
            if(isOps(c)){
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i+1));
                for(int l : left){
                    for(int r : right){
                        list.add(caculate(c, l, r));
                    }
                }
            }
        }
        if(list.size() == 0){
            list.add(Integer.valueOf(expression));
        }
        map.put(expression, list);
        return list;
    }

    private boolean isOps(char c){
        return c == '+' || c == '-' || c == '*';
    }

    private int caculate(char c, int l, int r){
        if(c == '+'){
            return l + r;
        }else if(c == '-'){
            return l - r;
        }else{
            return l * r;
        }
    }
}

1. 力扣95

class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[][] dp = new ArrayList[n+1][n+1];
        return generate(1, n, dp);
    }

    private List<TreeNode> generate(int start, int end, List<TreeNode>[][] dp){
        List<TreeNode> list = new ArrayList<>();
        //把特殊情况放前面，防止后面数组越界
        if(start > end){
            list.add(null);
            return list;
        }
        if(dp[start][end] != null){
            return dp[start][end];
        }
        for(int i=start; i<=end; ++i){
            List<TreeNode> left = generate(start, i-1, dp);
            List<TreeNode> right = generate(i+1, end, dp);
            for(TreeNode l : left){
                for(TreeNode r : right){
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    list.add(root);
                }
            }
        }
        dp[start][end] = list;
        return list;
    }
}