个人技术博客：www.zhenganwen.top
二叉树
实现二叉树的先序、中序、后续遍历，包括递归方式和非递归方式
递归方式
public static class Node{
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}
public static void preOrderRecursive(Node root) {
if (root != null) {
System.out.print(root.data+" ");
preOrderRecursive(root.left);
preOrderRecursive(root.right);
}
}
public static void medOrderRecursive(Node root) {
if (root != null) {
medOrderRecursive(root.left);
System.out.print(root.data+" ");
medOrderRecursive(root.right);
}
}
public static void postOrderRecursive(Node root) {
if (root != null) {
postOrderRecursive(root.left);
postOrderRecursive(root.right);
System.out.print(root.data+" ");
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
preOrderRecursive(root); //1 2 4 5 3 6 7
System.out.println();
medOrderRecursive(root); //4 2 5 1 6 3 7
System.out.println();
postOrderRecursive(root); //4 5 2 6 7 3 1
System.out.println();
}
复制代码以先根遍历二叉树为例，可以发现递归方式首先尝试打印当前结点的值，随后尝试打印左子树，打印完左子树后尝试打印右子树，递归过程的base case是当某个结点为空时停止子过程的展开。这种递归尝试是由二叉树本身的结构所决定的，因为二叉树上的任意结点都可看做一棵二叉树的根结点（即使是叶子结点，也可以看做是一棵左右子树为空的二叉树根结点）。
观察先序、中序、后序三个递归方法你会发现，不同点在于打印当前结点的值这一操作的时机。你会发现每个结点会被访问三次：进入方法时算一次、递归处理左子树完成之后返回时算一次、递归处理右子树完成之后返回时算一次。因此在preOrderRecursive中将打印语句放到方法开始时就产生了先序遍历；在midOrderRecursive中，将打印语句放到递归chu处理左子树完成之后就产生了中序遍历。
非递归方式
先序遍历
拿到一棵树的根结点后，首先打印该结点的值，然后将其非空右孩子、非空左孩子依次压栈。栈非空循环：从栈顶弹出结点（一棵子树的根节点）并打印其值，再将其非空右孩子、非空左孩子依次压栈。
public static void preOrderUnRecur(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
Node cur;
while (!stack.empty()) {
cur = stack.pop();
System.out.print(cur.data+" ");
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
System.out.println();
}
复制代码你会发现压栈的顺序和打印的顺序是相反的，压栈是先根结点，然后有右孩子就压右孩子、有左孩子就压左孩子，这是利用栈的后进先出。每次获取到一棵子树的根节点之后就可以获取其左右孩子，因此无需保留其信息，直接弹出并打印，然后保留其左右孩子到栈中即可。
中序遍历
对于一棵树，将该树的左边界全部压栈，root的走向是只要左孩子不为空就走向左孩子。当左孩子为空时弹出栈顶结点（此时该结点是一棵左子树为空的树的根结点，根据中序遍历可以直接打印该结点，然后中序遍历该结点的右子树）打印，如果该结点的右孩子非空（说明有右子树），那么将其右孩子压栈，这个右孩子又可能是一棵子树的根节点，因此将这棵子树的左边界压栈，这时回到了开头，以此类推。
public static void medOrderUnRecur(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
System.out.print(root.data+" ");
root = root.right;
}
}
System.out.println();
}
复制代码后序遍历
思路一：准备两个栈，一个栈用来保存遍历时的结点信息，另一个栈用来排列后根顺序（根节点先进栈，右孩子再进，左孩子最后进）。
public static void postOrderUnRecur1(Node root) {
if (root == null) {
return;
}
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.empty()) {
root = stack1.pop();
if (root.left != null) {
stack1.push(root.left);
}
if (root.right != null) {
stack1.push(root.right);
}
stack2.push(root);
}
while (!stack2.empty()) {
System.out.print(stack2.pop().data + " ");
}
System.out.println();
}
复制代码思路二：只用一个栈。借助两个变量
h和c，h代表最近一次打印过的结点，c代表栈顶结点。首先将根结点压栈，此后栈非空循环，令c等于栈顶元素（c=stack.peek()）执行以下三个分支：
c的左右孩子是否与h相等，如果都不相等，说明c的左右孩子都不是最近打印过的结点，由于左右孩子是左右子树的根节点，根据后根遍历的特点，左右子树肯定都没打印过，那么将左孩子压栈（打印左子树）。- 分支1没有执行说明
c的左孩子要么不存在；要么左子树刚打印过了；要么右子树刚打印过了。这时如果是前两种情况中的一种，那就轮到打印右子树了，因此如果c的右孩子非空就压栈。- 如果前两个分支都没执行，说明
c的左右子树都打印完了，因此弹出并打印c结点，更新一下h。
public static void postOrderUnRecur2(Node root) {
if (root == null) {
return;
}
Node h = null; //最近一次打印的结点
Node c = null; //代表栈顶结点
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
c = stack.peek();
if (c.left != null && c.left != h && c.right != h) {
stack.push(c.left);
} else if (c.right != null && c.right != h) {
stack.push(c.right);
} else {
System.out.print(stack.pop().data + " ");
h = c;
}
}
System.out.println();
}
复制代码在二叉树中找一个结点的后继结点，结点除lleft,right指针外还包含一个parent指针
这里的后继结点不同于链表的后继结点。在二叉树中，前驱结点和后继结点是按照二叉树中两个结点被中序遍历的先后顺序来划分的。比如某二叉树的中序遍历是
2 1 3，那么1的后继结点是3，前驱结点是2
你当然可以将二叉树中序遍历一下，在遍历到该结点的时候标记一下，那么下一个要打印的结点就是该结点的后继结点。
我们可以推测一下，当我们来到二叉树中的某个结点时，如果它的右子树非空，那么它的后继结点一定是它的右子树中最靠左的那个结点；如果它的右孩子为空，那么它的后继结点一定是它的祖先结点中，把它当做左子孙（它存在于祖先结点的左子树中）的那一个，否则它没有后继结点。
这里如果它的右孩子为空的情况比较难分析，我们可以借助一个指针parent，当前来到的结点node和其父结点parent的parent.left比较，如果相同则直接返回parent，否则node来到parent的位置，parent则继续向上追溯，直到parent到达根节点为止若node还是不等于parent的左孩子，则返回null表明给出的结点没有后继结点。
public class FindSuccessorNode {
public static class Node{
int data;
Node left;
Node right;
Node parent;
public Node(int data) {
this.data = data;
}
}
public static Node findSuccessorNode(Node node){
if (node == null) {
return null;
}
if (node.right != null) {
node = node.right;
while (node.left != null) {
node = node.left;
}
return node;
} else {
Node parent = node.parent;
while (parent != null && parent.left != node) {
node = parent;
parent = parent.parent;
}
return parent == null ? null : parent;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.left.parent = root;
root.left.left = new Node(4);
root.left.left.parent = root.left;
root.left.right = new Node(5);
root.left.right.parent = root.left;
root.right = new Node(3);
root.right.parent = root;
root.right.right = new Node(6);
root.right.right.parent = root.right;
if (findSuccessorNode(root.left.right) != null) {
System.out.println("node5's successor node is:"+findSuccessorNode(root.left.right).data);
} else {
System.out.println("node5's successor node doesn't exist");
}
if (findSuccessorNode(root.right.right) != null) {
System.out.println("node6's successor node is:"+findSuccessorNode(root.right.right).data);
} else {
System.out.println("node6's successor node doesn't exist");
}
}
}
复制代码介绍二叉树的序列化和反序列化
序列化
二叉树的序列化要注意的两个点如下：
- 每序列化一个结点数值之后都应该加上一个结束符表示一个结点序列化的终止，如
!。- 不能忽视空结点的存在，可以使用一个占位符如
#表示空结点的序列化。
/** * 先根遍历的方式进行序列化 * @param node 序列化来到了哪个结点 * @return */
public static String serializeByPre(Node node) {
if (node == null) {
return "#!";
}
//收集以当前结点为根节点的树的序列化信息
String res = node.data + "!";
//假设能够获取左子树的序列化结果
res += serializeByPre(node.left);
//假设能够获取右子树的序列化结果
res += serializeByPre(node.right);
//返回以当前结点为根节点的树的序列化结果
return res;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right = new Node(3);
root.right.right = new Node(6);
System.out.println(serializeByPre(root));
}
复制代码重建
怎么序列化的，就怎么反序列化
public static Node reconstrut(String serializeStr) {
if (serializeStr != null) {
String[] datas = serializeStr.split("!");
if (datas.length > 0) {
//借助队列保存结点数值
Queue<String> queue = new LinkedList<>();
for (String data : datas) {
queue.offer(data);
}
return recon(queue);
}
}
return null;
}
private static Node recon(Queue<String> queue) {
//依次出队元素重建结点
String data = queue.poll();
//重建空结点，也是base case，当要重建的某棵子树为空时直接返回
if (data.equals("#")) {
return null;
}
//重建头结点
Node root = new Node(Integer.parseInt(data));
//重建左右子树
root.left = recon(queue);
root.right = recon(queue);
return root;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right = new Node(3);
root.right.right = new Node(6);
String str = serializeByPre(root);
Node root2 = reconstrut(str);
System.out.println(serializeByPre(root2));
}
复制代码判断一个树是否是平衡二叉树
平衡二叉树的定义：当二叉树的任意一棵子树的左子树的高度和右子树的高度相差不超过1时，该二叉树为平衡二叉树。
根据定义可知，要确认一个二叉树是否是平衡二叉树势必要遍历所有结点。而遍历到每个结点时，要想知道以该结点为根结点的子树是否是平衡二叉树，我们要收集两个信息：
- 该结点的左子树、右子树是否是平衡二叉树
- 左右子树的高度分别是多少，相差是否超过1
那么我们来到某个结点时（子过程），我们需要向上层（父过程）返回的信息就是该结点为根结点的树是否是平衡二叉树以及该结点的高度，这样的话，父过程就能继续向上层返回应该收集的信息。
package top.zhenganwen.algorithmdemo.recursive;
/** * 判断是否为平衡二叉树 */
public class IsBalanceBTree {
public static class Node{
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}
/** * 遍历时，来到某个结点需要收集的信息 * 1、以该结点为根节点的树是否是平衡二叉树 * 2、该结点的高度 */
public static class ReturnData {
public boolean isBalanced;
public int height;
public ReturnData(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
public static ReturnData isBalancedBinaryTree(Node node){
if (node == null) {
return new ReturnData(true, 0);
}
ReturnData leftData = isBalancedBinaryTree(node.left);
if (leftData.isBalanced == false) {
//只要有一棵子树不是平衡二叉树，则会一路返回false，该树的高度自然不必收集了
return new ReturnData(false, 0);
}
ReturnData rightDta = isBalancedBinaryTree(node.right);
if (rightDta.isBalanced == false) {
return new ReturnData(false, 0);
}
//返回该层收集的结果
if (Math.abs(leftData.height - rightDta.height) > 1) {
return new ReturnData(false, 0);
}
//若是平衡二叉树，树高等于左右子树较高的那个加1
return new ReturnData(true, Math.max(leftData.height, rightDta.height) + 1);
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.left.left = new Node(4);
root.right = new Node(3);
root.right.right = new Node(5);
root.right.right.right = new Node(6);
System.out.println(isBalancedBinaryTree(root).isBalanced); //false
}
}
复制代码递归很好用，该题中的递归用法也是一种经典用法，可以高度套路：
- 分析问题的解决需要哪些步骤（这里是遍历每个结点，确认每个结点为根节点的子树是否为平衡二叉树）
- 确定递归：父问题是否和子问题相同
- 子过程要收集哪些信息
- 本次递归如何利用子过程返回的信息得到本过程要返回的信息
base case
判断一棵树是否是搜索二叉树
搜索二叉树的定义：对于二叉树的任意一棵子树，其左子树上的所有结点的值小于该子树的根节点的值，而其右子树上的所有结点的值大于该子树的根结点的值，并且整棵树上任意两个结点的值不同。
根据定义，搜索二叉树的中序遍历打印将是一个升序序列。因此我们可以利用二叉树的中序遍历的非递归方式，比较中序遍历时相邻两个结点的大小，只要有一个结点的值小于其后继结点的那就不是搜索二叉树。
import java.util.Stack;
/** * 判断是否是搜索二叉树 */
public class IsBST {
public static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}
public static boolean isBST(Node root) {
if (root == null) {
return true;
}
int preData = Integer.MIN_VALUE;
Stack<Node> stack = new Stack<>();
while (root != null || !stack.empty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
Node node = stack.pop();
if (node.data < preData) {
return false;
} else {
preData = node.data;
}
root = node.right;
}
}
return true;
}
public static void main(String[] args) {
Node root = new Node(6);
root.left = new Node(3);
root.left.left = new Node(1);
root.left.right = new Node(4);
root.right = new Node(8);
root.right.left = new Node(9);
root.right.right = new Node(10);
System.out.println(isBST(root)); //false
}
}
复制代码判断一棵树是否是完全二叉树
根据完全二叉树的定义，如果二叉树上某个结点有右孩子无左孩子则一定不是完全二叉树；否则如果二叉树上某个结点有左孩子而没有右孩子，那么该结点所在的那一层上，该结点右侧的所有结点应该是叶子结点，否则不是完全二叉树。
import java.util.LinkedList;
import java.util.Queue;
/** * 判断是否为完全二叉树 */
public class IsCompleteBTree {
public static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}
public static boolean isCompleteBTree(Node root) {
if (root == null) {
return true;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node node = queue.poll();
//左空右不空
if (node.left == null && node.right != null) {
return false;
}
//如果开启了叶子结点阶段，结点不能有左右孩子
if (leaf &&
(node.left != null || node.right != null)) {
return false;
}
//将下一层要遍历的加入到队列中
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
} else {
//左右均为空，或左不空右空。该结点同层的右侧结点均为叶子结点，开启叶子结点阶段
leaf = true;
}
}
return true;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(4);
System.out.println(isCompleteBTree(root));//false
}
}
复制代码已知一棵完全二叉树，求其结点个数，要求时间复杂度0(N)
如果我们遍历二叉树的每个结点来计算结点个数，那么时间复杂度将是O(N^2)，我们可以利用满二叉树的结点个数为2^h-1（h为树的层数）来加速这个过程。
首先完全二叉树，如果其左子树的最左结点在树的最后一层，那么其右子树肯定是满二叉树，且高度为h-1；否则其左子树肯定是满二叉树，且高度为h-2。也就是说，对于一个完全二叉树结点个数的求解，我们可以分解求解过程：1个根结点+ 一棵满二叉树（高度为h-1或者h-2）+ 一棵完全二叉树（高度为h-1）。前两者的结点数是可求的（1+2^level -1=2^level），后者就又成了求一棵完全二叉树结点数的问题了，可以使用递归。
/** * 求一棵完全二叉树的节点个数 */
public class CBTNodesNum {
public static class Node {
int data;
Node left;
Node right;
public Node(int data) {
super();
this.data = data;
}
}
// 获取完全二叉树的高度
public static int getLevelOfCBT(Node root) {
if (root == null)
return 0;
int level = 0;
while (root != null) {
level++;
root = root.left;
}
return level;
}
public static int getNodesNum(Node node) {
//base case
if (node == null)
return 0;
int level = getLevelOfCBT(node);
if (getLevelOfCBT(node.right) == level - 1) {
// 左子树满，且高度为 level-1；收集左子树节点数2^(level-1)-1和头节点，对右子树重复此过程
int leftNodesAndRoot = 1 << (level - 1);
return getNodesNum(node.right) + leftNodesAndRoot;
} else {
// 右子树满，且高度为 level-2；收集右子树节点数2^(level-2)-1和头节点1,对左子树重复此过程
int rightNodesAndRoot = 1 << (level - 2);
return getNodesNum(node.left) + rightNodesAndRoot;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
System.out.println(getNodesNum(root));
}
}
复制代码并查集
并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union：将两个子集合并成同一个集合。
并查集结构的实现
首先并查集本身是一个结构，我们在构造它的时候需要将所有要操作的数据扔进去，初始时每个数据自成一个结点，且每个结点都有一个父指针（初始时指向自己）。
初始时并查集中的每个结点都算是一个子集，我们可以对任意两个元素进行合并操作。值得注意的是，union(nodeA,nodeB)并不是将结点nodeA和nodeB合并成一个集合，而是将nodeA所在的集合和nodeB所在的集合合并成一个新的子集：
那么合并两个集合的逻辑是什么呢？首先要介绍一下代表结点这个概念：找一结点所在集合的代表结点就是找这个集合中父指针指向自己的结点（并查集初始化时，每个结点都是各自集合的代表结点）。那么合并两个集合就是将结点个数较少的那个集合的代表结点的父指针指向另一个集合的代表结点：
还有一个find操作：查找两个结点是否所属同一个集合。我们只需判断两个结点所在集合的代表结点是否是同一个就可以了：
代码示例：
import java.util.*;
public class UnionFindSet{
public static class Node{
//whatever you like to store int , char , String ..etc
}
private Map<Node,Node> fatherMap;
private Map<Node,Integer> nodesNumMap;
//give me the all nodes need to save into the UnionFindSet
public UnionFindSet(List<Node> nodes){
fatherMap = new HashMap();
nodesNumMap = new HashMap();
for(Node node : nodes){
fatherMap.put(node,node);
nodesNumMap.put(node,1);
}
}
public void union(Node a,Node b){
if(a == null || b == null){
return;
}
Node rootOfA = getRoot(a);
Node rootOfB = getRoot(b);
if(rootOfA != rootOfB){
int numOfA = nodesNumMap.get(rootOfA);
int numOfB = nodesNumMap.get(rootOfB);
if(numOfA >= numOfB){
fatherMap.put(rootOfB , rootOfA);
nodesNumMap.put(rootOfA, numOfA + numOfB);
}else{
fatherMap.put(rootOfA , rootOfB);
nodesNumMap.put(rootOfB, numOfA + numOfB);
}
}
}
public boolean find(Node a,Node b){
if(a == null || b == null){
return false;
}
Node rootOfA = getRoot(a);
Node rootOfB = getRoot(b);
return rootOfA == rootOfB ? true : false;
}
public Node getRoot(Node node){
if(node == null){
return null;
}
Node father = fatherMap.get(node);
if(father != node){
father = fatherMap.get(father);
}
fatherMap.put(node, father);
return father;
}
public static void main(String[] args){
Node a = new Node();
Node b = new Node();
Node c = new Node();
Node d = new Node();
Node e = new Node();
Node f = new Node();
Node[] nodes = {a,b,c,d,e,f};
UnionFindSet set = new UnionFindSet(Arrays.asList(nodes));
set.union(a, b);
set.union(c, d);
set.union(b, e);
set.union(a, c);
System.out.println(set.find(d,e));
}
}
复制代码你会发现union和find的过程中都会有找一个结点所在集合的代表结点这个过程，所以我把它单独抽出来成一个getRoot，而且利用递归做了一个优化：找一个结点所在集合的代表结点时，会不停地向上找父指针指向自己的结点，最后在递归回退时将沿途路过的结点的父指针改为直接指向代表结点：
诚然，这样做是为了提高下一次查找的效率。
并查集的应用
并查集结构本身其实很简单，但是其应用却很难。这里以岛问题做引子，当矩阵相当大的时候，用单核CPU去跑这个遍历和感染效率是很低的，可能会使用并行计算框架来完成岛数量的统计。也就是说矩阵可能被分割成几个部分，逐个统计，最后在汇总。那么问题来了：
上面这个矩阵的岛数量是1；但如果从中间竖着切开，那么左边的岛数量是1，右边的岛数量是2，总数是3。如何处理切割后，相邻子矩阵之间的边界处的1相邻导致的重复统计呢？其实利用并查集的特性就很容易解决这个问题：
首先将切割边界处的数据封装成结点加入到并查集中并合并同一个岛上的结点，在分析边界时，查边界两边的1是否在同一个集合，如果不在那就union这两个结点，并将总的岛数量减1；否则就跳过此行继续分析下一行边界上的两个点。
贪心策略
拼接最小字典序
给定一个字符串类型的数组strs，找到一种拼接方式，使得把所有字符串拼起来之后形成的字符串具有最低的字典序。
此题很多人的想法是把数组按照字典序排序，然后从头到尾连接，形成的字符串就是所有拼接结果中字典序最小的那个。但这很容易证明是错的，比如
[ba,b]的排序结果是[b,ba]，拼接结果是bba，但bab的字典序更小。正确的策略是，将有序字符串数组从头到尾两两拼接时，应取两两拼接的拼接结果中字典序较小的那个。证明如下
如果令.代表拼接符号，那么这里的命题是如果str1.str2 < str2.str2且str2.str3 < str3.str2，那么一定有str1.str3 < str3.str1。这可以使用数学归纳法来证明。如果将a~z对应到0~25，比较两个字符串的字典序的过程，其实就比较两个26进制数大小的过程。str1.str2拼接的过程可以看做两个26进制数拼接的过程，若将两字符串解析成数字int1和int2，那么拼接就对应int1 * 26^(str2的长度) + int2，那么证明过程就变成了两个整数不等式递推另一个不等式了。
金条和铜板
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的 金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金 条，怎么分最省铜板？
例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长度60的金条分成10和50，花费60 再把长度50的金条分成20和30，花费50 一共花费110铜板。但是如果， 先把长度60的金条分成30和30，花费60 再把长度30金条分成10和20，花费30 一共花费90铜板。
输入一个数组，返回分割的最小代价。
贪心策略，将给定的数组中的元素扔进小根堆，每次从小根堆中先后弹出两个元素（如10和20），这两个元素的和（如30）就是某次分割得到这两个元素的花费，再将这个和扔进小根堆。直到小根堆中只有一个元素为止。（比如扔进30之后，弹出30、30，此次花费为30+30=60，再扔进60，堆中只有一个60了，结束，总花费30+60-=90）
public stzuoatic int lessMoney(int arr[]){
if (arr == null || arr.length == 0) {
return 0;
}
//PriorityQueue是Java语言对堆结构的一个实现，默认将按自然顺序的最小元素放在堆顶
PriorityQueue<Integer> minHeap = new PriorityQueue();
for (int i : arr) {
minHeap.add(i);
}
int res = 0;
int curCost = 0;
while (minHeap.size() > 1) {
curCost = minHeap.poll() + minHeap.poll();
res += curCost;
minHeap.add(curCost);
}
return res;
}
public static void main(String[] args) {
int arr[] = {10, 20, 30};
System.out.println(lessMoney(arr));
}
复制代码IPO
输入： 参数1：正数数组costs；参数2：正数数组profits；参数3：正数k；参数4：正数m。costs[i]表示i号项目的花费（成本），profits[i]表示i号项目做完后在扣除花费之后还能挣到的钱(利润)，k表示你不能并行，只能串行的最多做k个项目 m表示你初始的资金。
说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出： 你最后获得的最大钱数。
贪心策略：借助两个堆，一个是存放各个项目花费的小根堆、另一个是存放各个项目利润的大根堆。首先将所有项目放入小根堆而大根堆为空，对于手头上现有的资金（本金），将能做的项目（成本低于现有资金）从小根堆依次弹出并放入到大根堆，再弹出大根堆堆顶项目来完成，完成后根据利润更新本金。本金更新后，再将小根堆中能做的项目弹出加入到大根堆中，再弹出大根堆中的堆顶项目来做，重复此操作，直到某次本金更新和两个堆更新后大根堆无项目可做或者完成的项目个数已达k个为止。
import java.util.Comparator;
import java.util.PriorityQueue;
public class IPO {
public class Project{
int cost;
int profit;
public Project(int cost, int profit) {
this.cost = cost;
this.profit = profit;
}
}
public class MinCostHeap implements Comparator<Project> {
@Override
public int compare(Project p1, Project p2) {
return p1.cost-p2.cost; //升序，由此构造的堆将把花费最小项目的放到堆顶
}
}
public class MaxProfitHeap implements Comparator<Project> {
@Override
public int compare(Project p1, Project p2) {
return p2.profit-p1.profit;
}
}
public int findMaximizedCapital(int costs[], int profits[], int k, int m) {
int res = 0;
PriorityQueue<Project> minCostHeap = new PriorityQueue<>(new MinCostHeap());
PriorityQueue<Project> maxProfitHeap = new PriorityQueue<>(new MaxProfitHeap());
for (int i = 0; i < costs.length; i++) {
Project project = new Project(costs[i], profits[i]);
minCostHeap.add(project);
}
for (int i = 0; i < k; i++) {
//unlock project
while (minCostHeap.peek().cost < m) {
maxProfitHeap.add(minCostHeap.poll());
}
if (maxProfitHeap.isEmpty()) {
return m;
}
m += maxProfitHeap.poll().profit;
}
return m;
}
}
复制代码会议室项目宣讲
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数组，里面 是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行 的宣讲的场次最多。返回这个最多的宣讲场次。
贪心策略：
1、开始时间最早的项目先安排。反例：开始时间最早，但持续时间占了一整天，其他项目无法安排。
2、持续时间最短的项目先安排。反例：这样安排会导致结束时间在此期间和开始时间在此期间的所有项目不能安排。
3、最优策略：最先结束的项目先安排。
import java.util.Arrays;
import java.util.Comparator;
public class Schedule {
public class Project {
int start;
int end;
}
public class MostEarlyEndComparator implements Comparator<Project> {
@Override
public int compare(Project p1, Project p2) {
return p1.end-p2.end;
}
}
public int solution(Project projects[],int currentTime) {
//sort by the end time
Arrays.sort(projects, new MostEarlyEndComparator());
int res = 0;
for (int i = 0; i < projects.length; i++) {
if (currentTime <= projects[i].start) {
res++;
currentTime = projects[i].end;
}
}
return res;
}
}
复制代码经验：贪心策略相关的问题，累积经验就好，不必花费大量精力去证明。解题的时候要么找相似点，要么脑补策略然后用对数器、测试用例去证。
递归和动态规划
暴力递归：
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件(base case)
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
动态规划：
- 从暴力递归中来
- 将每一个子问题的解记录下来，避免重复计算
- 把暴力递归的过程，抽象成了状态表达
- 并且存在化简状态表达，使其更加简洁的可能
P和NP
P指的是我明确地知道怎么算，计算的流程很清楚；而NP问题指的是我不知道怎么算，但我知道怎么尝试（暴力递归）。
暴力递归
n!问题
我们知道n!的定义，可以根据定义直接求解：
int getFactorial_1(int n){
int res=1;
for(int i = 1 ; i <= n ; n++){
res*=i;
}
return res;
}
复制代码但我们可以这样想，如果知道(n-1)!，那通过(n-1)! * n不就得出n!了吗？于是我们就有了如下的尝试：
int getFactorial_2(int n){
if(n=1)
return 1;
return getFactorial_2(n-1) * n;
}
复制代码n!的状态依赖(n-1)!，(n-1)!依赖(n-2)!，就这样依赖下去，直到n=1这个突破口，然后回溯，你会发现整个过程就回到了1 * 2 * 3 * …… * (n-1) * n的计算过程。
汉诺塔问题
该问题最基础的一个模型就是，一个竹竿上放了2个圆盘，需要先将最上面的那个移到辅助竹竿上，然后将最底下的圆盘移到目标竹竿，最后把辅助竹竿上的圆盘移回目标竹竿。
public class Hanoi {
public static void process(String source,String target,String auxiliary,int n){
if (n == 1) {
System.out.println("move 1 disk from " + source + " to " + target);
return;
}
//尝试把前n-1个圆盘暂时放到辅助竹竿->子问题
process(source, auxiliary, target, n - 1);
//将底下最大的圆盘移到目标竹竿
System.out.println("move 1 disk from "+source+" to "+target);
//再尝试将辅助竹竿上的圆盘移回到目标竹竿->子问题
process(auxiliary,target,source,n-1);
}
public static void main(String[] args) {
process("Left", "Right", "Help", 3);
}
}
复制代码根据Master公式计算得T(N) = T(N-1)+1+T(N-1)，时间复杂度为O(2^N)
打印一个字符串的所有子序列
字符串的子序列和子串有着不同的定义。子串指串中相邻的任意个字符组成的串，而子序列可以是串中任意个不同字符组成的串。
尝试：开始时，令子序列为空串，扔给递归方法。首先来到字符串的第一个字符上，这时会有两个决策：将这个字符加到子序列和不加到子序列。这两个决策会产生两个不同的子序列，将这两个子序列作为这一级收集的信息扔给子过程，子过程来到字符串的第二个字符上，对上级传来的子序列又有两个决策，……这样最终能将所有子序列组合穷举出来：
/** * 打印字符串的所有子序列-递归方式 * @param str 目标字符串 * @param index 当前子过程来到了哪个字符的决策上（要还是不要） * @param res 上级扔给本级的子序列 */
public static void printAllSubSequences(String str,int index,String res) {
//base case ： 当本级子过程来到的位置到达串末尾，则直接打印
if(index == str.length()) {
System.out.println(res);
return;
}
//决策是否要index位置上的字符
printAllSubSequences(str, index+1, res+str.charAt(index));
printAllSubSequences(str, index+1, res);
}
public static void main(String[] args) {
printAllSubSequences("abc", 0, "");
}
复制代码打印一个字符串的所有全排列结果
/** * 本级任务：将index之后（包括index）位置上的字符和index上的字符交换，将产生的所有结果扔给下一级 * @param str * @param index */
public static void printAllPermutations(char[] chs,int index) {
//base case
if(index == chs.length-1) {
System.out.println(chs);
return;
}
for (int j = index; j < chs.length; j++) {
swap(chs,index,j);
printAllPermutations(chs, index+1);
}
}
public static void swap(char[] chs,int i,int j) {
char temp = chs[i];
chs[i] = chs[j];
chs[j] = temp;
}
public static void main(String[] args) {
printAllPermutations("abc".toCharArray(), 0);
}
复制代码母牛生牛问题
母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设不会死。求N年后，母牛的数量。
那么求第n年母牛的数量，按照此公式顺序计算即可，但这是O(N)的时间复杂度，存在O(logN)的算法（放到进阶篇中讨论）。
暴力递归改为动态规划
为什么要改动态规划？有什么意义？
动态规划由暴力递归而来，是对暴力递归中的重复计算的一个优化，策略是空间换时间。
最小路径和
给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。
递归尝试版本
/** * 从矩阵matrix的(i,j)位置走到右下角元素，返回最小沿途元素和。每个位置只能向右或向下 * * @param matrix * @param i * @param j * @return 最小路径和 */
public static int minPathSum(int matrix[][], int i, int j) {
// 如果(i,j)就是右下角的元素
if (i == matrix.length - 1 && j == matrix[0].length - 1) {
return matrix[i][j];
}
// 如果(i,j)在右边界上，只能向下走
if (j == matrix[0].length - 1) {
return matrix[i][j] + minPathSum(matrix, i + 1, j);
}
// 如果(i,j)在下边界上，只能向右走
if (i == matrix.length - 1) {
return matrix[i][j] + minPathSum(matrix, i, j + 1);
}
// 不是上述三种情况，那么(i,j)就有向下和向右两种决策，取决策结果最小的那个
int left = minPathSum(matrix, i, j + 1);
int down = minPathSum(matrix, i + 1, j);
return matrix[i][j] + Math.min(left,down );
}
public static void main(String[] args) {
int matrix[][] = {
{ 9, 1, 0, 1 },
{ 4, 8, 1, 0 },
{ 1, 4, 2, 3 }
};
System.out.println(minPathSum(matrix, 0, 0)); //14
}
复制代码根据尝试版本改动态规划
上述暴力递归的缺陷在于有些子过程是重复的。比如minPathSum(matrix,0,1)和minPathSum(matrix,1,0)都会依赖子过程minPathSum(matrix,1,1)的状态（执行结果），那么在计算minPathSum(matrix,0,0)时势必会导致minPathSum(matrix,1,1)的重复计算。那我们能否通过对子过程计算结果进行缓存，在再次需要时直接使用，从而实现对整个过程的一个优化呢。
由暴力递归改动态规划的核心就是将每个子过程的计算结果进行一个记录，从而达到空间换时间的目的。那么minPath(int matrix[][],int i,int j)中变量i和j的不同取值将导致i*j种结果，我们将这些结果保存在一个i*j的表中，不就达到动态规划的目的了吗？
观察上述代码可知，右下角、右边界、下边界这些位置上的元素是不需要尝试的（只有一种走法，不存在决策问题），因此我们可以直接将这些位置上的结果先算出来：
而其它位置上的元素的走法则依赖右方相邻位置（i，j+1）走到右下角的最小路径和和下方相邻位置（i+1，j）走到右下角的最小路径和的大小比较，基于此来做一个向右走还是向左走的决策。但由于右边界、下边界位置上的结果我们已经计算出来了，因此对于其它位置上的结果也就不难确定了：
我们从base case开始，倒着推出了所有子过程的计算结果，并且没有重复计算。最后minPathSum(matrix,0,0)也迎刃而解了。
这就是动态规划，它不是凭空想出来的。首先我们尝试着解决这个问题，写出了暴力递归。再由暴力递归中的变量的变化范围建立一张对应的结果记录表，以
base case作为突破口确定能够直接确定的结果，最后解决普遍情况对应的结果。
一个数是否是数组中任意个数的和
给你一个数组arr，和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim，返回true或者false。
此题的思路跟求解一个字符串的所有子序列的思路一致，穷举出数组中所有任意个数相加的不同结果。
暴力递归版本
/** * 选择任意个arr中的元素相加是否能得到aim * * @param arr * @param aim * @param sum 上级扔给我的结果 * @param i 决策来到了下标为i的元素上 * @return */
public static boolean isSum(int arr[], int aim, int sum,int i) {
//决策完毕
if (i == arr.length) {
return sum == aim;
}
//决策来到了arr[i]：加上arr[i]或不加上。将结果扔给下一级
return isSum(arr, aim, sum + arr[i], i + 1) || isSum(arr, aim, sum, i + 1);
}
public static void main(String[] args) {
int arr[] = {1, 2, 3};
System.out.println(isSum(arr, 5, 0, 0));
System.out.println(isSum(arr, 6, 0, 0));
System.out.println(isSum(arr, 7, 0, 0));
}
复制代码暴力递归改动态规划（高度套路）
-
首先看递归函数的参数，找出变量。这里
arr和aim是固定不变的，可变的只有sum和i。 -
对应变量的变化范围建立一张表保存不同子过程的结果，这里
i的变化范围是0~arr.length-1即0~2，而sum的变化范围是0~数组元素总和，即0~6。因此需要建一张3*7的表。 -
从
base case入手，计算可直接计算的子过程，以isSum(5,0,0)的计算为例，其子过程中“是否+3”的决策之后的结果是可以确定的： -
按照递归函数中
base case下的尝试过程，推出其它子过程的计算结果，这里以i=1,sum=1的推导为例：
哪些暴力递归能改为动态规划
看过上述例题之后你会发现只要你能够写出尝试版本，那么改动态规划是高度套路的。但是不是所有的暴力递归都能够改动态规划呢？不是的，比如汉诺塔问题和N皇后问题，他们的每一步递归都是必须的，没有多余。这就涉及到了递归的有后效性和无后效性。
有后效性和无后效性
无后效性是指对于递归中的某个子过程，其上级的决策对该级的后续决策没有任何影响。比如最小路径和问题中以下面的矩阵为例：
对于（1，1）位置上的8，无论是通过9->1->8还是9->4->8来到这个8上的，这个8到右下角的最小路径和的计算过程不会改变。这就是无后效性。
只有无后效性的暴力递归才能改动态规划。
哈希
哈希函数
百科：散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将输入域中的数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。
哈希函数的性质
哈希函数的输入域可以是非常大的范围，比如，任意一个字符串，但是输出域是固定的范围（一定位数的bit），假设为S，并具有如下性质：
- 典型的哈希函数都有无限的输入值域。
- 当给哈希函数传入相同的输入值时，返回值一样。
- 当给哈希函数传入不同的输入值时，返回值可能一样，也可能不一样，这时当然的，因为输出域统一是S，所以会有不同的输入值对应在S中的一个元素上（这种情况称为 哈希冲突）。
- 最重要的性质是很多不同的输入值所得到的返回值会均匀分布在S上。
前3点性质是哈希函数的基础，第4点是评价一个哈希函数优劣的关键，不同输入值所得到的所有返回值越均匀地分布在S上，哈希函数越优秀，并且这种均匀分布与输入值出现的规律无关。比如，“aaa1”、“aaa2”、“aaa3”三个输入值比较类似，但经过优秀的哈希函数计算后得到的结果应该相差非常大。
哈希函数的经典实现
参考文献：哈希函数的介绍
比如使用MD5对“test”和“test1”两个字符串哈希的结果如下（哈希结果为128个bit，数据范围为0~(2^128)-1，通常转换为32个16进制数显示）：
test 098f6bcd4621d373cade4e832627b4f6
test1 5a105e8b9d40e1329780d62ea2265d8a
复制代码哈希表
百科：散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
哈希表的经典实现
哈希表初始会有一个大小，比如16，表中每个元素都可以通过数组下标（0~15）访问。每个元素可以看做一个桶，当要往表里放数据时，将要存放的数据的键值通过哈希函数计算出的哈希值模上16，结果正好对应0~15，将这条数据放入对应下标的桶中。
那么当数据量超过16时，势必会存在哈希冲突（两条数据经哈希计算后放入同一个桶中），这时的解决方案就是将后一条入桶的数据作为后继结点链入到桶中已有的数据之后，如此，每个桶中存放的就是一个链表。那么这就是哈希表的经典结构：
当数据量较少时，哈希表的增删改查操作的时间复杂度都是O(N)的。因为根据一个键值就能定位一个桶，即使存在哈希冲突（桶里不只一条数据），但只要哈希函数优秀，数据量几乎均分在每个桶上（这样很少有哈希冲突，即使有，一个桶里也只会有很少的几条数据），那就在遍历一下桶里的链表比较键值进一步定位数据即可（反正链表很短）。
哈希表扩容
如果哈希表大小为16，对于样本规模N（要存储的数据数量）来说，如果N较小，那么根据哈希函数的散列特性，每个桶会均分这N条数据，这样落到每个桶的数据量也较小，不会影响哈希表的存取效率（这是由桶的链表长度决定的，因为存数据要往链表尾追加首先就要遍历得到尾结点，取数据要遍历链表比较键值）；但如果N较大，那么每个桶里都有N/16条数据，存取效率就变成O(N)了。因此哈希表哈需要一个扩容机制，当表中某个桶的数据量超过一个阀值时（O(1)到O(N)的转变，这需要一个算法来权衡），需要将哈希表扩容（一般是成倍的）。
扩容步骤是，创建一个新的较大的哈希表（假如大小为m），将原哈希表中的数据取出，将键值的哈希值模上m，放入新表对应的桶中，这个过程也叫rehash。
如此的话，那么原来的O(N)就变成了O(log(m/16,N))，比如扩容成5倍那就是O(log(5,N))（以5为底，N的对数）。当这个底数较大的时候就会将N的对数压得非常低而和O(1)非常接近了，并且实际工程中基本是当成O(1)来用的。
你也许会说rehash很费时，会导致哈希表性能降低，这一点是可以侧面避免的。比如扩容时将倍数提高一些，那么rehash的次数就会很少，平衡到整个哈希表的使用来看，影响就甚微了。或者可以进行离线扩容，当需要扩容时，原哈希表还是供用户使用，在另外的内存中执行rehash，完成之后再将新表替换原表，这样的话对于用户来说，他是感觉不到rehash带来的麻烦的。
哈希表的JVM实现
在Java中，哈希表的实现是每个桶中放的是一棵红黑树而非链表，因为红黑树的查找效率很高，也是对哈希冲突带来的性能问题的一个优化。
布隆过滤器
不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64B。现在想要实现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计该系统。
要求如下：
- 该系统允许有万分之一以下的判断失误率。
- 使用的额外空间不要超过30GB。
如果将这100亿个URL通过数据库或哈希表保存起来，就可以对每条URL进行查询，但是每个URL有64B，数量是100亿个，所以至少需要640GB的空间，不满足要求2。
如果面试者遇到网页黑名单系统、垃圾邮件过滤系统，爬虫的网页判重系统等题目，又看到系统容忍一定程度的失误率，但是对空间要求比较严格，那么很可能是面试官希望面试者具备布隆过滤器的知识。一个布隆过滤器精确地代表一个集合，并可以精确判断一个元素是否在集合中。注意，只是精确代表和精确判断，到底有多精确呢？则完全在于你具体的设计，但想做到完全正确是不可能的。布隆过滤器的优势就在于使用很少的空间就可以将准确率做到很高的程度。该结构由
Burton Howard Bloom于1970年提出。
那么什么是布隆过滤器呢？
假设有一个长度为m的bit类型的数组，即数组的每个位置只占一个bit，如果我们所知，每一个bit只有0和1两种状态，如图所示：
再假设一共有k个哈希函数，这些函数的输出域S都大于或等于m，并且这些哈希函数都足够优秀且彼此之间相互独立（将一个哈希函数的计算结果乘以6除以7得出的新哈希函数和原函数就是相互独立的）。那么对同一个输入对象（假设是一个字符串，记为URL），经过k个哈希函数算出来的结果也是独立的。可能相同，也可能不同，但彼此独立。对算出来的每一个结果都对m取余（%m），然后在bit array 上把相应位置设置为1（我们形象的称为涂黑）。如图所示
我们把bit类型的数组记为bitMap。至此，一个输入对象对bitMap的影响过程就结束了，也就是bitMap的一些位置会被涂黑。接下来按照该方法，处理所有的输入对象（黑名单中的100亿个URL）。每个对象都可能把bitMap中的一些白位置涂黑，也可能遇到已经涂黑的位置，遇到已经涂黑的位置让其继续为黑即可。处理完所有的输入对象后，可能bitMap中已经有相当多的位置被涂黑。至此，一个布隆过滤器生成完毕，这个布隆过滤器代表之前所有输入对象组成的集合。
那么在检查阶段时，如何检查一个对象是否是之前的某一个输入对象呢（判断一个URL是否是黑名单中的URL）？假设一个对象为a，想检查它是否是之前的输入对象，就把a通过k个哈希函数算出k个值，然后把k个值都取余（%m），就得到在[0,m-1]范围伤的k个值。接下来在bitMap上看这些位置是不是都为黑。如果有一个不为黑，说明a一定不再这个集合里。如果都为黑，说明a在这个集合里，但可能误判。
再解释具体一点，如果a的确是输入对象 ，那么在生成布隆过滤器时，bitMap中相应的k个位置一定已经涂黑了，所以在检查阶段，a一定不会被漏过，这个不会产生误判。会产生误判的是，a明明不是输入对象，但如果在生成布隆过滤器的阶段因为输入对象过多，而bitMap过小，则会导致bitMap绝大多数的位置都已经变黑。那么在检查a时，可能a对应的k个位置都是黑的，从而错误地认为a是输入对象（即是黑名单中的URL）。通俗地说，布隆过滤器的失误类型是“宁可错杀三千，绝不放过一个”。
布隆过滤器到底该怎么生成呢？只需记住下列三个公式即可：
- 对于输入的数据量n（这里是100亿）和失误率p（这里是万分之一），布隆过滤器的大小m：
m = - (n*lnp)/(ln2*ln2)，计算结果向上取整（这道题m=19.19n，向上取整为20n，即需要2000亿个bit，也就是25GB） - 需要的哈希函数的个数k：
k = ln2 * m/n = 0.7 * m/n（这道题k = 0.7 * 20n/n = 14） - 由于前两步都进行了向上取整，那么由前两步确定的布隆过滤器的真正失误率p：
p = (1 - e^(-nk/m))^k
一致性哈希算法的基本原理
题目
工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略：
- 无论是添加、查询还是珊瑚数据，都先将数据的id通过哈希函数换成一个哈希值，记为key
- 如果目前机器有N台，则计算
key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。
请分析这种缓存策略可能带来的问题，并提出改进的方案。
解析
题目中描述的缓存从策略的潜在问题是，如果增加或删除机器时（N变化）代价会很高，所有的数据都不得不根据id重新计算一遍哈希值，并将哈希值对新的机器数进行取模啊哦做。然后进行大规模的数据迁移。
为了解决这些问题，下面介绍一下一致性哈希算法，这时一种很好的数据缓存设计方案。我们假设数据的id通过哈希函数转换成的哈希值范围是2^32，也就是0~(2^32)-1的数字空间中。现在我们可以将这些数字头尾相连，想象成一个闭合的环形，那么一个数据id在计算出哈希值之后认为对应到环中的一个位置上，如图所示
接下来想象有三台机器也处在这样一个环中，这三台机器在环中的位置根据机器id（主机名或者主机IP，是主机唯一的就行）设计算出的哈希值对2^32取模对应到环上。那么一条数据如何确定归属哪台机器呢？我们可以在该数据对应环上的位置顺时针寻找离该位置最近的机器，将数据归属于该机器上：
这样的话，如果删除machine2节点，则只需将machine2上的数据迁移到machine3上即可，而不必大动干戈迁移所有数据。当添加节点的时候，也只需将新增节点到逆时针方向新增节点前一个节点这之间的数据迁移给新增节点即可。
但这时还是存在如下两个问题：
-
机器较少时，通过机器id哈希将机器对应到环上之后，几个机器可能没有均分环
那么这样会导致负载不均。
-
增加机器时，可能会打破现有的平衡：
为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一台机器通过不同的哈希函数计算出多个哈希值，对多个位置都放置一个服务节点，称为虚拟节点。具体做法：比如对于machine1的IP192.168.25.132（或机器名），计算出192.168.25.132-1、192.168.25.132-2、192.168.25.132-3、192.168.25.132-4的哈希值，然后对应到环上，其他的机器也是如此，这样的话节点数就变多了，根据哈希函数的性质，平衡性自然会变好：
此时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，比如上图的查找表。当某一条数据计算出归属于m2-1时再根据查找表的跳转，数据将最终归属于实际的m1节点。
基于一致性哈希的原理有很多种具体的实现，包括Chord算法、KAD算法等，有兴趣的话可以进一步学习。
RandomPool
设计一种结构，在该结构中有如下三个功能：
- inserrt(key)：将某个key加入到该结构中，做到不重复加入。
- delete(key)：将原本在结构中的某个key移除。
- getRandom()：等概率随机返回结构中的任何一个key。
要求：insert、delete和getRandom方法的时间复杂度都是O(1)
思路：使用两个哈希表和一个变量
size，一个表存放某key的标号，另一个表根据根据标号取某个key。size用来记录结构中的数据量。加入key时，将size作为该key的标号加入到两表中；删除key时，将标号最大的key替换它并将size--；随机取key时，将size范围内的随机数作为标号取key。
import java.util.HashMap;
public class RandomPool {
public int size;
public HashMap<Object, Integer> keySignMap;
public HashMap<Integer, Object> signKeyMap;
public RandomPool() {
this.size = 0;
this.keySignMap = new HashMap<>();
this.signKeyMap = new HashMap<>();
}
public void insert(Object key) {
//不重复添加
if (keySignMap.containsKey(key)) {
return;
}
keySignMap.put(key, size);
signKeyMap.put(size, key);
size++;
}
public void delete(Object key) {
if (keySignMap.containsKey(key)) {
Object lastKey = signKeyMap.get(--size);
int deleteSign = keySignMap.get(key);
keySignMap.put(lastKey, deleteSign);
signKeyMap.put(deleteSign, lastKey);
keySignMap.remove(key);
signKeyMap.remove(lastKey);
}
}
public Object getRandom() {
if (size > 0) {
return signKeyMap.get((int) (Math.random() * size));
}
return null;
}
}
复制代码小技巧
对数器
概述
有时我们对编写的算法进行测试时，会采用自己编造几个简单数据进行测试。然而别人测试时可能会将大数量级的数据输入进而测试算法的准确性和健壮性，如果这时出错，面对庞大的数据量我们将无从查起（是在操作哪一个数据时出了错，算法没有如期起作用）。当然我们不可能对这样一个大数据进行断点调试，去一步一步的分析错误点在哪。这时 对数器 就粉墨登场了，对数器 就是通过随机制造出几乎所有可能的简短样本作为算法的输入样本对算法进行测试，这样大量不同的样本从大概率上保证了算法的准确性，当有样本测试未通过时又能打印该简短样本对错误原因进行分析。
对数器的使用
- 对于你想测试的算法
- 实现功能与该算法相同但绝对正确、复杂度不好的算法
- 准备大量随机的简短样本的
- 实现比对的方法：对于每一个样本，比对该算法和第二步中算法的执行结果以判断该算法的正确性
- 如果有一个样本比对出错则打印该样本
- 当样本数量很多时比对测试依然正确，可以确定算法a已经正确
对数器使用案例——对自写的插入排序进行测试：
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
//1.有一个自写的算法，但不知其健壮性（是否会有特殊情况使程序异常中断甚至崩溃）和正确性
void insertionSort(int arr[], int length){
if(arr==NULL || length<=1){
return;
}
for (int i = 1; i < length; ++i) {
for (int j = i - 1; j >= 0 || arr[j] <= arr[j + 1]; j--) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}
//2、实现一个功能相同、绝对正确但复杂度不好的算法（这里摘取大家熟知的冒泡排序）
void bubbleSort(int arr[], int length) {
for (int i = length-1; i > 0; i--) {
for (int j = 0; j < i; ++j) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}
//3、实现一个能够产生随机简短样本的方法
void generateSample(int arr[], int length){
for (int i = 0; i < length; ++i) {
arr[i] = rand() % 100-rand()%100;//控制元素在-100~100之间，考虑到零正负三种情况
}
}
//4、实现一个比对测试算法和正确算法运算结果的方法
bool isEqual(int arr1[],int arr2[],int length) {
if (arr1 != NULL && arr2 != NULL) {
for (int i = 0; i < length; ++i) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
return false;
}
void travels(int arr[], int length){
for (int i = 0; i < length; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
void copy(int source[], int target[],int length){
for (int i = 0; i < length; ++i) {
target[i] = source[i];
}
}
int main(){
srand(time(NULL));
int testTimes=10000;
//循环产生100000个样本进行测试
for (int i = 0; i < testTimes; ++i) {
int length = rand() % 10; //控制每个样本的长度在10以内，便于出错时分析样本（因为简短）
int arr[length];
generateSample(arr, length);
//不要改变原始样本，在复制样本上改动
int arr1[length], arr2[length];
copy(arr, arr1, length);
copy(arr, arr2, length);
bubbleSort(arr1,length);
insertionSort(arr2, length);
// travels(arr, length);
// travels(arr1, length);
//5、比对两个算法，只要有一个样本没通过就终止，并打印原始样本
if (!isEqual(arr1, arr2, length)) {
printf("test fail!the sample is: ");
travels(arr, length);
return 0;
}
}
//6、测试全部通过，该算法大概率上正确
printf("nice!");
return 0;
}
复制代码打印二叉树
有时我们不确定二叉树中是否有指针连空了或者连错了，这时需要将二叉树具有层次感地打印出来，下面就提供了这样一个工具。你可以将你的头逆时针旋转90度看打印结果。v表示该结点的头结点是左下方距离该结点最近的一个结点，^表示该结点的头结点是左上方距离该结点最近的一个结点。
package top.zhenganwen.algorithmdemo.recursive;
public class PrintBinaryTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(-222222222);
head.right = new Node(3);
head.left.left = new Node(Integer.MIN_VALUE);
head.right.left = new Node(55555555);
head.right.right = new Node(66);
head.left.left.right = new Node(777);
printTree(head);
head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.right.left = new Node(5);
head.right.right = new Node(6);
head.left.left.right = new Node(7);
printTree(head);
head = new Node(1);
head.left = new Node(1);
head.right = new Node(1);
head.left.left = new Node(1);
head.right.left = new Node(1);
head.right.right = new Node(1);
head.left.left.right = new Node(1);
printTree(head);
}
}
复制代码递归的实质和Master公式
递归的实质
递归的实质就是系统在帮我们压栈。首先让我们来看一个递归求阶乘的例子：
int fun(int n){
if(n==0){
return 1;
}
return n*fun(n-1);
}
复制代码课上老师一般告诉我们递归就是函数自己调用自己。但这听起来很玄学。事实上，在函数执行过程中如果调用了其他函数，那么当前函数的执行状态（执行到了第几行，有几个变量，各个变量的值是什么等等）会被保存起来压进栈（先进后出的存储结构，一般称为函数调用栈）中，转而执行子过程（调用的其他函数，当然也可以是当前函数）。若子过程中又调用了函数，那么调用前子过程的执行状态也会被保存起来压进栈中，转而执行子过程的子过程……以此类推，直到有一个子过程没有调用函数、能顺序执行完毕时会从函数调用栈依次弹出栈顶被保存起来的未执行完的函数（恢复现场）继续执行，直到函数调用栈中的函数都执行完毕，整个递归过程结束。
例如，在main中执行fun(3)，其递归过程如下：
int main(){
int i = fun(3);
printf("%d",i);
return 0;
}
复制代码
很多时候我们分析递归时都喜欢在心中模拟代码执行，去追溯、还原整个递归调用过程。但事实上没有必要这样做，因为每相邻的两个步骤执行的逻辑都是相同的，因此我们只需要分析第一步到第二步是如何执行的以及递归的终点在哪里就可以了。
一切的递归算法都可以转化为非递归，因为我们完全可以自己压栈。只是说递归的写法更加简洁。在实际工程中，递归的使用是极少的，因为递归创建子函数的开销很大并且存在安全问题（stack overflow）。
Master公式
包含递归的算法的时间复杂度有时很难通过算法表面分析出来， 比如 归并排序。这时Master公式就粉墨登场了，当某递归算法的时间复杂度符合T(n)=aT(n/b)+O(n^d)形式时可以直接求出该算法的直接复杂度：
- 当（以b为底a的对数）
log(b,a) > d时，时间复杂度为O(n^log(b,a)) - 当
log(b,a) = d时，时间复杂度为O(n^d * logn) - 当
log(b,a) < d时，时间复杂度为O(n^d)
其中，
n为样本规模，n/b为子过程的样本规模（暗含子过程的样本规模必须相同，且相加之和等于总样本规模），a为子过程的执行次数，O(n^d)为除子过程之后的操作的时间复杂度。以归并排序为例，函数本体先对左右两半部分进行归并排序，样本规模被分为了左右各
n/2即b=2，左右各归并排序了一次，子过程执行次数为2即a=2，并入操作的时间复杂度为O(n+n)=O(n)即d=1，因此T(n)=2T(n/2)+O(n)，符合log(b,a)=d=1，因此归并排序的时间复杂度为O(n^1*logn)=O(nlogn)
京公网安备 11010502036488号