241 为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式增加括号，扭转其运算优先级以求出不同的后果。你须要给出所有可能的组合的后果。无效的运算符号蕴含 +, - 以及 *。

示例 1:

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

示例 2:

 输出: "2*3-4*5"
输入: [-34, -14, -10, -10, 10]
解释: (2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

题解：分治

class Solution {public List<Integer> diffWaysToCompute(String input) {List<Integer> res = new ArrayList<>();
        if (input == null || input.length() == 0){return res;}
        // 字符串全为数字时转化为数字并返回
       int num = 0;
        // 思考是全数字的状况
        int index = 0;
        while (index < input.length() && !isOperation(input.charAt(index))) {num = num * 10 + input.charAt(index) - '0';
            index ++;
        }
        // 将全数字的状况间接返回
        if (index == input.length()) {res.add(num);
            return res;
        }

        for(int i=0; i<input.length(); i++){if (isOperation(input.charAt(i))){List<Integer> res1 = diffWaysToCompute(input.substring(0,i));
                List<Integer> res2 = diffWaysToCompute(input.substring(i+1));
                for (int j = 0; j < res1.size(); j++){for (int k = 0; k < res2.size(); k++){num = calculate(res1.get(j), input.charAt(i), res2.get(k));
                        res.add(num);
                    }
                }
            }
        }
        return res;

    }
    // 计算两个数的运算值
    public int calculate(int num1, char op, int num2){switch(op){
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
        }
        return -1;
    }

    public boolean isOperation(char ch){return ch == '+' || ch == '-' || ch == '*';}
}

递归分治优化：Map 保留计算过的后果

Solution {public List<Integer> diffWaysToCompute(String input) {List<Integer> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<String, Integer>();

        // 如果 map 曾经寄存 input 对应的后果，间接将值增加到 res，并返回。if (map.containsKey(input)){res.add(map.get(input));
            return res;
        }
        if (input == null || input.length() == 0){return res;}
        // 字符串全为数字时转化为数字并返回
       int num = 0;
        // 思考是全数字的状况
        int index = 0;
        while (index < input.length() && !isOperation(input.charAt(index))) {num = num * 10 + input.charAt(index) - '0';
            index ++;
        }
        // 将全数字的状况间接返回
        if (index == input.length()) {res.add(num);
            return res;
        }

        for(int i=0; i<input.length(); i++){if (isOperation(input.charAt(i))){List<Integer> res1 = diffWaysToCompute(input.substring(0,i));
                List<Integer> res2 = diffWaysToCompute(input.substring(i+1));
                for (int j = 0; j < res1.size(); j++){for (int k = 0; k < res2.size(); k++){num = calculate(res1.get(j), input.charAt(i), res2.get(k));
                        res.add(num);
                        map.put(input, num);
                    }
                }
            }
        }
        return res;

    }
    // 计算两个数的运算值
    public int calculate(int num1, char op, int num2){switch(op){
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
        }
        return -1;
    }

    public boolean isOperation(char ch){return ch == '+' || ch == '-' || ch == '*';}
}

95. 不同的二叉搜寻树 II

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

提醒：
0 <= n <= 8

题解：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) {this.val = val;}
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {public List<TreeNode> generateTrees(int n) {List<TreeNode> res = new ArrayList<>();
        if (n<=0){return res;}
        return help(1, n);
    }

    public List<TreeNode> help(int start, int end){List<TreeNode> list = new ArrayList<>();
        if (start > end){list.add(null);
            return list;
        }
        if (start == end){list.add(new TreeNode(start));
        }
        else if (start < end){for (int i = start; i<=end; i++){List<TreeNode> leftTrees = help(start, i-1);
                List<TreeNode> rightTrees = help(i+1, end);
                for (TreeNode left: leftTrees){for (TreeNode right: rightTrees){TreeNode root = new TreeNode(i, left, right);
                        list.add(root);
                    }
                }

            }
        }
        return list;
    }
}