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; }}