Leetcode 题解 - 分治
优质
小牛编辑
166浏览
2023-12-01
1. 给表达式加括号
241. Different Ways to Add Parentheses (Medium)
// html Input: "2-1-1". ((2-1)-1) = 0 (2-(1-1)) = 2 Output : [0, 2]
// java public List diffWaysToCompute(String input) { List ways = new ArrayList<>(); for (int i = 0; i < input.length(); i++) { char c = input.charAt(i); if (c == '+' || c == '-' || c == '*') { List left = diffWaysToCompute(input.substring(0, i)); List right = diffWaysToCompute(input.substring(i + 1)); for (int l : left) { for (int 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. 不同的二叉搜索树
95. Unique Binary Search Trees II (Medium)
给定一个数字 n,要求生成所有值为 1...n 的二叉搜索树。
// html Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
// java public List generateTrees(int n) { if (n < 1) { return new LinkedList(); } return generateSubtrees(1, n); } private List generateSubtrees(int s, int e) { List res = new LinkedList(); if (s > e) { res.add(null); return res; } for (int i = s; i <= e;="" ++i)="" {="" list leftSubtrees = generateSubtrees(s, i - 1); List rightSubtrees = generateSubtrees(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; }