【图解算法数据结构】分治算法篇 + Java代码实现

---

一、重建二叉树

public class Solution {int[] preorder;HashMap<Integer, Integer> dic = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;for (int i = 0; i < inorder.length; i++) {dic.put(inorder[i], i);}return recur(0, 0, inorder.length - 1);}TreeNode recur(int root, int left, int right) {if (left > right) {// 递归终止return null;}// 建立根节点TreeNode node = new TreeNode(preorder[root]);// 划分根节点、左子树、右子树int i = dic.get(preorder[root]);// 开启左子树递归node.left = recur(root + 1, left, i - 1);// 开启右子树递归 i - left + root + 1 含义为 根节点索引 + 左子树长度 + 1node.right = recur(root + i - left + 1, i + 1, right);// 回溯返回根节点return node;}public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}}

---

二、数值的整数次方

public class Solution {public double myPow(double x, int n) {long b = n;double res = 1.0;if (b < 0) {x = 1 / x;b = -b;}while (b > 0) {if ((b & 1) == 1) {res *= x;}x *= x;b >>= 1;}return res;}
}

---

三、打印从 1 到最大的 n 位数

public class Solution {public int[] printNumbers(int n) {int[] res = new int[(int) Math.pow(10, n) - 1];for (int i = 0; i < res.length; i++) {res[i] = i + 1;}return res;}
}

---

四、二叉搜索树的后序遍历序列

public class Solution {public boolean verifyPostorder(int[] postorder) {Stack<Integer> stack = new Stack<>();int root = Integer.MAX_VALUE;for(int i = postorder.length - 1; i >= 0; i--) {if(postorder[i] > root) {return false;}while(!stack.isEmpty() && stack.peek() > postorder[i]) {root = stack.pop();}stack.add(postorder[i]);}return true;}
}

---

五、数组中的逆序对

public class Solution {int[] nums, tmp;public int reversePairs(int[] nums) {this.nums = nums;tmp = new int[nums.length];return mergeSort(0, nums.length - 1);}private int mergeSort(int l, int r) {// 终止条件if (l >= r) {return 0;}// 递归划分int m = (l + r) / 2;int res = mergeSort(l, m) + mergeSort(m + 1, r);// 合并阶段int i = l, j = m + 1;for (int k = l; k <= r; k++) {tmp[k] = nums[k];}for (int k = l; k <= r; k++) {if (i == m + 1) {nums[k] = tmp[j++];} else if (j == r + 1 || tmp[i] <= tmp[j])nums[k] = tmp[i++];else {nums[k] = tmp[j++];res += m - i + 1; // 统计逆序对}}return res;}
}