给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 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
按运算符分成左右两部分，分别计算后，利用分隔符，合并。 举个例子：2 * 3-4 * 5 第一次按分割，左边2，右边3-4 * 5 左边没有运算符，则直接等于2;右边继续分割，左边3，右边4 * 5，再继续分割右边，运算4 * 5 =20,将3-20=-17返回，再计算2(-17)=34压入vector; 接下来从-号开始分割，依次下去，就求出所有可能。
class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> list = partition(input);
Collections.sort(list);
return list;
}
private List<Integer> partition(String input) {
List<Integer> res = new ArrayList<>();
if (!input.contains("+") && !input.contains("-") && !input.contains("*")) {
res.add(Integer.valueOf(input));
return res;
}
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*') {
for (Integer left : partition(input.substring(0, i))) {
for (Integer right : partition(input.substring(i + 1))) {
char c = input.charAt(i);
if (c == '+') {
res.add(left + right);
} else if (c == '-') {
res.add(left - right);
} else {
res.add(left * right);
}
}
}
}
}
return res;
}
}给定一个整数 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
首先来计数需要构建的二叉树数量。可能的二叉搜素数数量是一个 卡特兰数。
n个节点可以组成f(n)个二叉搜索树
我们从序列 1 ..n 中取出数字 i，作为当前树的树根。于是，剩余 i - 1 个元素可用于左子树，n - i 个元素用于右子树。
如 前文所述，这样会产生 G(i - 1) 种左子树 和 G(n - i) 种右子树，其中 G 是卡特兰数。
现在，我们对序列 1 ... i - 1 重复上述过程，以构建所有的左子树；然后对 i + 1 ... n 重复，以构建所有的右子树。
这样，我们就有了树根 i 和可能的左子树、右子树的列表。
最后一步，对两个列表循环，将左子树和右子树连接在根上。
/**
* 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) {
if (n == 0) {
return new LinkedList<TreeNode>();
} else {
return allTree(1, n);
}
}
private List<TreeNode> allTree(int start, int end) {
List<TreeNode> res = new LinkedList<>();
if (start > end) {
res.add(null);
return res;
}
for (int i = start; i <= end; i++) {
List<TreeNode> left = allTree(start, i - 1);
List<TreeNode> right = allTree(i + 1, end);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
res.add(root);
}
}
}
return res;
}
}输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
dfs(root);
pre.right = head;
head.left = pre;
return head;
}
private void dfs(Node cur) {
if (cur == null) {
return;
}
dfs(cur.left);
if (pre == null) {
head = cur;
} else {
pre.right = cur;
}
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
大顶堆
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
if (k == 0) {
return new int[0];
}
Queue<Integer> maxHeap = new PriorityQueue<Integer>((x, y) -> y - x);
for (int i = 0; i < k; i++) {
maxHeap.offer(arr[i]);
}
for (int i = k; i < arr.length; i++) {
if (maxHeap.peek() > arr[i]) {
maxHeap.poll();
maxHeap.offer(arr[i]);
}
}
for (int i = k - 1; i >= 0; i--) {
res[i] = maxHeap.poll();
}
return res;
}
}