LeetCode——分治

ゝ一纸荒年。 2023-06-18 08:55 6阅读 0赞

# LeetCode类型题之分治 #

--------------------

## 目录 ##

1.  给表达式加括号
2.  不同的二叉搜索树

--------------------

### 1. 给表达式加括号 ###

![在这里插入图片描述][20191201164025209.png]

public List<Integer> diffWaysToCompute(String input) {
        
            List<Integer> ways = new ArrayList<Integer>();
            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 (Integer l : left) {
        
                        for (Integer 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. 不同的二叉搜索树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20191202151151431.png]

public List<TreeNode> generateTrees(int n) {
        
            if (n < 1) {
        
                return new LinkedList<TreeNode>();
            }
            return generateTrees(1, n);
        }
    
        private List<TreeNode> generateTrees(int s, int e) {
        
            List<TreeNode> res = new LinkedList<TreeNode>();
            if (s > e) {
        
                res.add(null);
                return res;
            }
            for (int i = s; i <= e; i++) {
        
                List<TreeNode> leftSubtrees = generateTrees(s, i - 1);
                List<TreeNode> rightSubtrees = generateTrees(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;
        }

[20191201164025209.png]: https://img-blog.csdnimg.cn/20191201164025209.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191202151126605.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[20191202151151431.png]: https://img-blog.csdnimg.cn/20191202151151431.png