LeetCode類型題之分治

---

目錄

給表達式加括號

不同的二叉搜索樹

---

1. 給表達式加括號

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. 不同的二叉搜索樹

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

總結(jié)

以上是生活随笔為你收集整理的LeetCode——分治的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。