[TOC]
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
详解见leetcode
利用归并排序的方法，先求左半部分的逆序对，再求右半部分的逆序对，最后求整个数列的逆序对。
class Solution {
public int reversePairs(int[] nums) {
int len = nums.length;
if (len < 2) {
return 0;
}
// 如果不能在nums修改，就copy一下nums
int[] copy = new int[len];
for (int i = 0; i < len; i++) {
copy[i] = nums[i];
}
int[] temp = new int[len];
return reversePairs(copy, 0, len - 1, temp);
}
private int reversePairs(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + ((right - left) >> 1);
int leftPairs = reversePairs(nums, left, mid, temp);
int rightPairs = reversePairs(nums, mid + 1, right, temp);
if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid, right, temp);
return crossPairs + leftPairs + rightPairs;
}
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left;
int j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
nums[k] = temp[j];
j++;
} else if (j == right + 1) {
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
} else {
nums[k] = temp[j];
j++;
count += mid - i + 1;
}
}
return count;
}
}给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 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;
}
}输入整数数组 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;
}
}