# algorithm-practice **Repository Path**: freedyamazing/algorithm-practice ## Basic Information - **Project Name**: algorithm-practice - **Description**: 复习数据结构与算法时写的代码 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 0 - **Created**: 2021-04-14 - **Last Updated**: 2022-06-20 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 稀疏数组 1. 稀疏数组就是将普通的二维数组转化为另一种二位数组,以压缩原有数组。 2. 其主要的作用是压缩原本的二维数组 3. 前提是原本的二维数组有很多无用数据,不然这种转换毫无意义 ![img](http://39.108.121.236:2333/upload/2021/03/image-000ff5dfc0ef4a27a3a35db9c04ebd54.png) ## 稀疏数组处理方法 - 稀疏数组把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模 - 稀疏数组也是二维数组，行数由原数组的数据决定，列数一般为 3 列 - 稀疏数组的第一行记录原数组一共有几行几列，有多少个不为零的值 - 第一列：原数组的行数 - 第二列：原数组的列数 - 第三列：原数组有多少个不为零的值 - 之后的行记录原数组中不为零（x）的值所在的行数、列数以及 x 的值 - 第一列：x 在原数组中的行数 - 第二列：x 在原数组中的列数 - 第三列：x 的值 ## 代码实现 ```java package com.freedy; /** * @author Freedy * @date 2021/3/14 11:05 */ public class SparseArr { public static void main(String[] args) { int[][] origin=new int[11][11]; origin[1][4]=1; origin[3][3]=2; System.out.println("===========原始数据==========="); printArr(origin); int[][] sparseArr = normalArrToSparseArr(origin); System.out.println("===========稀疏数组==========="); printArr(sparseArr); int[][] normalArr = sparseArrToNormalArr(sparseArr); System.out.println("===========转化回来的普通数组==========="); printArr(normalArr); } /** * 将稀疏数组转化为普通数组 */ public static int[][] sparseArrToNormalArr(int[][] sparseArr){ int[][] arr=new int[sparseArr[0][0]][sparseArr[0][1]]; for (int i = 1; i < sparseArr[0][2]+1; i++) { arr[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2]; } return arr; } /** * 将普通数组转稀疏数组 */ public static int[][] normalArrToSparseArr(int[][] origin){ //统计非零数据的个数，方便之后创建稀疏数组 int sum=0; //先遍历二维数组得到非0的数据 for (int i = 0; i < origin.length; i++) { for (int j = 0; j < origin[0].length; j++) { if (origin[i][j]!=0){ sum++; } } } int[][] sparseArr=new int[sum+1][3]; //对稀疏数组赋初始值 sparseArr[0][0]=origin.length; sparseArr[0][1]=origin[0].length; sparseArr[0][2]=sum; //对稀疏数组赋数据值 int row=1; for (int i = 0; i < origin.length; i++) { for (int j = 0; j < origin[0].length; j++) { if (origin[i][j]!=0){ sparseArr[row][0]=i; sparseArr[row][1]=j; sparseArr[row][2]=origin[i][j]; row++; } } } return sparseArr; } /** * 打印二维数组 * @param a */ public static void printArr(int[][] a){ for (int[] ints : a) { for (int anInt : ints) { System.out.printf("%d\t",anInt); } System.out.println(); } } } ``` ## 输出结果 ``` ===========原始数据=========== 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ===========稀疏数组=========== 11 11 2 1 4 1 3 3 2 ===========转化回来的普通数组=========== 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ``` # 队列 ## 队列介绍 1. 队列是一个有序列表，可以用数组或是链表来实现。 2. 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出 3. 示意图：(使用数组模拟队列示意图) ![image.png](http://39.108.121.236:2333/upload/2021/03/image-71ca6c2ef3454b0f9a59a819499c23e6.png) ## 实现思路 1. front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值=0 2. rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定.rear的初始值=0(如果这里不预留一个位置,则不能判断队列的满与空.因为这是他们的判定条件是一样的.) 3. 当队列满时，条件是(rear +1) % maxSize = front【满】 4. 对队列为空的条件，rear = front空 5. 当我们这样分析，队列中有效的数据的个数(rear + maxSize - front)% maxSize ## 数组环形队列代码实现 ```java package com.freedy.dataStructure.queue; /** * @author Freedy * @date 2021/3/14 12:46 */ public class ArrQueue { public static void main(String[] args) { //测试 CircleQueue queue = new CircleQueue(3); queue.addQueue(1); queue.addQueue(2); queue.addQueue(3); queue.popQueue(); queue.popQueue(); queue.addQueue(41); queue.addQueue(51); queue.popQueue(); queue.addQueue(51); System.out.println(queue.peek()); System.out.println(queue.size()); } } /** * 使用数组模拟队列 * 队列类 */ class CircleQueue{ private int maxSize;//表示数组最大容量 private int front;//指向队列头部的前一个位置 private int rear;//指向队列尾具体位置 private int[] arr;//该数组用于存放数据 //构造队列 public CircleQueue(int maxSize){ this.maxSize=maxSize+1; arr=new int[this.maxSize]; front=0; rear=0; } //判断队列是否满 public boolean isFull(){ return (rear+1)%maxSize==front; } //判断队列是否为空 public boolean isEmpty(){ return rear==front; } //添加数据到队列 public void addQueue(int n){ if (isFull()){ throw new RuntimeException("队列已满,不能加入数据！"); } arr[rear]=n; rear=(rear+1)%maxSize;//rear后移 } //取数据 public int popQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空！"); } int ret=arr[front]; front=(front+1)%maxSize; return ret; } public void showQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空！"); } for (int i = 0; i < size(); i++) { System.out.print(arr[(front+i)%maxSize]); } } //显示队列的头（不取数据） public int peek(){ if (isEmpty()){ throw new RuntimeException("队列为空！"); } return arr[front]; } //求队列长度 public int size(){ return (rear + maxSize - front)% maxSize; } } ``` # 链表(Linked List) ## 单链表介绍 链表是有序的列表，但是它在内存中是存储如下 ![image.png](http://39.108.121.236:2333/upload/2021/03/image-695edb4b09244b6caabd45fcf57442d6.png) 1. 链表是以节点的方式来存储,是链式存储 2. 每个节点包含 data 域， next 域：指向下一个节点. 3. 如图：发现链表的各个节点不一定是连续存储. 4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定 ## 链表相关操作思路 ### 添加（创建) 1. 先创建一个head头节点，作用就是表示单链表的头 2. 后面我们每添加一个节点，就直接加入到链表的最后遍历: ### 遍历: 1. 通过一个辅助变量遍历，帮助遍历整个链表 ## 单链表代码实现 ```java package com.freedy.dataStructure.linkedList; import java.util.Comparator; /** * @author Freedy * @date 2021/3/14 14:16 */ public class SingleLinkedList { //先初始化头节点,头节点不能变动 private final Node head; SingleLinkedList() { head = new Node<>(); } public void add(T data) { Node node = new Node<>(); node.setData(data); addNode(node); } /** * 带索引的添加 相当于插入 * @param index * @param data */ public void add(int index, T data) { Node node = new Node<>(); node.setData(data); setNode(index, node); } public T get(int index) { Node node = getNode(index); return node.getData(); } /** * @param index 索引 */ public void remove(int index) { //获取前置节点 Node pre = getNode(index - 1); Node node = getNode(index); pre.setNext(node.getNext()); } public void revers(){ if (size()==0) throw new RuntimeException("链表为空"); Node preNode = head.getNext(); Node node = preNode.getNext(); preNode.setNext(null); while (node!=null){ Node temp = node.getNext(); node.setNext(preNode); preNode=node; node=temp; } head.setNext(preNode); } /** * @return 链表大小 */ public int size() { int size = 0; Node temp = head.getNext(); while (temp != null) { size++; temp = temp.getNext(); } return size; } /** * 冒泡法排序 * @param c */ @SuppressWarnings("unchecked") public void sort(Comparator c) { Node node = head.getNext(); Object[] sort=new Object[size()]; int num=0; while (node!=null){ sort[num]=node.getData(); node=node.getNext(); num++; } for (int i = sort.length-1; i > 0; i--) { for (int j = 0; j < i; j++) { if (c.compare((T)sort[j],(T)sort[j+1])>0){ Object temp; temp=sort[j]; sort[j]=sort[j+1]; sort[j+1]=temp; } } } head.setNext(null); for (Object o : sort) { add((T) o); } } /** * ==================private==================== * 链表添加值 * * @param node */ private void addNode(Node node) { getNode(size() - 1).setNext(node); } /** * 给链表设置值 * * @param index 索引 * @param node 节点 */ private void setNode(int index, Node node) { Node temp = getNode(index - 1); //这里拿到的temp是index的前一个节点 Node mark; mark = temp.getNext(); temp.setNext(node); node.setNext(mark); } /** * 获取链表 * index为-1时获取的是头head * * @param index 索引 * @return 节点 */ private Node getNode(int index) { int count = -1; Node temp = head; boolean isOver = true; while (temp != null) { if (index == count) { isOver = false; break; } count++; temp = temp.getNext(); } if (isOver) { throw new RuntimeException("链表超界 数组大小:"+size()+" index:"+index); } return temp; } /** * 遍历整个列表 */ @Override public String toString() { if (head.getNext() == null) { return "[]"; } Node temp = head.getNext(); StringBuilder stringBuffer = new StringBuilder(); stringBuffer.append("["); while (temp != null) { stringBuffer.append(temp.getData().toString()).append(","); temp = temp.getNext(); //将temp后移 } stringBuffer.deleteCharAt(stringBuffer.length() - 1); stringBuffer.append("]"); return stringBuffer.toString(); } /** * 定义一个node类 * * @param */ private static class Node { private T data; private Node next; private T getData() { return data; } private void setData(T data) { this.data = data; } private Node getNext() { return next; } private void setNext(Node next) { this.next = next; } } } ``` 测试 ``` package com.freedy.dataStructure.linkedList; import java.util.Comparator; import java.util.LinkedList; /** * @author Freedy * @date 2021/3/14 19:58 */ public class Test { public static void main(String[] args) { SingleLinkedList list = new SingleLinkedList<>(); //LinkedList list = new LinkedList<>(); list.add(13123125); list.add(11); list.add(12); list.add(0,100); list.add(0,1030); list.add(0,1600); list.add(0,1080); list.add(1,9999); list.remove(4); list.add(9999999); System.out.println(list); list.sort(new Comparator() { @Override public int compare(Integer o1, Integer o2) { return o1-o2; } }); System.out.println(list); list.remove(0); list.remove(0); list.remove(0); list.remove(0); list.remove(0); list.remove(0); list.remove(0); list.remove(0); list.remove(0); System.out.println(list); } } ``` ## 结果输出 SingleLinkedList输出结果 ``` [1080,9999,1600,1030,13123125,11,12,9999999] [11,12,1030,1080,1600,9999,9999999,13123125] Exception in thread "main" java.lang.RuntimeException: index超界 at com.freedy.dataStructure.linkedList.SingleLinkedList.getNode(SingleLinkedList.java:134) at com.freedy.dataStructure.linkedList.SingleLinkedList.remove(SingleLinkedList.java:42) at com.freedy.dataStructure.linkedList.Test.main(Test.java:43) ``` JDK LinkedList输出结果 ``` [1080, 9999, 1600, 1030, 13123125, 11, 12, 9999999] [11, 12, 1030, 1080, 1600, 9999, 9999999, 13123125] Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0 at java.base/java.util.LinkedList.checkElementIndex(LinkedList.java:559) at java.base/java.util.LinkedList.remove(LinkedList.java:529) at com.freedy.dataStructure.linkedList.Test.main(Test.java:42) ``` ## 双向链表介绍 - 所谓的双向链表就是每个节点不止指向它的后节点，还指向它的前节点 ## 双向链表的遍历、增加、修改、删除的操作思路 1. 遍历方和单链表一样,只是可以向前，也可以向后查找 2. 添加(默认添加到双向链表的最后) - 先找到双向链表的最后这个节点 - temp.next =newHeroNode - newHeroNode.pre =temp; 3. 修改思路和单项链表一样 4. 因为是双向链表、因此我们可以实现自我删除某个节点 - 因为是双向链表，因此，我们可以实现自我删除某个节点 - 直接找到要删除的这个节点，比如temp - temp.pre.next =temp.next - temp.next.pre=temp.pre - 被删除的节点会被jvm进行垃圾回收 ## 代码实现 ```java package com.freedy.dataStructure.linkedList; import java.util.Comparator; /** * 双链表的实现 * @author Freedy * @date 2021/3/14 14:16 */ public class DoubleLinkedList { //先初始化头节点,头节点不能变动 private final Node head; private Integer size=0; DoubleLinkedList() { head = new Node<>(); } public Node getHead() { return head; } public void add(T data) { Node node = new Node<>(); node.setData(data); addNode(node); } /** * 带索引的添加 相当于插入 * @param index * @param data */ public void add(int index, T data) { Node node = new Node<>(); node.setData(data); setNode(index, node); } public T get(int index) { Node node = getNode(index); return node.getData(); } /** * @param index 索引 */ public void remove(int index) { //获取前置节点 Node node = getNode(index); node.getPre().setNext(node.getNext()); if (node.getNext()!=null){ node.getNext().setPre(node.getPre()); } size--; } /** * @return 链表大小 */ public int size() { return size; } /** * 冒泡法排序 * @param c */ @SuppressWarnings("unchecked") public void sort(Comparator c) { Node node = head.getNext(); Object[] sort=new Object[size()]; int num=0; while (node!=null){ sort[num]=node.getData(); node=node.getNext(); num++; } for (int i = sort.length-1; i > 0; i--) { for (int j = 0; j < i; j++) { if (c.compare((T)sort[j],(T)sort[j+1])>0){ Object temp; temp=sort[j]; sort[j]=sort[j+1]; sort[j+1]=temp; } } } head.setNext(null); for (Object o : sort) { add((T) o); } } /** * ==================private==================== * 链表添加值 * * @param node */ private void addNode(Node node) { Node lastNode = getNode(size() - 1); lastNode.setNext(node); node.setPre(lastNode); size++; } /** * 给链表设置值 * * @param index 索引 * @param node 节点 */ private void setNode(int index, Node node) { //这里拿到的pre是index的前一个节点 Node pre = getNode(index - 1); Node next = pre.getNext(); pre.setNext(node); node.setPre(pre); node.setNext(next); next.setPre(node); size++; } /** * 获取链表 * index为-1时获取的是头head * * @param index 索引 * @return 节点 */ private Node getNode(int index) { if (index>size-1) { throw new RuntimeException("链表超界 数组大小:"+size()+" index:"+index); } int count = -1; Node temp = head; while (temp != null) { if (index == count) { break; } count++; temp = temp.getNext(); } return temp; } /** * 遍历整个列表 */ @Override public String toString() { if (head.getNext() == null) { return "[]"; } Node temp = head.getNext(); StringBuilder stringBuffer = new StringBuilder(); stringBuffer.append("["); while (temp != null) { stringBuffer.append(temp.getData().toString()).append(","); temp = temp.getNext(); //将temp后移 } stringBuffer.deleteCharAt(stringBuffer.length() - 1); stringBuffer.append("]"); return stringBuffer.toString(); } /** * 定义一个node类 * * @param */ private static class Node { private T data; private Node next; private Node pre; public Node getPre() { return pre; } public void setPre(Node pre) { this.pre = pre; } private T getData() { return data; } private void setData(T data) { this.data = data; } private Node getNext() { return next; } private void setNext(Node next) { this.next = next; } } } ``` # 栈 ## 栈的实现 ### 介绍 1. 栈的英文为(stack) 2. 栈是一个先入后出(FILO-First In Last Out)的有序列表。 3. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一 种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另中一端为固定的一端，称为栈底(Bottom)。 4. 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而 删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除 5. 出栈和入栈的概念（如图） ![image.png](http://39.108.121.236:2333/upload/2021/03/image-60f92995eb1d417c9f6d728a9b16fdb7.png) ### 实现思路 1. 使用数组来模拟栈 2. 定义一个top 来表示栈顶，初始化为-1 3. 入栈的操作,当有数据加入到栈时，top++; stack[top]= data; 4. 出栈的操作，top--; return stack[top+1]; ### 代码实现 ```java package com.freedy.dataStructure.stack; /** * @author Freedy * @date 2021/3/16 16:34 */ public class ArrStack { private final int maxSize;//栈的大小 private final int[] stack;//数组模拟栈 private int top=-1;//表示栈顶 public ArrStack(int maxSize){ this.maxSize=maxSize; stack=new int[this.maxSize]; } /** * 判断栈是否为满 * @return */ public boolean isFull(){ return top==maxSize-1; } /** * 判断栈是否为空 * @return */ public boolean isEmpty(){ return top==-1; } /** * 入栈 * @param val */ public void push(int val){ if (isFull()) throw new RuntimeException("栈满"); top++; stack[top]=val; } /** * 出栈 * @return */ public int pop(){ if (isEmpty()) throw new RuntimeException("栈空"); top--; return stack[top+1]; } /** * 栈的遍历 */ public void list(){ if (isEmpty()) throw new RuntimeException("栈空"); for (int i = top; i >=0; i--) { System.out.printf("stack[%d]=%d\n",i,stack[i]); } } } ``` ### 测试结果 测试代码 ```java package com.freedy; import com.freedy.dataStructure.stack.ArrStack; import java.util.*; /** * @author Freedy * @date 2021/3/11 14:11 */ public class Test { public static void main(String[] args) { ArrStack stack = new ArrStack(5); System.out.println(stack.isEmpty()); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.isFull()); stack.list(); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); stack.list(); } } ``` 输出 ```java true true stack[4]=5 stack[3]=4 stack[2]=3 stack[1]=2 stack[0]=1 5 4 3 2 1 Exception in thread "main" java.lang.RuntimeException: 栈空 at com.freedy.dataStructure.stack.ArrStack.list(ArrStack.java:57) at com.freedy.Test.main(Test.java:27) 进程已结束，退出代码为 1 ``` ## 栈的应用-实现综合计算器(中缀表达式实现) ### 实现思路 1. 首先创建两个栈,一个数栈(numStack),一个符号栈(operationStack) 2. 通过一个index 值（索引），来遍历我们的表达式 3. 如果我们发现是一个数字,就直接入数栈 4. 如果发现扫描到是一个符号,就分如下情况 1. 如果发现当前的符号栈为空，就直接入栈 2. 如果符号栈有操作符，就进行比较。 3. 如果当前的操作符的**优先级小于或者等于**楫的操作符，就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈 4. 如果当前的操作符的**优先级大于**栈中的操作符,就直接入符号栈. 5. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行. 6. 最后在数栈只有一个数字,就是表达式的结果 ![image.png](http://39.108.121.236:2333/upload/2021/03/image-85cae99450704d7f89c414a6891826ab.png) ### 代码实现 这里将ArrStack改为泛型,因为我们实现计算器的时候要创建两个数据类型不一样的栈 ```java package com.freedy.dataStructure.stack; /** * @author Freedy * @date 2021/3/16 16:34 */ public class ArrStack { private final int maxSize;//栈的大小 private final T[] stack;//数组模拟栈 private int top=-1;//表示栈顶 public int size(){ return top+1; } public ArrStack(int maxSize){ this.maxSize=maxSize; stack=(T[])new Object[this.maxSize]; } /** * 判断栈是否为满 * @return */ public boolean isFull(){ return top==maxSize-1; } /** * 判断栈是否为空 * @return */ public boolean isEmpty(){ return top==-1; } /** * 入栈 * @param val */ public void push(T val){ if (isFull()) throw new RuntimeException("栈满"); top++; stack[top]=val; } /** * 出栈 * @return */ public T pop(){ if (isEmpty()) throw new RuntimeException("栈空"); top--; return stack[top+1]; } /** * 栈的遍历 */ public void list(){ if (isEmpty()) throw new RuntimeException("栈空"); for (int i = top; i >=0; i--) { System.out.printf("stack[%d]=%d\n",i,stack[i]); } } public T peak(){ return stack[top]; } } ``` 计算器实现代码 ```java package com.freedy.dataStructure.stack; /** * @author Freedy * @date 2021/3/16 18:24 */ public class Calculator { public Double calculate(String expression) { ArrStack numStack=new ArrStack<>(10); ArrStack opsStack=new ArrStack<>(10); double num1=0; double num2=0; char ops=0; double res=0; char ch=' ';//将每次扫描得到的char保存到ch StringBuilder builder=new StringBuilder(); for (int index = 0; index < expression.length(); index++) { ch=expression.charAt(index); if (isOps(ch)){ //检测到是运算符就将前面的数字放入数字栈(numStack)中 numStack.push( Double.parseDouble(builder.toString())); builder=new StringBuilder(); if (!opsStack.isEmpty()&&priority(ch)<=priority(opsStack.peak())){ num1=numStack.pop(); num2=numStack.pop(); ops=opsStack.pop(); res=cal(num1,num2,ops); //把运算结果加入数栈 numStack.push(res); opsStack.push(ch); }else { opsStack.push(ch); } }else { builder.append(ch); } } //将最后一个数推入栈 numStack.push( Double.parseDouble(builder.toString())); //当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行 while (!opsStack.isEmpty()){ num1=numStack.pop(); num2=numStack.pop(); ops=opsStack.pop(); res=cal(num1,num2,ops); //把运算结果加入数栈 numStack.push(res); } return numStack.pop(); } /** * 判断运算符的优先级,优先级用数字来表示 * 数字越大优先级越高 * @param ops * @return */ private int priority(char ops) { //int和char可以相互转换，char的底层也是数字 if (ops == '*' || ops == '/') { return 1; } else if (ops == '+' || ops == '-') { return 0; } else { return -1; } } /** * 判断是不是一个运算符 * @param val * @return */ private boolean isOps(char val){ return val=='+'||val=='-'||val=='*'||val=='/'; } private double cal(double num1,double num2,int ops){ double res = 0;//存放计算结果 switch (ops){ case '+': res=num1+num2; break; case '-': res=num2-num1; break; case '*': res=num1*num2; break; case '/': res=num2/num1; break; default: break; } return res; } } ``` ### 测试 由于没有实现括号功能,就做简单测试 ```java package com.freedy; import com.freedy.dataStructure.stack.Calculator; /** * @author Freedy * @date 2021/3/11 14:11 */ public class Test { public static void main(String[] args) { Calculator calculator = new Calculator(); Double aDouble = calculator.calculate("1+2*3-5"); System.out.println(aDouble); } } ``` 测试结果 ```java 2.0 进程已结束，退出代码为 0 ``` ## 前缀表达式(波兰表达式) 1. 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前 2. 举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 #### 前缀表达式的计算机求值 - 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素)，并将结果入栈;重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果 - 例如: (3+4)×5-6对应的前缀表达式就是-×+3456,针对前缀表达式求值步骤如下: 1. 从右至左扫描，将6、5、4、3压入堆栈 2. 遇到+运算符，因此弹出3和4(3为栈顶元素，4为次顶元素)，计算出3+4的值，得7,再将7入栈 3. 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈 4. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果 ## 中缀表达式 1. 中缀表达式就是常见的运算表达式，如(3+4)×5-6 2. 中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.) ## 后缀表达式 1. 后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后 2. 举例 ![image.png](http://39.108.121.236:2333/upload/2021/03/image-0e185526b0de48b799959630878bf012.png) #### 后缀表达式的计算机求值 - 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果 - 例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下: 1. 从左至右扫描，将3和4压入堆栈； 2. 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈； 3. 将5入栈； 4. 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 5. 将6入栈； 6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果 ## 逆波兰计算器（后缀表达式） 其思路如上 #### 代码实现 ArrStack类的实现和中缀表达式计算器的一样，其输入是后缀表达式. ```java package com.freedy.dataStructure.stack; /** * @author Freedy * @date 2021/3/16 20:21 */ public class PolandNotation { public Double calculate(String suffixExpression){ ArrStack stack = new ArrStack(30); StringBuilder builder = new StringBuilder(); for (int i = suffixExpression.length()-1; i >=0; i--) { char ch = suffixExpression.charAt(i); if (isOps(ch)){ stack.push(String.valueOf(ch)); }else if (suffixExpression.charAt(i)!=' '){ builder.append(suffixExpression.charAt(i)); }else if (suffixExpression.charAt(i)==' '&&builder.length()>0){ builder.reverse();//应为是反着遍历所以要颠倒一下数字 stack.push(builder.toString()); builder=new StringBuilder();//清空builder } } //将最后的数字push到栈中 builder.reverse(); stack.push(builder.toString()); ArrStack numStack = new ArrStack(30); try { while (stack.size()>0){ String pop = stack.pop(); if (!isOps(pop.charAt(0))){ numStack.push(Double.parseDouble(pop)); }else { Double num1 = numStack.pop(); Double num2 = numStack.pop(); double res = cal(num1,num2, pop.charAt(0)); numStack.push(res); } } } catch (Exception e) { e.printStackTrace(); throw new RuntimeException("表达式不正确"); } return numStack.pop(); } private boolean isOps(char val){ return val=='+'||val=='-'||val=='*'||val=='/'; } private double cal(double num1,double num2,int ops){ double res = 0;//存放计算结果 switch (ops){ case '+': res=num1+num2; break; case '-': res=num2-num1; break; case '*': res=num1*num2; break; case '/': res=num2/num1; break; default: throw new RuntimeException("计算错误"); } return res; } } ``` #### 测试 ```java package com.freedy; import com.freedy.dataStructure.stack.PolandNotation; /** * @author Freedy * @date 2021/3/11 14:11 */ public class Test { public static void main(String[] args) { PolandNotation calculator = new PolandNotation(); //对应的中缀表达式4+(2+3)*5-8/2 Double aDouble = calculator.calculate("4 2 3 + 5 * + 8 2 / -"); System.out.println(aDouble); } } ``` 输出 ```java 25.0 进程已结束，退出代码为 0 ``` ## 中缀表达式转后缀表达式 #### 具体步骤 1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2； 2. 从左至右扫描中缀表达式； 3. 遇到操作数时，将其压s2； 4. 遇到运算符时，比较其与s1栈顶运算符的优先级： - 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈； - 否则，若优先级比栈顶运算符的高，也将运算符压入s1； - 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较； 5. 遇到括号时： - 如果是左括号“(”，则直接压入s1 - 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 6. 重复步骤2至5，直到表达式的最右边 7. 将s1中剩余的运算符依次弹出并压入s2 8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式 #### 代码实现 后缀表达式计算器和中缀转后缀的实现 ArrStack类同上 ```java package com.freedy.dataStructure.stack; /** * 中缀转后缀 * 逆波兰计算器 * @author Freedy * @date 2021/3/16 20:21 */ public class PolandNotation { public Double calculate(String suffixExpression) { ArrStack stack = new ArrStack(30); StringBuilder builder = new StringBuilder(); for (int i = suffixExpression.length() - 1; i >= 0; i--) { char ch = suffixExpression.charAt(i); if (isOps(ch)) { stack.push(String.valueOf(ch)); } else if (suffixExpression.charAt(i) != ' ') { builder.append(suffixExpression.charAt(i)); } else if (suffixExpression.charAt(i) == ' ' && builder.length() > 0) { builder.reverse();//应为是反着遍历所以要颠倒一下数字 stack.push(builder.toString()); builder = new StringBuilder();//清空builder } } //将最后的数字push到栈中 builder.reverse(); stack.push(builder.toString()); ArrStack numStack = new ArrStack(30); try { while (stack.size() > 0) { String pop = stack.pop(); if (!isOps(pop.charAt(0))) { numStack.push(Double.parseDouble(pop)); } else { Double num1 = numStack.pop(); Double num2 = numStack.pop(); double res = cal(num1, num2, pop.charAt(0)); numStack.push(res); } } } catch (Exception e) { e.printStackTrace(); throw new RuntimeException("表达式不正确"); } return numStack.pop(); } /** * 将中缀表达式转化为后缀表达式 * * @param infixExpression * @return */ public String infixExpressionToSuffixExpression(String infixExpression) { StringBuilder temp = new StringBuilder(); ArrStack s1 = new ArrStack(infixExpression.length()); ArrStack s2 = new ArrStack(infixExpression.length()); //扫描字符串 for (int i = 0; i < infixExpression.length(); i++) { char charAt = infixExpression.charAt(i); if (isOps(charAt)) { if (!temp.isEmpty()) { s2.push(temp.toString()); temp = new StringBuilder(); } while (true) { if (s1.isEmpty() || priority(charAt) > priority(s1.peak()) || charAt == '(') { s1.push(charAt); break; } else if (charAt == ')') { while (s1.peak() != '(') { s2.push(String.valueOf(s1.pop())); } s1.pop(); break; } else { s2.push(String.valueOf(s1.pop())); } } } else { temp.append(charAt); } } //将最后一个元素推入 s2.push(String.valueOf(temp)); //将s1中剩余的元素推入s2中 while (!s1.isEmpty()) { s2.push(String.valueOf(s1.pop())); } //反向输出s2 构建后缀表达式 StringBuilder suffixExpression = new StringBuilder(); while (!s2.isEmpty()) { suffixExpression.insert(0,s2.pop()+" "); } return suffixExpression.toString().strip(); } private boolean isOps(char val) { return val == '+' || val == '-' || val == '*' || val == '/' || val == '(' || val == ')'; } private double cal(double num1, double num2, int ops) { double res = 0;//存放计算结果 switch (ops) { case '+': res = num1 + num2; break; case '-': res = num2 - num1; break; case '*': res = num1 * num2; break; case '/': res = num2 / num1; break; default: throw new RuntimeException("计算错误"); } return res; } /** * 判断运算符的优先级,优先级用数字来表示 * 数字越大优先级越高 * * @param ops * @return */ private int priority(char ops) { //int和char可以相互转换，char的底层也是数字 if (ops == '*' || ops == '/') { return 2; } else if (ops == '+' || ops == '-') { return 1; } else if (ops == '(' || ops == ')') { return 0; } else { return -1; } } } ``` #### 测试 ```java package com.freedy; import com.freedy.dataStructure.stack.PolandNotation; /** * @author Freedy * @date 2021/3/11 14:11 */ public class Test { public static void main(String[] args) { PolandNotation calculator = new PolandNotation(); String suffixExpression = calculator.infixExpressionToSuffixExpression("4+(2+3)*5-8/2"); Double aDouble = calculator.calculate(suffixExpression); System.out.println("4+(2+3)*5-8/2的后缀表达式为:"+suffixExpression); System.out.println("4+(2+3)*5-8/2通过后缀表达式计算出的结果为:"+aDouble); } } ``` 输出结果 ```java 4+(2+3)*5-8/2的后缀表达式为:4 2 3 + 5 * + 8 2 / - 4+(2+3)*5-8/2通过后缀表达式计算出的结果为:25.0 进程已结束，退出代码为 0 ``` # 递归 ## 介绍 简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。 ## 递归需要遵守的重要规则 1. 执行一个方法时，就创建一个新的受保护的独立空间(栈空间) 2. 方法的局部变量是独立的，不会相互影响, 比如n变量 3. 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据. 4. 递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了:) 5. 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。 ## 迷宫回溯问题 说明: 求小球起点到终点的路径 ### 代码实现 ```java package com.freedy.dataStructure.recursion; /** * @author Freedy * @date 2021/3/18 12:35 */ public class Maze { public static void main(String[] args) { int[][] map = mapMaker(); if (setWay(map,1,1,6,5)){ System.out.println("找到路径"); printMap(map); }else { System.out.println("没找到路径"); } } /** * 构建迷宫 * 1代表墙 */ public static int[][] mapMaker(){ int[][] map=new int[8][7]; for (int i = 0; i < 7; i++) { map[0][i]=1; map[7][i]=1; } for (int i = 0; i < 8; i++) { map[i][0]=1; map[i][6]=1; } map[3][1]=1; map[3][2]=1; //s输出地图 System.out.println("地图构建完成"); printMap(map); return map; } public static void printMap(int[][] map){ for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j]+" "); } System.out.println(); } } /** * @param map 迷宫 * @param startX 起始行坐标 * @param startY 起始列坐标 * @param endX 结束行坐标 * @param endY 结束列坐标 * map 2 表示通路 * 3 表示该点走过，但走不通 * 迷宫策略，下->右->上->左，若果走不通就回溯 */ public static boolean setWay(int[][] map,int startX,int startY,int endX,int endY){ if(map[endX][endY]==2){ //通路找到 return true; }else { if (map[startX][startY]==0){ //按照策略下->右->上->左 map[startX][startY]=2;//假定该点可以走通 if (setWay(map,startX+1,startY,endX,endY)){ return true; }else if (setWay(map,startX,startY+1,endX,endY)){ return true; }else if (setWay(map,startX-1,startY,endX,endY)){ return true; }else if (setWay(map,startX,startY-1,endX,endY)){ return true; }else { map[startX][startY]=3; return false; } }else { return false; } } } } ``` ## 八皇后问题 ### 介绍 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 ### 思路 1. 第一个皇后先放第一行第一列 2. 第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适 3. 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解 4. 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到. 5. 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤 ### 代码实现 ```java package com.freedy.dataStructure.recursion; /** * @author Freedy * @date 2021/3/18 13:42 */ public class EightQueen { //统计摆法的次数 public static int count=0; public static void main(String[] args) { int[][] map = new int[8][8]; queen(map,0); } /** * 主递归方法 */ public static void queen(int[][] map, int row) { if (row < 8) { for (int i = 0; i < 8; i++) { if (map[row][i] == 0) { int[][] backtrackingMap = new int[8][8];//创建一个回溯数组 copyArr(map,backtrackingMap); mark(map, row, i); queen(map,row+1); map=backtrackingMap;//进行回溯 } } }else { count++; System.out.println("第"+count+"种解法"); printMap(map); } } /** *对数组做标记 * 即对同一行、同一列或同一斜线上的元素赋值为2 * 此时被赋值为2的地方就不能放置皇后 */ public static void mark(int[][] map, int x, int y) { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (i == x && j == y) { map[i][j] = 1; } else if (i == x || j == y || j == -i + x + y||j==i+(y-x)) { map[i][j] = 2; } } } } /** * 打印数组 * @param map */ public static void printMap(int[][] map) { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } } /** *复制数组来方便进行回溯 */ public static void copyArr(int[][] origin,int[][] newOne){ for (int i = 0; i < origin.length; i++) { System.arraycopy(origin[i], 0, newOne[i], 0, origin[i].length); } } } ``` 运行结果 ```java 第1种解法 1 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 1 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 第2种解法 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 1 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 1 2 2 2 ........... ........... ........... ........... ........... 第92种解法 2 2 2 2 2 2 2 1 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 2 2 2 进程已结束，退出代码为 0 ``` 使用一维数组代替二维数组进行优化，即数组只放皇后在数组索引那一行的位置 ```java package com.freedy.dataStructure.recursion; /** * @author Freedy * @date 2021/3/18 13:42 */ public class EightQueueOptimization { //定义一个max表示共有多少个皇后 public final static int max = 10; //定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3} public static int[] array = new int[max]; public static int count = 0; public static void main(String[] args) { //测试一把 ， 8皇后是否正确 long l = System.currentTimeMillis(); check(0); System.out.printf("一共有%d解法\n", count); System.out.println("总耗时"+(System.currentTimeMillis()-l)); } //编写一个方法，放置第n个皇后 //特别注意： check 是 每一次递归时，进入到check中都有 for(int i = 0; i < max; i++)，因此会有回溯 private static void check(int n) { if(n == max) { //n = 8 , 其实8个皇后就既然放好 print(); return; } //依次放入皇后，并判断是否冲突 for(int i = 0; i < max; i++) { //先把当前这个皇后 n , 放到该行的第1列 array[n] = i; //判断当放置第n个皇后到i列时，是否冲突 if(judge(n)) { // 不冲突 //接着放n+1个皇后,即开始递归 check(n+1); // } //如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置 } } //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突 /** * * @param n 表示第n个皇后 */ private static boolean judge(int n) { for(int i = 0; i < n; i++) { // 说明 //1. array[i] == array[n] 表示判断 第n个皇后是否和前面的n-1个皇后在同一列 //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线 // n = 1 放置第 2列 1 n = 1 array[1] = 1 // Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1 //3. 判断是否在同一行, 没有必要，n 每次都在递增 if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) { return false; } } return true; } //写一个方法，可以将皇后摆放的位置输出 private static void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } } ``` 将max改为12，耗时对比 原始算法 > 总耗时9090 > > 进程已结束，退出代码为 0 一维数组算法 > 总耗时2039 > > 进程已结束，退出代码为 0 # 排序介绍 ## 排序的分类： 1. 内部排序: 指将需要处理的所有数据都加载到内部存储器中进行排序。 2. 外部排序法： 数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。 ## 常见的排序 ![image-20210318165928272](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210318165928272.png) ## 度量一个程序(算法)执行时间的两种方法 1. 事后统计的方法： 这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, **这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。** 2. 事前估算的方法： 通过分析某个算法的时间复杂度来判断哪个算法更优. ## 算法的时间复杂度 ### 时间频度 一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。*一个算法中的语句执行次数称为语句频度或时间频度*记为**T(n)**。 - 时间频度的常数项可以忽略 - 时间频度的低次项可以忽略 - 时间频度的系数可以忽略 ### 时间复杂度 1. 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) )  为算法的渐进时间复杂度，简称时间复杂度。 2. T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。 3. 计算时间复杂度的方法： - 用常数1代替运行时间中的所有加法常数  T(n)=n²+7n+6 => T(n)=n²+7n+1 - 修改后的运行次数函数中，只保留最高阶项  T(n)=n²+7n+1 => T(n) = n² - 去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²) ### 常见的时间复杂度 1. 常数阶O(1) 2. 对数阶O(log2n) 3. 线性阶O(n) 4. 线性对数阶O(nlog2n) 5. 平方阶O(n^2) 6. 立方阶O(n^3) 7. k次方阶O(n^k) 8. 指数阶O(2^n) 常见的算法时间复杂度由小到大依次为：**Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n)** ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低 > 我们应该尽可能避免使用指数阶的算法 ### 平均时间复杂度和最坏时间复杂度 1. 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。 2. 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长 3. 平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如图:) ![image-20210318180238747](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210318180238747.png) ## 算法的空间复杂度 1. 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。 2. 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况 3. 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间. # 八大排序算法 ## 1. 冒泡排序(Bubble Sort) > 基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。 ```java package com.freedy.dataStructure.sort; import java.util.Arrays; /** * 冒泡排序 * @author Freedy * @date 2021/3/18 18:08 */ public class BubbleSorting { public static void main(String[] args) { //20个随机数 int[] arr={368,93,284,507,204,620,331,573,910,977, 711,305,825,438,698,49,868,241,598,737}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr){ boolean exchangeFlag=false; for (int i = arr.length-1; i >= 0; i--) { for (int j = 0; j < i; j++) { if (arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; exchangeFlag=true; } } if (!exchangeFlag){ //在上一轮交换中，没有发生一次交换。证明已经排序完成可以提前退出 break; }else { //重置标志位进行下一轮循环 exchangeFlag=false; } } } } ``` ## 2. 选择排序(Select Sort) > 选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。 > > 它的基本思想是：第一次从arr[0]-arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]-arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]-arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]-arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。 ```java package com.freedy.dataStructure.sort; import java.util.Arrays; /** * @author Freedy * @date 2021/3/18 18:58 */ public class SelectSorting { public static void main(String[] args) { //20个随机数 int[] arr={368,93,284,507,204,620,331,573,910,977, 711,305,825,438,698,49,868,241,598,737}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr){ for (int i = 0; i < arr.length-1; i++) { int min=Integer.MAX_VALUE;//int类型的最大值 int minIndex = 0; for (int j = i; j < arr.length; j++) { if (arr[j] 基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。 代码实现 ```java package com.freedy.dataStructure.sort; import java.util.Arrays; /** * @author Freedy * @date 2021/3/18 20:47 */ public class InsertionSorting { public static void main(String[] args) { //20个随机数 int[] arr={368,93,284,507,204,620,331,573,910,977, 711,305,825,438,698,49,868,241,598,737}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr){ for (int i = 0; i < arr.length-1; i++) { for (int j = 0; j < i+1; j++) { if (arr[j]>arr[i+1]){ int temp=arr[i+1]; System.arraycopy(arr, j, arr, j + 1, i + 1 - j); arr[j]=temp; } } } } } ``` ![image-20210318213942099](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210318213942099.png) ## 4. 希尔排序(Shell Sort) > 希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。 > > 希尔排序法基本思想: > > 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止 ![image-20210318215112399](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210318215112399.png) 代码实现 ```java package com.freedy.dataStructure.sort; import java.util.Arrays; /** * @author Freedy * @date 2021/3/18 21:42 */ public class ShellSorting { public static void main(String[] args) { //20个随机数 int[] arr={368,93,284,507,204,620,331,573,910,977, 711,305,825,438,698,49,868,241,598,737}; sort(arr); System.out.println(Arrays.toString(arr)); } /** * 优化后 */ public static void sort(int[] arr) { for (int gap = arr.length/2; gap > 0; gap /=2) { for (int i = gap; i < arr.length; i++) { int temp=arr[i]; for (int j = i-gap; j >=0 ; j-=gap) { if (temp 0; gap /=2) { //对每组进行排序 for (int i = 0; i < gap; i++) { //采用插入排序法对此组数据排序 for (int j = i; j < arr.length; j = j + gap) { for (int k = i; k < j; k = k + gap) { if (arr[j] 快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 代码实现 ```java package com.freedy.dataStructure.sort; import java.util.Arrays; /** * @author Freedy * @date 2021/3/19 22:39 */ public class QuickSort { public static void main(String[] args) { //20个随机数 int[] arr = {368, 93, 284, 507, 204, 620, 331, 573, 910, 977, 711, 305, 825, 438, 698, 49, 868, 241, 598, 737}; sort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr, int l, int r) { int left = l; int right = r; //中轴值 int pivot = arr[(left + right) / 2]; int temp = 0; while (left < right) { //寻找适合的值进行交换 while (arr[left] < pivot) left++; while (arr[right] > pivot) right--; //当满足条件提前退出，不然可能发生数组越界 if (right <= left) break; //交换两个元素 temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; //防止arr[left]==pivot==arr[right]时发生死循环 if (arr[left] == pivot) right--; if (arr[right] == pivot) left++; } //防止发生死循环,例如当l=0，r=1且arr[l]>arr[r]时,经过上面的交换后会得到left=right=1 //如果不错开则会调用sort(arr, 0, 1),这时就又回到上面那种情况了,所以会发生死循环 if (left == right) { left++; right--; } if (l < right) sort(arr, l, right); if (left < r ) sort(arr, left, r); } } ``` ## 6. 并归排序(Merge Sort) > 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。 ![image-20210320124508975](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210320124508975.png) 可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。 代码实现 ```java package com.freedy.dataStructure.sort; import java.util.Arrays; /** * @author Freedy * @date 2021/3/20 12:46 */ public class MergeSort { public static void main(String[] args) { //20个随机数 int[] arr = {368, 93, 284, 507, 204, 620, 331, 573, 910, 977, 711, 305, 825, 438, 698, 49, 868, 241, 598, 737}; sort(arr,0,arr.length-1,new int[arr.length]); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid=(left+right)/2; //向左递归分解 sort(arr,left,mid,temp); //向右递归分解 sort(arr,mid+1,right,temp); //每分解一次就合并一次 merge(arr,left,mid,right,temp); } } /** * @param arr 需要排序的数组 * @param left 左边有序列的初始索引 * @param mid 中间索引 * @param right 右边数列右侧索引 * @param temp 中转数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left;//表示左边序列的初始索引 int j = mid + 1;//表示右边边序列的初始索引 int t = 0; //指向temp的左边索引 //1.先把左右两边的数据按照规则填充到temp数组中,直到某一边的数据没有了为止 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t] = arr[i]; t++; i++; } else { temp[t] = arr[j]; t++; j++; } } //2. 把另一边剩余的数据按照原有的顺序填充到temp数组中 for (; i <= mid; t++, i++) temp[t] = arr[i]; for (; j <= right; t++, j++) temp[t] = arr[j]; //3. 将temp数组拷贝到arr System.arraycopy(temp, 0, arr, left, right - left + 1); } } ``` ## 7. 基数排序(Radix Sort) > 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用 > > 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法 > > 基数排序(Radix Sort)是桶排序的扩展 > > 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。 > 基数排序基本思想 > > 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 > > 这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤 ```java package com.freedy.dataStructure.sort; import java.util.Arrays; /** * @author Freedy * @date 2021/3/20 15:24 */ public class RadixSort { public static void main(String[] args) { //20个随机数 int[] arr = {368, 93, 284, 507, 204, 620, 331, 573, 910, 977, 711, 305, 825, 438, 698, 49, 868, 241, 598, 737}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr) { int[][] bucket = new int[10][arr.length]; int[] bucketIndex = new int[10];//表示每个桶所放入的数据个数 int max = Integer.MIN_VALUE; for (int k : arr) { if (max < Integer.toString(k).length()) { max = Integer.toString(k).length(); } } for (int k = 0; k < max; k++) { for (int ele : arr) { int digit = ele % 10; if (k != 0) digit = (ele / (int)(Math.pow(10,k))) % 10; bucket[digit][bucketIndex[digit]] = ele; bucketIndex[digit]++; } int index = 0; for (int i = 0; i < bucketIndex.length; i++) { if (bucketIndex[i] != 0) { for (int j = 0; j < bucketIndex[i]; j++) { arr[index] = bucket[i][j]; index++; } } } bucketIndex = new int[10];//清空桶 } } } ``` 注意！当数据量过大会导致堆溢出 ```java //对一亿个数进行排序时，报错 Caused by: java.lang.OutOfMemoryError: Java heap space at com.freedy.dataStructure.sort.RadixSort.sort(RadixSort.java:21) ... 6 more ``` - 基数排序的说明: - 基数排序是对传统桶排序的扩展，速度很快. - 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。 - 基数排序时稳定的。 - [注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的] - 有负数的数组，我们不能用基数排序来进行排序 ## 8. 堆排序 见下面 树的实际应用 # 常用排序算法总结和对比 ![image-20210320170735816](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210320170735816.png) 1. 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面； 2. 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面； 3. 内排序：所有排序操作都在内存中完成； 4. 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行； 5. 时间复杂度： 一个算法执行所耗费的时间。 6. 空间复杂度：运行完一个程序所需内存的大小。 7. n: 数据规模 8. k: “桶”的个数 9. In-place: 不占用额外内存 10. Out-place: 占用额外内存 ## 各个排序算法时间对比-单位ms #### 测试一亿条不同数据 ```java //第一次测试 java.util.Arrays总耗时:12365 com.freedy.dataStructure.sort.ShellSort总耗时:49918 com.freedy.dataStructure.sort.QuickSort总耗时:24897 com.freedy.dataStructure.sort.MergeSort总耗时:21941 //第二次测试 java.util.Arrays总耗时:12347 com.freedy.dataStructure.sort.ShellSort总耗时:51074 com.freedy.dataStructure.sort.QuickSort总耗时:20324 com.freedy.dataStructure.sort.MergeSort总耗时:20220 //第三次测试 java.util.Arrays总耗时:11740 com.freedy.dataStructure.sort.ShellSort总耗时:50217 com.freedy.dataStructure.sort.QuickSort总耗时:19434 com.freedy.dataStructure.sort.MergeSort总耗时:20933 ``` > 冒泡、插入、选择排序时间太长就没测了，基数排序由于数据量太大直接堆溢出了 #### 测试一千万条不同数据 ```java //第一次测试 java.util.Arrays总耗时:363 com.freedy.dataStructure.sort.ShellSort总耗时:246 com.freedy.dataStructure.sort.QuickSort总耗时:315 com.freedy.dataStructure.sort.MergeSort总耗时:197 com.freedy.dataStructure.sort.RadixSort总耗时:352 //第二次测试 java.util.Arrays总耗时:305 com.freedy.dataStructure.sort.ShellSort总耗时:344 com.freedy.dataStructure.sort.QuickSort总耗时:263 com.freedy.dataStructure.sort.MergeSort总耗时:257 com.freedy.dataStructure.sort.RadixSort总耗时:412 //第三次测试 java.util.Arrays总耗时:388 com.freedy.dataStructure.sort.ShellSort总耗时:426 com.freedy.dataStructure.sort.QuickSort总耗时:304 com.freedy.dataStructure.sort.MergeSort总耗时:214 com.freedy.dataStructure.sort.RadixSort总耗时:364 ``` > 冒泡、插入、选择排序时间太长没结果。 #### 测试十万条不通数据 ```java //第一次测试 java.util.Arrays总耗时:56 com.freedy.dataStructure.sort.ShellSort总耗时:68 com.freedy.dataStructure.sort.QuickSort总耗时:33 com.freedy.dataStructure.sort.MergeSort总耗时:37 com.freedy.dataStructure.sort.RadixSort总耗时:83 com.freedy.dataStructure.sort.BubbleSort总耗时:23153 com.freedy.dataStructure.sort.SelectSort总耗时:5512 com.freedy.dataStructure.sort.InsertionSort总耗时:7203 //第二次测试 java.util.Arrays总耗时:64 com.freedy.dataStructure.sort.ShellSort总耗时:49 com.freedy.dataStructure.sort.QuickSort总耗时:46 com.freedy.dataStructure.sort.MergeSort总耗时:32 com.freedy.dataStructure.sort.RadixSort总耗时:78 com.freedy.dataStructure.sort.BubbleSort总耗时:22998 com.freedy.dataStructure.sort.SelectSort总耗时:5551 com.freedy.dataStructure.sort.InsertionSort总耗时:7247 //第三次测试 java.util.Arrays总耗时:95 com.freedy.dataStructure.sort.ShellSort总耗时:31 com.freedy.dataStructure.sort.QuickSort总耗时:43 com.freedy.dataStructure.sort.MergeSort总耗时:32 com.freedy.dataStructure.sort.RadixSort总耗时:75 com.freedy.dataStructure.sort.BubbleSort总耗时:22947 com.freedy.dataStructure.sort.SelectSort总耗时:5777 com.freedy.dataStructure.sort.InsertionSort总耗时:7279 ``` 综上可以看出冒泡、插入、选择实在实在是慢了,以后排序可以直接pass掉了 #### 测速代码 ```java package com.freedy.dataStructure.sort; import java.lang.reflect.Method; import java.util.Arrays; import java.util.Random; /** * @author Freedy * @date 2021/3/11 14:11 */ public class Test { //测试数组 public static int[] TEST_ARRAY; //最大测试数据 public final static int MAX_TEST_DATA = 100000; //是否打印测试数据 public final static boolean whetherPrint = false; //是否测试相同数据 public final static boolean whetherSame = false; public static void main(String[] args) throws Exception { sort("java.util.Arrays"); sort("com.freedy.dataStructure.sort.ShellSort"); sort("com.freedy.dataStructure.sort.QuickSort", 0, MAX_TEST_DATA - 1); sort("com.freedy.dataStructure.sort.MergeSort", 0, MAX_TEST_DATA - 1, new int[MAX_TEST_DATA]); sort("com.freedy.dataStructure.sort.RadixSort"); sort("com.freedy.dataStructure.sort.BubbleSort"); sort("com.freedy.dataStructure.sort.SelectSort"); sort("com.freedy.dataStructure.sort.InsertionSort"); } /** * 测试主方法 * 利用反射调取各个类的sort算法 * * @param className 测试类的全类名 */ public static void sort(String className, Object... args) { try { int[] arr = randomArrMaker(); //通过全类名获取字节码对象 Class sortClass = Class.forName(className); Method[] methods = sortClass.getDeclaredMethods(); boolean isInvoke = false; Exception e = null; for (Method method : methods) { if (method.getName().equals("sort") && method.getGenericParameterTypes()[0]. getTypeName().equals("int[]")) { method.setAccessible(true); Object[] obj = new Object[args.length + 1]; obj[0] = arr; System.arraycopy(args, 0, obj, 1, args.length); //执行方法 try { long time = System.currentTimeMillis(); method.invoke(null, obj); System.out.println(sortClass.getName() + "总耗时:" + (System.currentTimeMillis() - time)); isInvoke = true; break; } catch (Exception exception) { e=exception; } } } if (!isInvoke) { if (e!=null){ e.printStackTrace(); } throw new RuntimeException("此类中没有符合测试的sort方法,请检查参数是否输入有误."); } if (whetherPrint) { System.out.println(Arrays.toString(arr)); } } catch (Exception e) { e.printStackTrace(); } } /** * 生成随机数组 */ public static int[] randomArrMaker() { Random random = new Random(); if (whetherSame) { if (TEST_ARRAY == null) { int[] ints = new int[MAX_TEST_DATA]; for (int i = 0; i < MAX_TEST_DATA; i++) { ints[i] = random.nextInt(MAX_TEST_DATA * 100); } TEST_ARRAY = ints; } return TEST_ARRAY.clone(); } else { int[] ints = new int[MAX_TEST_DATA]; for (int i = 0; i < MAX_TEST_DATA; i++) { ints[i] = random.nextInt(MAX_TEST_DATA * 100); } return ints; } } } ``` # 查找算法 ## 二分查找算法 ### 思路分析 1. 首先确定该数组的中间的下标mid= (left +right)/2 2. 然后让需要查找的数 findval和arr[mid]比较 - findval>arr[mid],说明你要查找的数在mid的右边,因此需要递归的向右查找 - findval right就需要退出 ### 代码 ```java package com.freedy.dataStructure.search; import com.freedy.dataStructure.sort.Test; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 使用二分查找的前提是数组是有序的 * * @author Freedy * @date 2021/3/22 20:40 */ public class BinarySearch { public static int count = 0; public static void main(String[] args) { Test.MAX_TEST_DATA = 10000; int[] ints = Test.randomArrMaker(); ints[50] = 35324; Arrays.sort(ints); System.out.println(Arrays.toString(mulSearch(ints, 0, ints.length - 1, 35324))); System.out.println(count); } public static int search(int[] arr, int left, int right, int findVal) { int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { if (left == right) return -1; return search(arr, mid + 1, right, findVal); } else if (findVal < midVal) { if (left == right) return -1; return search(arr, left, mid-1, findVal); } else { return mid; } } /** * 是上面方法的加强,可以找到多个索引 */ public static int[] mulSearch(int[] arr, int left, int right, int findVal) { count++; int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { if (left == right) return new int[]{-1}; return mulSearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) { if (left == right) return new int[]{-1}; return mulSearch(arr, left, mid-1, findVal); } else { int lIndex = mid; int rIndex = mid + 1; List list = new ArrayList<>(); while (lIndex >= left && arr[lIndex] == findVal) { list.add(lIndex); lIndex--; } while (rIndex <= right && arr[rIndex] == findVal) { list.add(rIndex); rIndex++; } return list.stream().mapToInt(Integer::intValue).toArray(); } } } ``` ## 插值查找算法 ### 插值查找原理介绍 1. 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。 2. 将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right ![image-20210322214838827](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210322214838827.png) 3. int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/*插值索引*/ 对应前面的代码公式： int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left]) 4. 举例说明插值查找算法 1-100 的数组 代码和上面几乎一模一样,最大的差别就是mid不一样 ```java //然后需要加上if防止数组越界 if (findValarr[right]) return new int[]{-1}; //进行中间索引计算的时候 需要将中间的计算过程换成double类型,不然会是mid计算不准确降低效率 int mid = left == right ? left : (int)((double)left + (double)(findVal - arr[left]) / (double)(arr[right] - arr[left]) * (double)(right - left)); ``` > 插值查找注意事项： > > 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快. > 关键字分布不均匀的情况下，该方法不一定比折半查找要好 ## 斐波那契(黄金分割法)查找算法 ### 基本介绍 1. 黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。 2. 斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例，无限接近 黄金分割值0.618 ### 波那契(黄金分割法)原理: 1. 斐波那契查找原理与前两种相似，仅仅 改变了中间结点（mid）的位置，mid不 再是中间或插值得到，而是位于黄金分 割点附近，即mid=low+F(k-1)-1 （F代表斐波那契数列），如下图所示 ![image-20210322230337448](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210322230337448.png) 对F(k-1)-1的理解： 1. 由斐波那契数列 **F[k]=F[k-1]+F[k-2]** 的性质，可以得到 **（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1** 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1 2. 类似的，每一子段也可以用相同的方式分割 3. 但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。 ![image-20210322230405158](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210322230405158.png) 代码实现 ```java package com.freedy.dataStructure.search; import com.freedy.dataStructure.sort.Test; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * @author Freedy * @date 2021/3/23 10:42 */ public class FibonacciSearch { public static int maxSize = 100; public static int count = 0; public static void main(String[] args) { Test.MAX_TEST_DATA = 10; int[] ints = Test.randomArrMaker(); ints[4] = 15; ints[5] = 15; ints[6] = 15; Arrays.sort(ints); System.out.println(Arrays.toString(Search(ints, 15))); System.out.println(count); } /** * 使用非递归方式 */ public static int[] Search(int[] arr, int key) { int low=0; int height= arr.length-1; int k=0; int mid=0; int[] fib = fib(); while (height-low>fib[k]-1){ k++; } int[] fibArr = Arrays.copyOf(arr, fib[k]); for (int i = height+1; i < fibArr.length; i++) { fibArr[i]=Integer.MAX_VALUE; } //只要条件满足就一直找 while (low<=height){ count++; mid=low+fib[k-1]-1; if (keyfibArr[mid]){ low=mid+1; k-=2; }else { if (mid list = new ArrayList<>(); while (lIndex >= low && arr[lIndex] == key) { list.add(lIndex); lIndex--; } while (rIndex <= height && arr[rIndex] == key) { list.add(rIndex); rIndex++; } return list.stream().mapToInt(Integer::intValue).toArray(); }else { return new int[]{height}; } } } return new int[]{-1}; } /** * 得到一个斐波那契数列 */ public static int[] fib() { int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i < maxSize; i++) { f[i] = f[i - 1] + f[i - 2]; } return f; } } ``` # 哈希表 ## 介绍 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 ![image-20210323121627220](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210323121627220.png) ## 代码实现 ```java package com.freedy.dataStructure.hashTable; import java.util.ArrayList; import java.util.StringJoiner; /** * @author Freedy * @date 2021/3/23 16:42 */ public class HashTable { private ArrayList> linkedListArr; private int size = 10; public HashTable(int size) { this.size = size; initLinkedListArr(); } public HashTable() { initLinkedListArr(); } private void initLinkedListArr() { linkedListArr = new ArrayList<>(size); for (int i = 0; i < size; i++) { LinkedList list = new LinkedList<>(); linkedListArr.add(list); } } public void put(K key, T value) { LinkedList list = linkedListArr.get(hash(key)); Node node = list.getNode(key); if (node == null) { list.add(key, value); } else { node.setData(value); } } public T get(K key) { LinkedList list = linkedListArr.get(hash(key)); return list.get(key); } public void remove(K key) { LinkedList list = linkedListArr.get(hash(key)); list.remove(key); } /** * 打印出hashTable的结构 */ public void printStructure() { for (int i = 0; i < size; i++) { LinkedList list = linkedListArr.get(i); StringBuilder builder = new StringBuilder(); builder.append("HEADER").append(i).append("-->"); int size = list.size(); for (int j = 0; j < size; j++) { builder.append(list.getNode(j).toString()); builder.append("-->"); } System.out.println(builder); } } /** * 散列函数,这里使用取模法 */ private int hash(K key) { return key.hashCode() % size; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("{"); for (int i = 0; i < size; i++) { LinkedList list = linkedListArr.get(i); for (int j = 0; j < list.size(); j++) { Node node = list.getNode(j); builder.append(node.getKey().toString()); builder.append("="); builder.append(node.getData().toString()); builder.append(", "); } } builder.delete(builder.length() - 2, builder.length()); builder.append("}"); return builder.toString(); } /** * 链表类 */ public static class LinkedList { private final Node head; public LinkedList() { head = new Node(); } public void add(K key, T data) { Node tNode = new Node(); tNode.setData(data); tNode.setKey(key); getNode(size() - 1).setNext(tNode); } public T get(K key) { for (int i = 0; i < size(); i++) { if (getNode(i).getKey().equals(key)) { return getNode(i).getData(); } } return null; } public T get(int index) { Node node = getNode(index); return node.getData(); } public void remove(K key) { //获取前置节点 for (int i = 0; i < size(); i++) { if (getNode(i).getKey().equals(key)) { remove(i); } } } /** * 删除索引 */ public void remove(int index) { //获取前置节点 Node pre = getNode(index - 1); Node node = getNode(index); pre.setNext(node.getNext()); } /** * @return 链表大小 */ public int size() { int size = 0; Node temp = head.getNext(); while (temp != null) { size++; temp = temp.getNext(); } return size; } /** * 获取链表 * -1 代表头节点 */ public Node getNode(int index) { int count = -1; Node temp = head; while (temp != null && index != count) { count++; temp = temp.getNext(); } return temp; } public Node getNode(K key) { for (int i = 0; i < size(); i++) { if (getNode(i).getKey().equals(key)) { return getNode(i); } } return null; } @Override public String toString() { if (head.getNext() == null) { return "[]"; } Node temp = head.getNext(); StringBuilder stringBuffer = new StringBuilder(); stringBuffer.append("["); while (temp != null) { stringBuffer.append(temp.getData().toString()).append(","); temp = temp.getNext(); //将temp后移 } stringBuffer.deleteCharAt(stringBuffer.length() - 1); stringBuffer.append("]"); return stringBuffer.toString(); } } /** * 节点类 */ public static class Node { private K key; private T data; private Node next; public K getKey() { return key; } public void setKey(K key) { this.key = key; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } @Override public String toString() { return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]") .add("key=" + key) .add("data=" + data) .toString(); } } } ``` ## 测试代码 ```java package com.freedy.dataStructure.hashTable; import java.util.StringJoiner; /** * @author Freedy * @date 2021/3/23 16:42 */ public class Test { public static void main(String[] args) { HashTable table = new HashTable<>(5); Emp emp1 = new Emp(1, "张三"); Emp emp2 = new Emp(2, "王五"); Emp emp3 = new Emp(3, "李四"); Emp emp4 = new Emp(4, "王八蛋"); table.put(1,emp1); table.put(2,emp2); table.put(3,emp3); table.put(1,emp4); System.out.println(table); table.printStructure(); Emp s = table.get(2); System.out.println(s); table.remove(2); System.out.println(table); table.printStructure(); } static class Emp{ public int id; public String name; public Emp(int id, String name) { this.id = id; this.name = name; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public String toString() { return new StringJoiner(", ", Emp.class.getSimpleName() + "[", "]") .add("id=" + id) .add("name='" + name + "'") .toString(); } } } ``` ## 结果输出 ```java {1=Emp[id=4, name='王八蛋'], 2=Emp[id=2, name='王五'], 3=Emp[id=3, name='李四']} HEADER0--> HEADER1-->Node[key=1, data=Emp[id=4, name='王八蛋']]--> HEADER2-->Node[key=2, data=Emp[id=2, name='王五']]--> HEADER3-->Node[key=3, data=Emp[id=3, name='李四']]--> HEADER4--> Emp[id=2, name='王五'] {1=Emp[id=4, name='王八蛋'], 3=Emp[id=3, name='李四']} HEADER0--> HEADER1-->Node[key=1, data=Emp[id=4, name='王八蛋']]--> HEADER2--> HEADER3-->Node[key=3, data=Emp[id=3, name='李四']]--> HEADER4--> 进程已结束，退出代码为 0 ``` # 树 为什么需要树这种数据结构？ 1. 数组存储方式的分析 - 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。 - 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低 [示意图] ![image-20210323200637086](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210323200637086.png) 2. 链式存储方式的分析 - 优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。 - 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历) 【示意图】 ![image-20210323200652824](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210323200652824.png) 3. 树存储方式的分析 能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。【示意图,后面详讲】案例: [7, 3, 10, 1, 5, 9, 12] ![image-20210323200730271](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210323200730271.png) **树示意图** ![image-20210323200756484](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210323200756484.png) - 树的常用术语(结合示意图理解): - 节点 - 根节点 - 父节点 - 子节点 - 叶子节点 (没有子节点的节点) - 节点的权(节点值) - 路径(从root节点找到该节点的路线) - 层 - 子树 - 树的高度(最大层数) - 森林 :多颗子树构成森林 ## 二叉树 ### 二叉树的概念 1. 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。 2. 二叉树的子节点分为左节点和右节点。 3. 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。 4. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。 ### 二叉树的遍历、搜索、删除 说明： > 前序遍历: 先输出父节点，再遍历左子树和右子树 > 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树 > 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点 > 小结: 看输出父节点的顺序，就确定是前序，中序还是后序 代码实现 ```java package com.freedy.dataStructure.tree; import org.w3c.dom.Node; import java.util.StringJoiner; /** * @author Freedy * @date 2021/3/23 19:50 */ public class BinaryTree { private final Node root; private Node temp; private Node last; public BinaryTree(T data) { root = new Node<>(); root.setData(data); temp = root; last = root; } public BinaryTree(Node root) { this.root = root; temp = root; last = root; } /** * 向左插入，并且下一次操作是以你现在插入的那个为准 */ public BinaryTree putLeft(T data) { last = temp; Node node = new Node<>(); node.setData(data); temp.setLeftNode(node); temp = node; return this; } /** * 向有插入，并且下一次操作是以你现在插入的那个为准 */ public BinaryTree putRight(T data) { last = temp; Node node = new Node<>(); node.setData(data); temp.setRightNode(node); temp = node; return this; } /** * 让插入标准 回到root */ public BinaryTree returnRoot() { temp = root; return this; } /** * 让插入标准 回到上次操作 */ public BinaryTree returnLast() { temp = last; return this; } /** * 前序遍历 */ public void preOrder() { if (root != null) root.preOrder(); } /** * 中续遍历 */ public void infixOrder() { if (root != null) root.infixOrder(); } /** * 后续遍历 */ public void postOrder() { if (root != null) root.postOrder(); } /** * 判断树是否包含某个节点 */ public Boolean contain(T data) { return root.search(data); } /** * 删除树上的某个节点,并且连同该节点的子树 */ public Boolean del(T data) { if (root.data.equals(data)) return true; return root.deleteNode(data); } public static class Node { private T data; private Node leftNode; private Node rightNode; public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getLeftNode() { return leftNode; } public void setLeftNode(Node leftNode) { this.leftNode = leftNode; } public Node getRightNode() { return rightNode; } public void setRightNode(Node rightNode) { this.rightNode = rightNode; } @Override public String toString() { return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]") .add("data=" + data) .toString(); } /** * 前中后序遍历 */ public void preOrder() { System.out.println(this); if (leftNode != null) { leftNode.preOrder(); } if (rightNode != null) { rightNode.preOrder(); } } public void infixOrder() { if (leftNode != null) { leftNode.infixOrder(); } System.out.println(this); if (rightNode != null) { rightNode.infixOrder(); } } public void postOrder() { if (leftNode != null) { leftNode.postOrder(); } if (rightNode != null) { rightNode.postOrder(); } System.out.println(this); } public boolean search(T data){ if (this.data.equals(data)) return true; if (leftNode != null) { boolean left = leftNode.search(data); if (left) return true; } if (rightNode != null) { return rightNode.search(data); } return false; } public Boolean deleteNode(T data) { if (leftNode!=null&&leftNode.getData().equals(data)){ leftNode=null; return true; } if (rightNode != null&&rightNode.getData().equals(data)) { rightNode=null; return true; } if (leftNode != null) { boolean left = leftNode.deleteNode(data); if (left) return true; } if (rightNode != null) { return rightNode.deleteNode(data); } return false; } } } ``` 测试代码 ```java package com.freedy.dataStructure.tree; /** * @author Freedy * @date 2021/3/23 20:36 */ public class Test { public static void main(String[] args) { BinaryTree tree = new BinaryTree<>(0); tree.putLeft(1).putLeft(2).returnLast().putRight(3); tree.returnRoot(); tree.putRight(4).putLeft(5).returnLast().putRight(6); tree.putRight(7).returnLast().putLeft(9); tree.preOrder(); System.out.println("======================="); tree.infixOrder(); System.out.println("======================="); tree.postOrder(); System.out.println(tree.contain(12)); System.out.println(tree.del(4)); tree.preOrder(); } } ``` 结果 ```java Node[data=0] Node[data=1] Node[data=2] Node[data=3] Node[data=4] Node[data=5] Node[data=6] Node[data=9] Node[data=7] ======================= Node[data=2] Node[data=1] Node[data=3] Node[data=0] Node[data=5] Node[data=4] Node[data=9] Node[data=6] Node[data=7] ======================= Node[data=2] Node[data=3] Node[data=1] Node[data=5] Node[data=9] Node[data=7] Node[data=6] Node[data=4] Node[data=0] true true Node[data=0] Node[data=1] Node[data=2] Node[data=3] ``` ### 非递归遍历 1. 前序遍历的非递归写法 前序遍历的非递归写法要简单不少,我们来简单捋一下思路,我们需要先遍历根节点,再遍历左子树的节点,再遍历右子树的节点,完成遍历.另外,一般来说,由递归转化为非递归,我们都需要用到栈,这里也不例外.下面直接上代码,原理都在代码里面进行解释. ```cpp void preOrder(TreeNode* root) { if(root == nullptr) { return; } stack s; auto p = root; while(!s.empty() || p) { //直接访问树的最左节点,因为是先序遍历所以每次访问先打印节点的值 while(p) { s.push(p); cout<left; } if(!s.empty()) { auto node = s.top(); s.pop(); p = node->right; } } } ``` 1. 中序遍历的非递归写法 在三种非遍历算法中,中序遍历应该是最简单的了.实现代码q其实比较好玩的是和前序遍历基本一样(笑),只是改了一下输出的位置. ```cpp void inOrder(TreeNode* root) { if(root == nullptr) { return; } stack s; auto p = root; while(!s.empty() || p) { //到达树的最左节点,由于是中序遍历,所以先不打印节点的值 while(p) { s.push(p); p = p->left; } if(!s.empty()) { auto node = s.top(); s.pop(); cout<right; } } } ``` 1. 后序遍历的非递归写法 这个应该是三种非递归的写法中最难的了,因为我们需要判断当我们从子树返回的时候判断是从左子树返回还是从右子树返回的,所以我们需要一个prev指针来保存我们上一次访问的指针,其余的部分其实和之前也没有差很多. ```cpp void postOrder(TreeNode* root) { if(root == nullptr) { return; } stack s; auto p = node; TreeNode* prev = nullptr; while(!s.empty() || p) { while(p) { s.push(p); p = p->left; } if(!s.empty()) { auto node = s.top(); s.pop(); if(!node->right || node->right == prev) { cout<val; prev = node; } else { s.push(node); p = node->right; } } } } ``` 总结: 其实上面的代码风格十分统一,我个人觉得理解起来还是很简单的,主要核心还是理解遍历的顺序问题,我们每次都先访问到树的最左边,然后不断的压栈,思路其实并不难理解. ### 顺序存储二叉树 说明 > 从数据存储来看，数组存储方式和树 > 的存储方式可以相互转换，即数组可 > 以转换成树，树也可以转换成数组， > 看右面的示意图。 ![image-20210324095403283](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210324095403283.png) 顺序存储二叉树的特点: 1. 顺序二叉树通常只考虑完全二叉树 2. 第n个元素的左子节点为 2 * n + 1 3. 第n个元素的右子节点为 2 * n + 2 4. 第n个元素的父节点为 (n-1) / 2 5. n : 表示二叉树中的第几个元素(按0开始编号,如上图所示) 遍历顺序存储二叉树 ```java public class ArrBinaryTree { private final int[] arr;//存储数据节点的数组 public ArrBinaryTree(int[] arr) { this.arr = arr; } public void preOrder(){ preOrder(0); } /** * 完成顺序存储二叉树的前序遍历 */ public void preOrder(int index){ if (arr==null||arr.length==0) System.out.println("数组为空"); System.out.println(arr[index]); //向左遍历 if ((index*2+1) root; //为了实现线索化，需要创建要给指向当前节点的前驱节点的指针 private Node preNode; public void threadedNodes(Node node){ if (node==null) return; //先线索话左子树 threadedNodes(node.getLeftNode()); //先线索话当前节点 if (node.getLeftNode()==null){ //就让点前节点的做指针指向前驱节点 node.setLeftNode(preNode); node.setLeftType(1); }else{ node.setLeftType(0); } if (preNode!=null&&preNode.getRightNode()==null){ //就让点前节点的做指针指向前驱节点 preNode.setRightNode(node); preNode.setRightType(1); }else if (preNode!=null){ preNode.setRightType(0); } preNode=node; //先线索话右子树 threadedNodes(node.getRightNode()); } ``` [详细代码见gitee](https://gitee.com/) ## 树结构的实际应用 ### 堆排序 #### 介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。 2. 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。 3. 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆 4. 大顶堆举例说明 ![image-20210324204129209](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210324204129209.png) 我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子: ![image-20210324204141744](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210324204141744.png) **大顶堆特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 对应第几个节点，i从0开始编号** **小顶堆特点：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] // i 对应第几个节点，i从0开始编号一般升序采用大顶堆，降序采用小顶堆** #### 堆排序基本思想 1. 将待排序序列构造成一个大顶堆 2. 此时，整个序列的最大值就是堆顶的根节点。 3. 将其与末尾元素进行交换，此时末尾就为最大值。 4. 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。 可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了. 代码实现 ```java package com.freedy.dataStructure.tree; import java.util.Arrays; /** * @author Freedy * @date 2021/3/24 20:59 */ public class HeapSort { public static void main(String[] args) { int[] arr = {4, 6, 8, 5, 9}; sort(arr); System.out.println(Arrays.toString(arr)); ; } public static void sort(int[] arr) { int temp; for (int i = arr.length / 2 - 1; i >= 0; i--) { adjust(arr, i, arr.length); } for (int i = arr.length-1; i > 0; i--) { temp=arr[i]; arr[i]=arr[0]; arr[0]=temp; adjust(arr,0,arr.length); } } /** * 将一个非叶子节点子树调节成大顶堆 * * @param arr 数组 * @param i 表示非叶子节点在数组中的索引 * @param length 表示有多少个元素继续调整,length 是在逐渐减少 */ public static void adjust(int[] arr, int i, int length) { int temp = arr[i]; //开始调整 for (int j = i * 2 + 1; j < length; j = j * 2 + 1) { if (j + 1 < length && arr[j] < arr[j + 1]) { j++; } if (arr[j] > temp) { arr[i] = arr[j]; i = j; } else { break; } } arr[i] = temp; } } ``` ### 哈夫曼树(Huffman Tree) #### 介绍 1. 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。 2. 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。 #### 重要概念和举例说明 1. 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1 2. 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积 3. 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。 4. WPL最小的就是赫夫曼树 ![image-20210325204401778](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210325204401778.png) 从上图中可以看出树的形态不同，所构成的wpl也不同。而他的所有形态中，wpl最小的就是赫夫曼殊（如上图第二个） #### 构成赫夫曼树的步骤： 1. 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树 2. 取出根节点权值最小的两颗二叉树 3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和 4. 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树 #### 代码实现 ```java package com.freedy.dataStructure.tree; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.stream.Collectors; /** * @author Freedy * @date 2021/3/25 21:16 */ public class HuffmanTree { public static void main(String[] args) { int[] arr={13,7,8,3,29,6,1}; BinaryTree.Node node = buildHuffmanTree(arr); node.preOrder(); System.out.println(node); } public static BinaryTree.Node buildHuffmanTree(int[] arr){ List> nodeList = Arrays. stream(arr).boxed().map(BinaryTree.Node::new). sorted(Comparator.comparingInt(BinaryTree.Node::getData)). collect(Collectors.toList()); while (nodeList.size()>1){ BinaryTree.Node left = nodeList.get(0); BinaryTree.Node right = nodeList.get(1); BinaryTree.Node parent = new BinaryTree.Node<>(left.getData()+right.getData(),left,right); nodeList.remove(0); nodeList.remove(0); nodeList.add(parent); nodeList.sort(Comparator.comparingInt(BinaryTree.Node::getData)); } return nodeList.get(0); } } ``` ### 哈夫曼编码 #### 介绍、 1. 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法 2. 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。 3. 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间 4. 赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码 #### 原理剖析 通信领域中信息的处理方式1-定长编码 ```jade i like like like java do you like a java // 共40个字符(包括空格) 105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //对应Ascii码 01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制 按照二进制来传递信息，总的长度是 359 (包括空格) ``` 通信领域中信息的处理方式2-变长编码 ```java i like like like java do you like a java // 共40个字符(包括空格) d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数 0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d //对应的编码 说明：按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如 空格出现了9 次， 编码为0 ,其它依次类推. 按照上面给各个字符规定的编码，则我们在传输 "i like like like java do you like a java" 数据时，编码就是 10010110100... 字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码， 即不能匹配到重复的编码(这个在赫夫曼编码中，我们还要进行举例说明, 不捉急) ``` 通信领域中信息的处理方式3-赫夫曼编码 ```java i like like like java do you like a java // 共40个字符(包括空格) d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值.(图后) ``` #### 代码实现 ```java package com.freedy.dataStructure.tree; import java.io.*; import java.nio.charset.StandardCharsets; import java.util.*; import java.util.Map.Entry; import java.util.stream.Collectors; /** * @author Freedy * @date 2021/3/25 22:31 */ public class HuffmanCode { public static void main(String[] args) { String str = "哈哈,我是测试语句，啦啦啦啦啦啦"; HuffmanData encode = encode(str); String s = decode(encode); System.out.println("原始字节数组："+Arrays.toString(str.getBytes(StandardCharsets.UTF_8))); System.out.println("压缩后的字节数组："+Arrays.toString(encode.getData())); System.out.println("解压字典："+encode.getMap()); System.out.println(s); } public static void zipFile(File srcFile,File desFile){ try(FileInputStream is = new FileInputStream(srcFile); FileOutputStream os = new FileOutputStream(desFile); ObjectOutputStream oos = new ObjectOutputStream(os)) { byte[] b=new byte[is.available()]; is.read(b); HuffmanData encode = encode(b); oos.writeObject(encode); } catch (Exception e) { e.printStackTrace(); } } public static HuffmanData encode(String str) { byte[] bytes = str.getBytes(StandardCharsets.UTF_8); return HuffmanEncode( bytes, generateCode( buildHuffmanTree(statisticsNodes( bytes )) )); } public static HuffmanData encode(byte[] bytes) { return HuffmanEncode( bytes, generateCode( buildHuffmanTree(statisticsNodes( bytes )) )); } public static String decode(HuffmanData data) { return HuffmanDecode(data.data,data.map,data.flag); } /** * 根据bytes数组统计各个单词出现的频率 */ public static List> statisticsNodes(byte[] bytes) { HashMap map = new HashMap<>(); for (Byte b : bytes) { map.merge(b, 1, Integer::sum); } return map.entrySet(). stream().map(item -> new BinaryTree.Node<>( new HuffmanStruct(item.getKey(), item.getValue()) )).sorted((a, b) -> b.getData().getWeight() - a.getData().getWeight()).collect(Collectors.toList()); } /** * 构建哈夫曼树 */ private static BinaryTree.Node buildHuffmanTree(List> nodes) { while (nodes.size() > 1) { nodes.sort(Comparator.comparingInt(a -> a.getData().getWeight())); BinaryTree.Node left = nodes.get(0); BinaryTree.Node right = nodes.get(1); HuffmanStruct struct = new HuffmanStruct(left.getData().getWeight() + right.getData().getWeight()); BinaryTree.Node parent = new BinaryTree.Node(struct, left, right); nodes.remove(0); nodes.remove(0); nodes.add(parent); } return nodes.get(0); } /** * 生成各个单词对应的编码 */ public static Map generateCode(BinaryTree.Node node) { Map map = new HashMap<>(); StringBuilder route = new StringBuilder(); Stack> stack = new Stack<>(); int deep = 0; while (!stack.isEmpty() || node != null) { while (node != null) { node.getData().setDeep(deep); stack.push(node); node = node.getLeftNode(); deep++; route.insert(deep - 1, "0"); } if (!stack.isEmpty()) { BinaryTree.Node sNode = stack.pop(); if (sNode.getRightNode() == null && sNode.getLeftNode() == null) { map.put(sNode.getData().getData(), route.substring(0, sNode.getData().getDeep())); } node = sNode.getRightNode(); deep = sNode.getData().getDeep() + 1; route.insert(deep - 1, "1"); } } return map; } /** * 生成哈夫曼编码 */ public static HuffmanData HuffmanEncode(byte[] data, Map map) { StringBuilder builder = new StringBuilder(); for (byte datum : data) { String code = map.get(datum); builder.append(code); } int len = (builder.length() + 7) / 8; byte[] encodeByte = new byte[len]; boolean flag = true; for (int i = 0, index = 0; i < builder.length(); i += 8, index++) { String stringByte; if (i + 8 > builder.length()) { stringByte = builder.substring(i); flag = false; } else { stringByte = builder.substring(i, i + 8); } encodeByte[index] = (byte) Integer.parseInt(stringByte, 2); } HuffmanData huffmanData = new HuffmanData(); huffmanData.setData(encodeByte); huffmanData.setFlag(flag); huffmanData.setMap(map); return huffmanData; } /** * 哈夫曼解码 */ public static String HuffmanDecode(byte[] decodeByte, Map map,boolean flag) { StringBuilder str = new StringBuilder(); for (int i = 0; i < decodeByte.length; i++) { String s = toBinaryString(flag||(i != decodeByte.length - 1), decodeByte[i]); str.append(s); } StringBuilder builder = new StringBuilder(); ArrayList result = new ArrayList<>(); for (int i = 0; i < str.length(); i++) { builder.append(str.charAt(i)); if (map.containsValue(builder.toString())) { Set bytes = map.keySet(); for (Byte aByte : bytes) { if (map.get(aByte).equals(builder.toString())) { result.add(aByte); break; } } builder = new StringBuilder(); } } byte[] bytes = new byte[result.size()]; for (int i = 0; i < result.size(); i++) { bytes[i] = result.get(i); } return new String(bytes); } /** *字节转二进制字符串 */ private static String toBinaryString(boolean flag, byte b) { int temp = b; if (flag) { temp |= 0x100; } String str = Integer.toBinaryString(temp); if (flag) { return str.substring(str.length() - 8); } else { return str; } } public static class HuffmanStruct { private Byte data; private int weight; private int deep; public int getDeep() { return deep; } public void setDeep(int deep) { this.deep = deep; } public HuffmanStruct(Byte data, int weight) { this.data = data; this.weight = weight; } public HuffmanStruct(int weight) { this.weight = weight; } public Byte getData() { return data; } public void setData(Byte data) { this.data = data; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } @Override public String toString() { return new StringJoiner(", ", HuffmanStruct.class.getSimpleName() + "[", "]") .add("data=" + data) .add("weight=" + weight) .toString(); } } public static class HuffmanData { private byte[] data; private Map map; private boolean flag; public HuffmanData(byte[] data, Map map, boolean flag) { this.data = data; this.map = map; this.flag = flag; } public HuffmanData() { } public byte[] getData() { return data; } public void setData(byte[] data) { this.data = data; } public Map getMap() { return map; } public void setMap(Map map) { this.map = map; } public boolean isFlag() { return flag; } public void setFlag(boolean flag) { this.flag = flag; } } } ``` #### 测试 ```java //哈夫曼对字符串编码 public static void main(String[] args) { String str = "哈哈,我是测试语句，啦啦啦啦啦啦"; HuffmanData encode = encode(str); String s = decode(encode); System.out.println("原始字节数组："+Arrays.toString(str.getBytes(StandardCharsets.UTF_8))); System.out.println("压缩后的字节数组："+Arrays.toString(encode.getData())); System.out.println("解压字典："+encode.getMap()); System.out.println(s); } //结果输出 原始字节数组：[-27, -109, -120, -27, -109, -120, 44, -26, -120, -111, -26, -104, -81, -26, -75, -117, -24, -81, -107, -24, -81, -83, -27, -113, -91, -17, -68, -116, -27, -107, -90, -27, -107, -90, -27, -107, -90, -27, -107, -90, -27, -107, -90, -27, -107, -90] 压缩后的字节数组：[47, 37, -25, -38, -97, -85, -72, -81, 23, -56, -36, -124, -120, -73, -3, 40, -52, -52, -52, -52, -52, 51] 解压字典：{-68=111010, -104=111011, -107=110, -75=111100, -109=10111, 44=111101, -111=111110, -113=01000, -81=1000, -17=111111, -83=01001, -116=01010, -117=01011, -120=1001, -24=11100, -90=011, -26=1010, -27=00, -91=10110} 哈哈,我是测试语句，啦啦啦啦啦啦 ``` ### 二叉排序树 #### 介绍 二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。 特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点 比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为： ![image-20210402163934624](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210402163934624.png) #### 二叉排序树的删除 二叉排序树的删除情况比较复杂，有下面三种情况需要考虑 1. 删除叶子节点 (比如：2, 5, 9, 12) 2. 删除只有一颗子树的节点 (比如：1) 3. 删除有两颗子树的节点. (比如：7, 3，10 ) ![image-20210402220053810](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210402220053810.png) 第一种情况:删除叶子节点 (比如：2, 5, 9, 12) 1. 需求先去找到要删除的结点 targetNode 2. 找到targetNode 的 父结点 parent 3. 确定 targetNode 是 parent的左子结点 还是右子结点 4. 根据前面的情况来对应删除 左子结点 parent.left = null 右子结点 parent.right = null; 第二种情况: 删除只有一颗子树的节点 比如 1 1. 需求先去找到要删除的结点 targetNode 2. 找到targetNode 的 父结点 parent 3. 确定targetNode 的子结点是左子结点还是右子结点 4. targetNode 是 parent 的左子结点还是右子结点 5. 如果targetNode 有左子结点 1. 如果 targetNode 是 parent 的左子结点parent.left = targetNode.left; 2. 如果 targetNode 是 parent 的右子结点parent.right = targetNode.left; 6. 如果targetNode 有右子结点 1. 如果 targetNode 是 parent 的左子结点parent.left = targetNode.right; 2. 如果 targetNode 是 parent 的右子结点parent.right = targetNode.right 情况三 ： 删除有两颗子树的节点. (比如：7, 3，10 ) 1. 需求先去找到要删除的结点 targetNode 2. 找到targetNode 的 父结点 parent 3. 从targetNode 的右子树找到最小的结点 4. 用一个临时变量，将 最小结点的值保存 temp = 11 5. 删除该最小结点 6. targetNode.value = temp #### 代码实现 ```java package com.freedy.dataStructure.tree; import java.util.StringJoiner; /** * @author Freedy * @date 2021/4/2 16:41 */ public class BinarySortTree { private Node root; BinarySortTree(Integer rootVal) { root = new Node(rootVal); } public void changeRootVal(int val){ root.setData(val); } public void add(Integer val) { if (val != null) { Node node = new Node(val); root.add(node); } } public void print(TreeEnum mode) { switch (mode) { case preOrder -> root.preOrder(); case infixOrder -> root.infixOrder(); case postOrder -> root.postOrder(); default -> throw new RuntimeException("参数不正确"); } } public boolean del(int val){ Node target = root.search(val); if (target==null) return false; Node parent = root.searchParent(val); if (parent==null){ //表示要删除的是根节点 if (target.getLeftNode()==null&&target.getRightNode()==null){ //表示该树只有一个节点且是根节点，这是不能让其删除 throw new RuntimeException("binary sort tree can not be empty"); }else if (target.getLeftNode()==null&&target.getRightNode()!=null){ //要删除的节点只有右子树 root=root.getRightNode(); return true; }else if (target.getLeftNode()!=null&&target.getRightNode()==null){ //要删除的节点只有左子树 root=root.getLeftNode(); return true; }else if (target.getLeftNode()!=null&&target.getRightNode()!=null){ //要删除的节点是有两个子树 int minVal = delMinVal(target.getRightNode()); target.setData(minVal); return true; } }else { if (target.getLeftNode()==null&&target.getRightNode()==null){ //表示要删除的节点是叶子节点 if (parent.getLeftNode()!=null&&parent.getLeftNode().getData()==val){ parent.setLeftNode(null); return true; }else if (parent.getRightNode()!=null&&parent.getRightNode().getData()==val){ parent.setRightNode(null); return true; } }else if (target.getLeftNode()==null&&target.getRightNode()!=null){ //要删除的节点只有右子树 if (parent.getLeftNode()!=null&&parent.getLeftNode().getData()==val){ //要删的节点在parent的左子树 parent.setLeftNode(target.getRightNode()); return true; }else if (parent.getRightNode()!=null&&parent.getRightNode().getData()==val){ //要删的节点在parent的右子树 parent.setRightNode(target.getRightNode()); return true; } }else if (target.getLeftNode()!=null&&target.getRightNode()==null){ //要删除的节点只有左子树 if (parent.getLeftNode()!=null&&parent.getLeftNode().getData()==val){ //要删的节点在parent的左子树 parent.setLeftNode(target.getLeftNode()); return true; }else if (parent.getRightNode()!=null&&parent.getRightNode().getData()==val){ //要删的节点在parent的右子树 parent.setRightNode(target.getLeftNode()); return true; } }else if (target.getLeftNode()!=null&&target.getRightNode()!=null){ //要删除的节点是有两个子树 int minVal = delMinVal(target.getRightNode()); target.setData(minVal); return true; } } throw new RuntimeException("删除失败"); } /** * 找到排序二叉树中最小的值，并删除 */ private int delMinVal(Node node){ Node pre = null; while (node.getLeftNode()!=null){ pre=node; node=node.getLeftNode(); } Integer val = node.getData(); if (pre!=null){ pre.setLeftNode(null); }else { //表示node没有子节点，直接删除自己 Node parent = root.searchParent(val); if (parent.getLeftNode()!=null&& parent.getLeftNode().getData().equals(val)){ parent.setLeftNode(node.getRightNode()); }else if (parent.getRightNode()!=null&& parent.getRightNode().getData().equals(val)){ parent.setRightNode(node.getRightNode()); } } return val; } private static class Node { private Integer data; private Node leftNode; private Node rightNode; //*******************************CONSTRUCT********************************** public Node() { } public Node(Integer data) { this.data = data; } public Integer getData() { return data; } public void setData(Integer data) { this.data = data; } public Node getLeftNode() { return leftNode; } public void setLeftNode(Node leftNode) { this.leftNode = leftNode; } public Node getRightNode() { return rightNode; } public void setRightNode(Node rightNode) { this.rightNode = rightNode; } @Override public String toString() { return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]") .add("data=" + data) .add("leftNode=" + (leftNode == null ? "" : leftNode.hashCode())) .add("rightNode=" + (rightNode == null ? "" : rightNode.hashCode())) .toString(); } //***********************************END*************************************** /** * 添加节点 * 递归的形式添加节点，注意需要满足的二叉排序树的要求 */ public void add(Node node) { if (node == null) return; if (node.getData() < this.getData()) { //向左边比较 if (this.getLeftNode() == null) { //无节点 直接添加 this.setLeftNode(node); } else { //有节点 递归添加 this.getLeftNode().add(node); } } else { //向右边比较 if (this.getRightNode() == null) { //无节点 直接添加 this.setRightNode(node); } else { //有节点 递归添加 this.getRightNode().add(node); } } } /** * 查找结点 * @param val 要查找节点的值 * @return 节点 */ public Node search(int val) { if (val == this.data) { //找到就直接返回 return this; } else if (val < this.data) { //若果小于就去左节点继续查找 if (this.getLeftNode()!=null){ return this.getLeftNode().search(val); } } else { //若果大于就去右节点继续查找 if (this.getRightNode()!=null){ return this.getRightNode().search(val); } } return null; } /** * 返回要查找节点的父节点 */ public Node searchParent(int val){ if (this.getLeftNode()!=null&&this.getLeftNode().getData()==val || this.getRightNode()!=null&&this.getRightNode().getData()==val){ //找到其父节点 return this; }else { if (this.getData()>val){ //若果小于就去左节点继续查找 if (this.getLeftNode()!=null){ return this.getLeftNode().searchParent(val); } }else{ //若果大于就去右节点继续查找 if (this.getRightNode()!=null){ return this.getRightNode().searchParent(val); } } return null; } } /** * 前中后序遍历 */ public void preOrder() { System.out.println(this); if (leftNode != null) { leftNode.preOrder(); } if (rightNode != null) { rightNode.preOrder(); } } public void infixOrder() { if (leftNode != null) { leftNode.infixOrder(); } System.out.println(this); if (rightNode != null) { rightNode.infixOrder(); } } public void postOrder() { if (leftNode != null) { leftNode.postOrder(); } if (rightNode != null) { rightNode.postOrder(); } System.out.println(this); } public Boolean deleteNode(Integer data) { if (leftNode != null && leftNode.getData().equals(data)) { leftNode = null; return true; } if (rightNode != null && rightNode.getData().equals(data)) { rightNode = null; return true; } if (leftNode != null) { boolean left = leftNode.deleteNode(data); if (left) return true; } if (rightNode != null) { return rightNode.deleteNode(data); } return false; } } } ``` 测试 ```java public static void main(String[] args) { int[] arr={7,3,10,12,5,1,9,2,11}; BinarySortTree tree = new BinarySortTree(arr[0]); for (int i = 1; i < arr.length; i++) { tree.add(arr[i]); } tree.print(TreeEnum.infixOrder); tree.del(2); tree.del(5); tree.del(9); tree.del(12); tree.del(7); tree.del(3); tree.del(10); tree.del(1); System.out.println("============================="); tree.print(TreeEnum.infixOrder); } //运行结果 Node[data=1, leftNode=, rightNode=2093176254] Node[data=2, leftNode=, rightNode=] Node[data=3, leftNode=1854731462, rightNode=317574433] Node[data=5, leftNode=, rightNode=] Node[data=7, leftNode=885284298, rightNode=1389133897] Node[data=9, leftNode=, rightNode=] Node[data=10, leftNode=1534030866, rightNode=664223387] Node[data=11, leftNode=, rightNode=] Node[data=12, leftNode=824909230, rightNode=] ============================= Node[data=11, leftNode=, rightNode=] 进程已结束，退出代码为 0 ``` ### 平衡二叉树 看一个案例：给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST) ![image-20210402223117956](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210402223117956.png) 存在的问题分析: 1. 左子树全部为空，从形式上看，更像一个单链表. 2. 插入速度没有影响 3. 查询速度明显降低(因为需要依次比较), 不能发挥BST 的优势，因为每次还需要比较左子树，其查询速度比 单链表还慢 4. 解决方案-平衡二叉树(AVL) #### 介绍 1. 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。 2. 具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 #### 左旋转 ![image-20210404112758471](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404112758471.png) #### 右旋转 ![image-20210404113006633](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404113006633.png) #### 双旋转 假如一个树的结构如下图中左边的那颗树，那么进行右旋转后发现依然不是平衡二叉树，所以下面引入双旋转的方法来解决这种问题。 ![image-20210404121155242](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404121155242.png) 问题分析: 1. 当符号右旋转的条件时 2. 如果它的左子树的右子树高度大于它的左子树的高度 3. 先对当前这个结点的左节点进行左旋转 4. 在对当前结点进行右旋转的操作即可 #### 代码实现 ```java package com.freedy.dataStructure.tree; import java.util.StringJoiner; /** * 平衡二叉树 * * @author Freedy * @date 2021/4/2 22:47 */ public class AVLTree { private Node root; AVLTree(Integer rootVal) { root = new Node(rootVal); } public void changeRootVal(int val) { root.setData(val); } public void add(Integer val) { if (val != null) { Node node = new Node(val); root.add(node); } } public void print(TreeEnum mode) { switch (mode) { case preOrder -> root.preOrder(); case infixOrder -> root.infixOrder(); case postOrder -> root.postOrder(); default -> throw new RuntimeException("参数不正确"); } } public int height(TreeEnum mode) { int height; switch (mode) { case height -> height = root.height(); case leftHeight -> height = root.leftHeight(); case rightHeight -> height = root.rightHeight(); default -> throw new RuntimeException("参数不正确"); } return height; } public boolean del(int val) { Node target = root.search(val); if (target == null) return false; Node parent = root.searchParent(val); if (parent == null) { //表示要删除的是根节点 if (target.getLeftNode() == null && target.getRightNode() == null) { //表示该树只有一个节点且是根节点，这是不能让其删除 throw new RuntimeException("binary sort tree can not be empty"); } else if (target.getLeftNode() == null && target.getRightNode() != null) { //要删除的节点只有右子树 root = root.getRightNode(); return true; } else if (target.getLeftNode() != null && target.getRightNode() == null) { //要删除的节点只有左子树 root = root.getLeftNode(); return true; } else if (target.getLeftNode() != null && target.getRightNode() != null) { //要删除的节点是有两个子树 int minVal = delMinVal(target.getRightNode()); target.setData(minVal); return true; } } else { if (target.getLeftNode() == null && target.getRightNode() == null) { //表示要删除的节点是叶子节点 if (parent.getLeftNode() != null && parent.getLeftNode().getData() == val) { parent.setLeftNode(null); return true; } else if (parent.getRightNode() != null && parent.getRightNode().getData() == val) { parent.setRightNode(null); return true; } } else if (target.getLeftNode() == null && target.getRightNode() != null) { //要删除的节点只有右子树 if (parent.getLeftNode() != null && parent.getLeftNode().getData() == val) { //要删的节点在parent的左子树 parent.setLeftNode(target.getRightNode()); return true; } else if (parent.getRightNode() != null && parent.getRightNode().getData() == val) { //要删的节点在parent的右子树 parent.setRightNode(target.getRightNode()); return true; } } else if (target.getLeftNode() != null && target.getRightNode() == null) { //要删除的节点只有左子树 if (parent.getLeftNode() != null && parent.getLeftNode().getData() == val) { //要删的节点在parent的左子树 parent.setLeftNode(target.getLeftNode()); return true; } else if (parent.getRightNode() != null && parent.getRightNode().getData() == val) { //要删的节点在parent的右子树 parent.setRightNode(target.getLeftNode()); return true; } } else if (target.getLeftNode() != null && target.getRightNode() != null) { //要删除的节点是有两个子树 int minVal = delMinVal(target.getRightNode()); target.setData(minVal); return true; } } throw new RuntimeException("删除失败"); } /** * 找到排序二叉树中最小的值，并删除 */ private int delMinVal(Node node) { Node pre = null; while (node.getLeftNode() != null) { pre = node; node = node.getLeftNode(); } Integer val = node.getData(); if (pre != null) { pre.setLeftNode(null); } else { //表示node没有子节点，直接删除自己 Node parent = root.searchParent(val); if (parent.getLeftNode() != null && parent.getLeftNode().getData().equals(val)) { parent.setLeftNode(node.getRightNode()); } else if (parent.getRightNode() != null && parent.getRightNode().getData().equals(val)) { parent.setRightNode(node.getRightNode()); } } return val; } private static class Node { private Integer data; private Node leftNode; private Node rightNode; //*******************************CONSTRUCT********************************** public Node() { } public Node(Integer data) { this.data = data; } public Integer getData() { return data; } public void setData(Integer data) { this.data = data; } public Node getLeftNode() { return leftNode; } public void setLeftNode(Node leftNode) { this.leftNode = leftNode; } public Node getRightNode() { return rightNode; } public void setRightNode(Node rightNode) { this.rightNode = rightNode; } @Override public String toString() { return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]") .add("data=" + data) .add("leftNode=" + (leftNode == null ? "" : leftNode.hashCode())) .add("rightNode=" + (rightNode == null ? "" : rightNode.hashCode())) .toString(); } //***********************************END*************************************** /** * @return 返回当前节点下面的树的高度 */ public int height() { return Math.max(leftNode == null ? 0 : leftNode.height(), rightNode == null ? 0 : rightNode.height()) + 1; } public int leftHeight() { if (leftNode == null) return 0; return leftNode.height(); } public int rightHeight() { if (rightNode == null) return 0; return rightNode.height(); } /** * 左旋转 */ public void leftRotate() { //创建新的节点 Node node = new Node(data); //讲新的节点的左子树设置为当前节点的左子树 node.setLeftNode(this.getLeftNode()); //把新的节点的右子树设置为当前节点的*右子树的左子树* node.setRightNode(this.getRightNode().getLeftNode()); //把当前节点换成右子节点的值 this.setData(this.getRightNode().getData()); //把当前节点的右子树设置为当前节点的右子树的右子树 this.setRightNode(this.getRightNode().getRightNode()); //把当前节点的左子树设置为新的节点 this.setLeftNode(node); } /** * 右旋转 */ public void rightRotate(){ Node node = new Node(data); node.setLeftNode(this.getLeftNode().getRightNode()); node.setRightNode(this.getRightNode()); this.setData(this.getLeftNode().getData()); this.setRightNode(node); this.setLeftNode(this.getLeftNode().getLeftNode()); } /** * 添加节点 * 递归的形式添加节点，注意需要满足的二叉排序树的要求 */ public void add(Node node) { if (node == null) return; if (node.getData() < this.getData()) { //向左边比较 if (this.getLeftNode() == null) { //无节点 直接添加 this.setLeftNode(node); } else { //有节点 递归添加 this.getLeftNode().add(node); } } else { //向右边比较 if (this.getRightNode() == null) { //无节点 直接添加 this.setRightNode(node); } else { //有节点 递归添加 this.getRightNode().add(node); } } //当添加完一个节点后，如果 右子树的高度-左子树的高度>1,即右边比左边高所以要左旋转 if (this.rightHeight() - this.leftHeight() > 1) { if (this.getRightNode()!=null&&this.getRightNode().leftHeight()>this.getRightNode().rightHeight()){ this.getRightNode().rightRotate(); } leftRotate(); return; } //当添加完一个节点后，如果 左子树的高度-右子树的高度>1,即左边比右边高所以要右旋转 if(this.leftHeight()-this.rightHeight()>1){ //若果左子树的右子树的高度大于左子树的左子树的高度 if (this.getLeftNode()!=null&&this.getLeftNode().rightHeight()>this.getLeftNode().leftHeight()){ this.getLeftNode().leftRotate(); } rightRotate(); } } /** * 查找结点 * * @param val 要查找节点的值 * @return 节点 */ public Node search(int val) { if (val == this.data) { //找到就直接返回 return this; } else if (val < this.data) { //若果小于就去左节点继续查找 if (this.getLeftNode() != null) { return this.getLeftNode().search(val); } } else { //若果大于就去右节点继续查找 if (this.getRightNode() != null) { return this.getRightNode().search(val); } } return null; } /** * 返回要查找节点的父节点 */ public Node searchParent(int val) { if (this.getLeftNode() != null && this.getLeftNode().getData() == val || this.getRightNode() != null && this.getRightNode().getData() == val) { //找到其父节点 return this; } else { if (this.getData() > val) { //若果小于就去左节点继续查找 if (this.getLeftNode() != null) { return this.getLeftNode().searchParent(val); } } else { //若果大于就去右节点继续查找 if (this.getRightNode() != null) { return this.getRightNode().searchParent(val); } } return null; } } /** * 前中后序遍历 */ public void preOrder() { System.out.println(this); if (leftNode != null) { leftNode.preOrder(); } if (rightNode != null) { rightNode.preOrder(); } } public void infixOrder() { if (leftNode != null) { leftNode.infixOrder(); } System.out.println(this); if (rightNode != null) { rightNode.infixOrder(); } } public void postOrder() { if (leftNode != null) { leftNode.postOrder(); } if (rightNode != null) { rightNode.postOrder(); } System.out.println(this); } } } ``` ### 多路查找树 #### 二叉树的问题分析 二叉树的操作效率较高，但是也存在问题, 请看下面的二叉树 ![image-20210404124450768](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404124450768.png) 1. 二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如1亿)， 就存在如下问题: 2. 问题1：在构建二叉树时，需要多次进行i/o操作(海量数据存在数据库或文件中)，节点海量，构建二叉树时，速度有影响 3. 问题2：节点海量，也会造成二叉树的高度很大，会降低操作速度. #### 多叉树 1. 在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree） 2. 后面我们讲解的2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。 3. 举例说明(下面2-3树就是一颗多叉树) ![image-20210404124841610](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404124841610.png) ##### 2-3树基本介绍 2-3树是最简单的B树结构, 具有如下特点: 1. 2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件) 2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点. 3. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点. 4. 2-3树是由二节点和三节点构成的树。 ###### 2-3树的构成规则 1. 2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件) 2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点. 3. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点 4. 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。 5. 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则 ##### B树的基本介绍 B树通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率。 ![image-20210404125645809](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404125645809.png) 1. 如图B树通过重新组织节点， 降低了树的高度. 2. 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为4k)，这样每个节点只需要一次I/O就可以完全载入 3. 将树的度M设置为1024，在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素, B树(B+)广泛应用于文件存储系统以及数据库系统中 前面已经介绍了2-3树和2-3-4树，他们就是B树(英语：B-tree 也写成B-树)，这里我们再做一个说明，我们在学习Mysql时，经常听到说某种类型的索引是基于B树或者B+树的，如图: ![image-20210404132221500](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404132221500.png) B树的说明: 1. B树的阶：节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4 2. B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点 3. 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据. 4. 搜索有可能在非叶子结点结束 5. 其搜索性能等价于在关键字全集内做一次二分查找 ##### B+树的介绍 B+树是B树的变体，也是一种多路搜索树 ![image-20210404132755515](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404132755515.png) B+树的说明: 1. B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找 2. 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。 3. 不可能在非叶子结点命中 4. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层 5. 更适合文件索引系统 6. B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然. ##### B*树的介绍 B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。![image-20210404133525020](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404133525020.png) B*树的说明: 1. B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。 2. 从第1个特点我们可以看出，B*树分配新结点的概率比B+树要低，空间使用率更高 # 图 ## 图基本介绍 为什么要有图 1. 前面我们学了线性表和树 2. 线性表局限于一个直接前驱和一个直接后继的关系 3. 树也只能有一个直接前驱也就是父节点 4. 当我们需要表示多对多的关系时， 这里我们就用到了图 图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。 ## 图的表示方式 图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。 ### 邻接矩阵 邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。 ![image-20210404135649659](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404135649659.png) ### 邻接表 1. 邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失. 2. 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成 ![image-20210404135730847](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404135730847.png) - 标号为0的结点的相关联的结点为 1 2 3 4 - 标号为1的结点的相关联结点为0 4， - 标号为2的结点相关联的结点为 0 4 5 ## 图的遍历 所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历 ### 图的深度优先搜索(DFS) 。 1. 深度优先遍历(Depth First Search) ，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。 2. 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。 3. 显然，深度优先搜索是一个递归的过程 深度优先遍历算法的实现步骤： 1. 访问初始结点v，并标记结点v为已访问。 2. 查找结点v的第一个邻接结点w。 3. 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。 4. 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。 5. 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。 ### 图的广度优先遍历 图的广度优先搜索(Broad First Search) 。类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点 广度优先遍历算法步骤: 1. 访问初始结点v并标记结点v为已访问。 2. 结点v入队列 3. 当队列非空时，继续执行，否则算法结束。 4. 出队列，取得队头结点u。 5. 查找结点u的第一个邻接结点w。 6. 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤： - 若结点w尚未被访问，则访问结点w并标记为已访问。 - 结点w入队列 - 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。 ### 代码实现 ```java package com.freedy.dataStructure.graph; import java.util.*; /** * 邻接矩阵实现图 * * @author Freedy * @date 2021/4/4 14:01 */ public class AdjacencyMatrixGraph { private final List vertexList;//存储顶点的集合 private final int[][] edges;//存储图的邻接矩阵 private final boolean[] isVisited; private int numOfEdge;//边的数目 public AdjacencyMatrixGraph(int n) { vertexList = new ArrayList<>(n); edges = new int[n][n]; isVisited = new boolean[n]; numOfEdge = 0; } public void insertVertex(String vertex) { vertexList.add(vertex); } /** * 添加边 * * @param v1 第一个顶点的下标 * @param v2 第二个顶点的下标 * @param weight 权值 */ public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdge++; } /** * @return 节点的个数 */ public int size() { return vertexList.size(); } /** * @return 返回边的数目 */ public int getNumOfEdge() { return numOfEdge; } /** * @param i 索引 * @return 指定索引所对应的数据 */ public String getValueByIndex(int i) { return vertexList.get(i); } /** * @param v1 第一个顶点的下标 * @param v2 第二个顶点的下标 * @return 两点之间的权值 */ public int getWight(int v1, int v2) { return edges[v1][v2]; } /** * 打印图 */ public void printGraph() { for (int i = -1; i < edges.length; i++) { for (int j = -1; j < edges.length; j++) { if (i == -1) { System.out.print(j == -1 ? " " : vertexList.get(j) + " "); } else { System.out.print(j == -1 ? vertexList.get(i) + " " : edges[i][j] + " "); } } System.out.println(); } } /** * 使用深度优先遍历的方法,来遍历图 */ public void DFS() { //重置isVisited数组 Arrays.fill(isVisited, false); //考虑到非联通图 需要对每个点进行深度遍历 for (int i = 0; i < vertexList.size(); i++) { if (!isVisited[i]) { DFS(i); } } System.out.println(); } /** * 使用广度优先遍历的方法,来遍历图 */ public void BFS(){ //重置isVisited数组 Arrays.fill(isVisited, false); //考虑到非联通图 需要对每个点进行深度遍历 for (int i = 0; i < vertexList.size(); i++) { if (!isVisited[i]) { BFS(i); } } System.out.println(); } /** * 深度优先遍历 */ private void DFS(int index) { isVisited[index] = true; System.out.print(vertexList.get(index) + "->"); for (int i = 0; i < edges.length; i++) { if (edges[index][i] != 0) { if (!isVisited[i]) { DFS(i); } } } } /** * 广度优先遍历 */ private void BFS(int index) { //队列，记录节点访问的顺序 LinkedList queue = new LinkedList<>(); isVisited[index] = true; System.out.print(vertexList.get(index)+"->"); queue.addLast(index); while (!queue.isEmpty()){ Integer pop = queue.pop(); for (int i = 0; i < edges.length; i++) { if (edges[pop][i] != 0) { if (!isVisited[i]) { isVisited[i] = true; System.out.print(vertexList.get(i)+"->"); queue.addLast(i); } } } } } } ``` 测试 ```java public static void main(String[] args) { String[] vertexVal ={"1","2","3","4","5","6","7","8"}; AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(vertexVal.length); for (String s : vertexVal) { graph.insertVertex(s); } //添加边 graph.insertEdge(0,1,1); graph.insertEdge(0,2,1); graph.insertEdge(1,3,1); graph.insertEdge(1,4,1); graph.insertEdge(3,7,1); graph.insertEdge(4,7,1); graph.insertEdge(2,5,1); graph.insertEdge(2,6,1); graph.insertEdge(5,6,1); graph.printGraph(); graph.DFS(); graph.BFS(); } ``` ![image-20210404185306896](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210404185306896.png) 测试的图的样例如上。 结果： ```java 1 2 3 4 5 6 7 8 1 0 1 1 0 0 0 0 0 2 1 0 0 1 1 0 0 0 3 1 0 0 0 0 1 1 0 4 0 1 0 0 0 0 0 1 5 0 1 0 0 0 0 0 1 6 0 0 1 0 0 0 1 0 7 0 0 1 0 0 1 0 0 8 0 0 0 1 1 0 0 0 1->2->4->8->5->3->6->7-> 1->2->3->4->5->6->7->8-> ``` # 常见10中算法 ## 二分查找算法(非递归) ### 二分查找算法(非递归)介绍 1. 前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式 2. 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找 3. 二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7) ### 代码实现 ```java /** * 二分查找非递归实现 * @param arr 要查找的数组 * @param target 要查找的值 * @return 找到的索引 */ public static int binarySearch(int[] arr,int target){ int left=0; int right=arr.length-1; while (left<=right){ int mid=(left+right)/2; if (arr[mid]==target){ return mid; }else if (arr[mid]>target){ right=mid-1;//向左查找 }else if (arr[mid]C 2. 如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘 - 先把 最上面的盘 A->B - 把最下边的盘 A->C - 把B塔的所有盘 从 B->C ![image-20210411213715039](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210411213715039.png) ### 代码实现 ```java public class HanoiTower { public static void main(String[] args) { hanoiTower(5,'A','B','C'); } /** * 汉洛塔 使用分治算法 * @param num 盘的数量 */ public static void hanoiTower(int num,char t1,char t2,char t3){ if (num==1){ System.out.println("第1个盘从 "+t1+"->"+t3); }else { //如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘所有 //- 先把 最上面的盘 A->B hanoiTower(num-1,t1,t3,t2); //- 把最下边的盘 A->C System.out.println("第"+num+"个盘从 "+t1+"->"+t3); //- 把B塔的所有盘 从 B->C hanoiTower(num-1,t2,t1,t3); } } } ``` ## 动态规划算法 ### 动态规划算法介绍 1. 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法 2. 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 3. 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 ) 4. 动态规划可以通过填表的方式来逐步推进，得到最优解 ### 动态规划算法最佳实践-背包问题 背包问题：有一个背包，容量为4磅 ， 现有如下物品 | **物品** | **重量** | **价格** | | -------- | -------- | -------- | | 吉他(G) | 1 | 1500 | | 音响(S) | 4 | 3000 | | 电脑(L) | 3 | 2000 | 1. 要求达到的目标为装入的背包的总价值最大，并且重量不超出 2. 要求装入的物品不能重复 思路分析: - 利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令valueTable[i] [j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果： ```java 1. v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0 2. 当w[i]> j 时：v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略 3. 当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 当 准备加入的新增的商品的容量小于等于当前背包的容量, // 装入的方式: v[i-1][j]： 就是上一个单元格的装入的最大值 v[i] : 表示当前商品的价值 v[i-1][j-w[i]] ： 装入i-1商品，到剩余空间j-w[i]的最大值 当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} : ``` 背包问题的图解 | 物品 | 0 磅 | 1磅 | 2磅 | 3磅 | 4磅 | | -------------- | -------------- | ------------- | ------------- | ------------- | ------------- | | | 0 | 0 | 0 | 0 | 0 | | 吉他(G) | 0 | 1500(G) | 1500(G) | 1500(G) | 1500(G) | | 音响(S) | 0 | 1500(G) | 1500(G) | 1500(G) | 3000(S) | | 电脑(L) | 0 | 1500(G) | 1500(G) | 2000(L) | 3500(L+G) | ### 代码实现 ```java public class BackPack { public static void main(String[] args) { int[] weight = {1, 4, 3}; int[] value = {1500, 3000, 2000}; int capacity = 4;//背包的容量 int n = value.length;//物品的数量 int[][] valueTable = new int[n + 1][capacity + 1]; int[][] path=new int[n + 1][capacity + 1]; //根据前面得到的公式动态规划处理 for (int i = 1; i < n + 1; i++) {//不处理第一行 for (int j = 1; j < capacity + 1; j++) {//不处理第一列 if (weight[i - 1] > j) { valueTable[i][j] = valueTable[i - 1][j];//表示放不下去，取上一行的最优解 } else { //表示可以放下去，比较上一行的最优解与 //上一行减去所需重量的最优解加上新加上去的物品的价值 //谁大就是本格的最优解 if ( valueTable[i - 1][j]>(value[i - 1] + valueTable[i - 1][j - weight[i - 1]])){ valueTable[i][j]=valueTable[i - 1][j]; }else { valueTable[i][j]= value[i - 1] + valueTable[i - 1][j - weight[i - 1]]; path[i][j]=1; } } } } for (int[] ints : valueTable) { System.out.println(Arrays.toString(ints)); } System.out.print("最优解为:装入"); for (int i = 0; i < path.length; i++) { if (path[i][path[i].length-1]==1) { System.out.print(i + "号 "); } } System.out.println("物品，总计价值:"+valueTable[n][capacity]); } } ``` 运行结果 ```java [0, 0, 0, 0, 0] [0, 1500, 1500, 1500, 1500] [0, 1500, 1500, 1500, 3000] [0, 1500, 1500, 2000, 3500] 最优解为:装入1号 2号 3号 物品，总计价值:3500 ``` ## KMP算法 ### 应用场景-字符串匹配问题 1. 有一个字符串 str1= ""硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好""，和一个子串 str2="尚硅谷你尚硅你" 2. 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1 #### 不使用kmp，而使用暴力匹配算法 如果用暴力匹配的思路，并假设现在str1匹配到 i 位置，子串str2匹配到 j 位置，则有: 1. 如果当前字符匹配成功（即str1[i] == str2[j]），则i++，j++，继续匹配下一个字符 2. 如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。 3. 用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。(不可行!) 4. 暴力匹配算法实现. ```java public class ViolenceMatch { public static void main(String[] args) { String a="I LOVE YOU SO MUCH"; String b=" SO "; System.out.println(violenceMatch(a,b)); } public static int violenceMatch(String str1, String str2) { char[] cs1 = str1.toCharArray(); char[] cs2 = str2.toCharArray(); int i=0; int j=0; while (i0&&str1.charAt(i)!=str2.charAt(j)){ j=next[j-1]; } if (str1.charAt(i)==str2.charAt(j)){ j++; } if (j==str2.length()){ return i-j+1;//找到了 } } return -1; } /** * 获取一个字符串的部分匹配值 * @param dest 字串 * @return 匹配表 */ public static int[] kmpNext(String dest) { int[] next = new int[dest.length()]; next[0] = 0;//如果字符串的长度为一，部分匹配值为0 for (int i = 1, j = 0; i < dest.length(); i++) { //条件满足时,部分匹配值就要+1 while (j > 0 && dest.charAt(i) != dest.charAt(j)) { j = next[j - 1]; } if (dest.charAt(i) == dest.charAt(j)) { j++; } next[i] = j; } return next; } } ``` ## 贪心算法 ### 贪心算法介绍 1. 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法 2. 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果 ### 贪心算法最佳应用-集合覆盖 假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号 | 广播台 | 覆盖地区 | | ------ | ---------------------- | | K1 | "北京", "上海", "天津" | | K2 | "广州", "北京", "深圳" | | K3 | "成都", "上海", "杭州" | | K4 | "上海", "天津" | | K5 | "杭州", "大连" | 思路分析: - 如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有 2ⁿ -1 个,假设每秒可以计算10个子集， 如图: | 广播台数量n | 子集总数2ⁿ | 需要的时间 | | ----------- | ---------- | ---------- | | 5 | 32 | 3.2秒 | | 10 | 1024 | 102.4秒 | | 32 | 4294967296 | 13.6年 | | 100 | 1.26*100³º | 4x10²³年 | - 使用贪婪算法，效率高:目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合: 1. 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系） 2. 将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。 3. 重复第1步直到覆盖了全部的地区 ### 代码实现 ```java import java.util.*; /** * @author Freedy * @date 2021/4/12 21:07 */ public class GreedyAlgorithm { public static void main(String[] args) { //创建广播电台，放入到map HashMap> broadCasts = init(); HashSet allAreas = new HashSet<>(); for (Map.Entry> entry : broadCasts.entrySet()) { allAreas.addAll(entry.getValue()); } ArrayList result = new ArrayList<>(); while (!allAreas.isEmpty()){ //每个电台覆盖了未覆盖的地区的电台的数量 HashMap selects = new HashMap(); for (Map.Entry> entry : broadCasts.entrySet()) { selects.put(entry.getKey(),0); for (String s : entry.getValue()) { if (allAreas.contains(s)){ selects.merge(entry.getKey(),1,Integer::sum); } } } int max=Integer.MIN_VALUE; String index=""; for (Map.Entry entry : selects.entrySet()) { if (entry.getValue()>max){ max=entry.getValue(); index=entry.getKey(); } } HashSet set = broadCasts.get(index); allAreas.removeAll(set); result.add(index); } System.out.println(result); } public static HashMap> init(){ HashMap> broadCasts = new HashMap<>(); HashSet set1 = new HashSet<>(); set1.add("北京"); set1.add("上海"); set1.add("天津"); HashSet set2 = new HashSet<>(); set2.add("广州"); set2.add("北京"); set2.add("深圳"); HashSet set3 = new HashSet<>(); set3.add("成都"); set3.add("上海"); set3.add("杭州"); HashSet set4 = new HashSet<>(); set4.add("上海"); set4.add("天津"); HashSet set5 = new HashSet<>(); set5.add("杭州"); set5.add("大连"); broadCasts.put("k1",set1); broadCasts.put("k2",set2); broadCasts.put("k3",set3); broadCasts.put("k4",set4); broadCasts.put("k5",set5); return broadCasts; } } //运行结果 //[k1, k2, k3, k5] ``` 贪心算法注意事项和细节： 1. 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果 2. 比如上题的算法选出的是K1, K2, K3, K5，符合覆盖了全部的地区 3. 但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果K2 的使用成本低于K1,那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的. ## 普里姆算法 看一个应用场景和问题： ![image-20210413213404154](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210413213404154.png) 1. 有胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通 2. 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里 3. 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短? 思路: 将10条边，连接即可，但是总的里程数不是最小. 正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少. ### 最小生成树 修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。 1. 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树 2. N个顶点，一定有N-1条边 3. 包含全部顶点 4. N-1条边都在图中 5. 举例说明(如图:) 6. 求最小生成树的算法主要是普里姆 算法和克鲁斯卡尔算法 ![image-20210413213808821](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210413213808821.png) ### 普里姆算法介绍 1. 普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图 2. 普利姆的算法如下: 3. 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合 4. 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1 5. 若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited[vj]=1 6. 重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边 ![image-20210413225733197](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210413225733197.png) > 简单而言：先随便取一个点，然后找到离这个点最近那个点，然后把这个点加入，并把这两个点当作一个整体（这是有两个点）。然后再次找离这个整体最近的点，然后加入这个整体（这是总共有3个点）。然后继续上面的操作，直到所有的点都找遍历完，这时可以得出最小生成树。即每个点加入的顺序就是生成树的顺序。例如上面那幅图生成最小生成树的次序就是 > > A->G 距离:2 > G->B 距离:3 > G->E 距离:4 > E->F 距离:5 > F->D 距离:4 > A->C 距离:7 ### 代码实现 图类： ```java public class MGraph { int verxs;//节点的个数 char[] data;//存放在节点的数据 int[][] weight;//存放边，就是我们的邻接矩阵 public MGraph(char[] data,int[][] weight) { if (data.length!=weight.length||weight[0].length!=weight.length) throw new RuntimeException("传入的数据不匹配!"); this.verxs = data.length; this.data=data; this.weight=weight; } public void printGraph(){ for (int i = -1; i < weight.length; i++) { for (int j = -1; j < weight[0].length; j++) { if (i==-1){ System.out.print(j==-1?" ":data[j]+" "); }else if (j==-1){ System.out.print(data[i]+" "); } else { System.out.print(weight[i][j]+" "); } } System.out.println(); } } } ``` 最小生成树类： ```java public class MinTree { private MGraph graph; public MinTree(MGraph graph) { this.graph = graph; } public void createMinTree() { System.out.println("生成最小生成树"); int[] visited = new int[graph.verxs];//标记节点是否被访问 visited[0] = 1; int index1 = -1, index2 = -1;//记录最小距离两点的下标 int minWeight ;//两点间的最小距离 for (int i = 1; i < graph.verxs; i++) {//有verxs个点->最小生成树有verxs-1条边 minWeight=Integer.MAX_VALUE;//每次循环重置minWeight //确定每一次生成的子图，和哪个节点的距离最近 for (int j = 0; j < graph.verxs; j++) { for (int k = 0; k < graph.verxs; k++) { if (visited[j] == 1 && visited[k] == 0 && graph.weight[j][k] < minWeight && graph.weight[j][k] != 0) {//0代表无穷远或者无穷近 minWeight=graph.weight[j][k]; index1=j; index2=k; } } } visited[index2]=1; System.out.println(graph.data[index1]+"->"+graph.data[index2]+" 距离:"+graph.weight[index1][index2]); } } } ``` 测试 ```java public class PrimAlgorithm { public static void main(String[] args) { char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int[][] weight ={ {0, 5, 7, 0, 0, 0, 2}, {5, 0, 0, 9, 0, 0, 3}, {7, 0, 0, 0, 8, 0, 0}, {0, 9, 0, 0, 0, 4, 0}, {0, 0, 8, 0, 0, 5, 4}, {0, 0, 0, 4, 5, 0, 6}, {2, 3, 0, 0, 4, 6, 0} }; MGraph graph = new MGraph(data,weight); graph.printGraph(); MinTree tree = new MinTree(graph); tree.createMinTree(); } } 结果如下: /** A B C D E F G A 0 5 7 0 0 0 2 B 5 0 0 9 0 0 3 C 7 0 0 0 8 0 0 D 0 9 0 0 0 4 0 E 0 0 8 0 0 5 4 F 0 0 0 4 5 0 6 G 2 3 0 0 4 6 0 生成最小生成树 A->G 距离:2 G->B 距离:3 G->E 距离:4 E->F 距离:5 F->D 距离:4 A->C 距离:7 进程已结束，退出代码为 0 **/ ``` ## 克鲁斯卡尔算法 ### 克鲁斯卡尔算法介绍 1. 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。 2. 基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路 3. 具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止 ### 分析 现在就以下图来演示如何使用克鲁斯卡尔算法来构成最小生成树 ![image-20210414092741102](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210414092741102.png) - 第1步：将边加入R中。 边的权值最小，因此将它加入到最小生成树结果R中。 - 第2步：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。 - 第3步：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。 - 第4步：将边加入R中。 上一步操作之后，边的权值最小，但会和已有的边构成回路；因此，跳过边。同理，跳过边。将边加入到最小生成树结果R中。 - 第5步：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。 - 第6步：将边加入R中。 上一步操作之后，边的权值最小，但会和已有的边构成回路；因此，跳过边。同理，跳过边。将边加入到最小生成树结果R中。 此时，最小生成树构造完成！它包括的边依次是： 。 根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题： ***\*问题一\**** 对图的所有边按照权值大小进行排序。 ***\*问题二\**** 将边添加到最小生成树中时，怎么样判断是否形成了回路。 问题一很好解决，采用排序算法进行排序即可。 问题二，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 ![image-20210414093003294](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210414093003294.png) 在将 加入到最小生成树R中之后，这几条边的顶点就都有了终点： >***(01)*** C的终点是F。 >***(02)*** D的终点是F。 >***(03)*** E的终点是F。 >***(04)*** F的终点是F。 关于终点的说明： 1. 就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 2. 因此，接下来，虽然是权值最小的边。但是C和E的终点都是F，即它们的终点相同，因此，将加入最小生成树的话，会形成回路。这就是判断回路的方式。也就是说，***\*我们加入的\*******\*边\*******\*的\*******\*两个顶点\*******\*不能\*******\*都指向同一个终点\*******\*，否则将构成回路\****。【后面有代码说明】 ### 代码实现 图类： ```java /** * @author Freedy * @date 2021/4/13 21:50 */ public class MGraph { private final int edgeNum;//节点的个数 private final char[] data;//存放在节点的数据 private final int[][] weight;//存放边，就是我们的邻接矩阵 private final ArrayList edges; public MGraph(char[] data, int[][] weight) { if (data.length != weight.length || weight[0].length != weight.length) throw new RuntimeException("传入的数据不匹配!"); edges = new ArrayList<>(); for (int i = 0; i < weight.length; i++) { for (int j = 0; j < weight[i].length; j++) { if (weight[i][j] > 0 && i >= j) { edges.add(new Edge(i,j,data[i],data[j], weight[i][j])); } } } this.data = data; this.weight = weight; edgeNum=edges.size(); edges.sort(Comparator.comparingInt(Edge::getWeight)); } public void printGraph() { for (int i = -1; i < weight.length; i++) { for (int j = -1; j < weight[0].length; j++) { if (i == -1) { System.out.print(j == -1 ? " " : data[j] + " "); } else if (j == -1) { System.out.print(data[i] + " "); } else { System.out.print(weight[i][j] + ((weight[i][j] + "").length() == 1 ? " " : " ")); } } System.out.println(); } } /** * 求出给定点的终点 * @param ends 该数组的下标表示第一个点里面的值表示他的下一个点 * 例如：3的下一个点是2，这时ends[3]就等于2， * 以此类推可以得到这个点的终点 * @param i 给定点的下标 * @return 终点下标 */ public int getEnd(int[] ends,int i){ while (ends[i]!=0){ i=ends[i]; } return i; } //=====================getter====================== public int getEdgeNum() { return edgeNum; } public char[] getData() { return data; } public int[][] getWeight() { return weight; } public ArrayList getEdges() { return edges; } public static class Edge { private final int start; private final int end; private final char startPoint; private final char endPoint; private final int weight; public Edge(int start, int end,char startPoint,char endPoint ,int weight) { this.start = start; this.end = end; this.startPoint=startPoint; this.endPoint=endPoint; this.weight = weight; } @Override public String toString() { return new StringJoiner(", ", Edge.class.getSimpleName() + "[", "]") .add("startPoint=" + startPoint) .add("endPoint=" + endPoint) .add("weight=" + weight) .toString(); } public int getStart() { return start; } public int getEnd() { return end; } public int getWeight() { return weight; } public char getStartPoint() { return startPoint; } public char getEndPoint() { return endPoint; } } } ``` 最小生成类： ```java /** * 创建最小生成树->村庄的图 * * @author Freedy * @date 2021/4/13 21:58 */ public class MinTree { private final MGraph graph; public MinTree(MGraph graph) { this.graph = graph; } public void createMinTree() { System.out.println("生成最小生成树"); //保存已被访问的点（就是已经生成的最小生成树）的下个点 int[] ends=new int[graph.getEdgeNum()]; //创建结果数组 ArrayList edges = graph.getEdges(); //遍历edges，将最小边添加到结果数组中，如果构成回路则不添加 for (MGraph.Edge edge : edges) { int start = edge.getStart(); int end = edge.getEnd(); //获取start在已有最小生成树中的终点 int m = graph.getEnd(ends, start); int n = graph.getEnd(ends, end); //没有构成回路 if (m != n) { //设置终点 ends[m] = n; //打印最小生成树 System.out.println(edge); } } } } ``` 测试： ```java /** * @author Freedy * @date 2021/4/14 9:32 */ public class Kruskal { public static void main(String[] args) { char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int[][] weight ={ { 0, 12, 0, 0, 0, 16, 14}, {12, 0, 10, 0, 0, 7, 0}, {0, 10, 0, 3, 5, 6, 0}, {0, 0, 3, 0, 4, 0, 0}, {0, 0, 5, 4, 0, 2, 8}, {16, 7, 6, 0, 2, 0, 9}, { 14, 0, 0, 0, 8, 9, 0}}; MGraph graph = new MGraph(data,weight); graph.printGraph(); MinTree tree = new MinTree(graph); tree.createMinTree(); } } /***********************运行结果************************* A B C D E F G A 0 12 0 0 0 16 14 B 12 0 10 0 0 7 0 C 0 10 0 3 5 6 0 D 0 0 3 0 4 0 0 E 0 0 5 4 0 2 8 F 16 7 6 0 2 0 9 G 14 0 0 0 8 9 0 生成最小生成树 Edge[startPoint=F, endPoint=E, weight=2] Edge[startPoint=D, endPoint=C, weight=3] Edge[startPoint=E, endPoint=D, weight=4] Edge[startPoint=F, endPoint=B, weight=7] Edge[startPoint=G, endPoint=E, weight=8] Edge[startPoint=B, endPoint=A, weight=12] Edge[startPoint=G, endPoint=A, weight=14] Edge[startPoint=F, endPoint=A, weight=16] */ ``` ## 迪杰斯特拉算法 ### 算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。 ### 算法过程 设置出发顶点为v，顶点集合V{v1,v2,vi...}，v到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,di...}，Dis集合记录着v到图中各顶点的距离(到自身可以看作0，v到vi距离对应为di) 1. 从Dis中选择值最小的di并移出Dis集合，同时移出V集合中对应的顶点vi，此时的v到vi即为最短路径 2. 更新Dis集合，更新规则为：比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为vi，表明是通过vi到达的) 3. 重复执行两步骤，直到最短路径顶点为目标顶点即可结束 ### 应用-最短路径 ![image-20210414154840804](C:\Users\Freedy\AppData\Roaming\Typora\typora-user-images\image-20210414154840804.png) 1. 战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄 2. 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里 3. 问：如何计算出G村庄到 其它各个村庄的最短距离? 4. 如果从其它点出发到各个点的最短距离又是多少?