1.线性表
1.1数组
概念
数组（Array）是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。
优缺点
优点：
数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素
缺点：
插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。 (ArrayList LinkedList )
申请的空间必须是连续的，也就是说即使有空间也可能因为没有足够的连续空间而创建失败如果超出范围，需要重新申请内存进行存储，原空间就浪费了
应用
数组是基础的数据结构，应用太广泛了，ArrayList、Redis、消息队列等等。
数据结构和算法的可视化网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
/**
* 数组
* @author yancheng
* @since 2024/2/1
*/
public class ArrayDemo1 {
int[] nums = new int[8];
public ArrayDemo1() {
nums[0] = 3;
nums[1] = 1;
nums[2] = 2;
nums[3] = 5;
nums[4] = 4;
nums[5] = 9;
}
public int get(int i) {
return nums[i];
}
public void update(int i, int n) {
nums[i] = n;
}
public void insertMiddle(int p, int n) {
for (int i = nums.length - 1; i >= p - 1; i--) {
//能取得值
if (nums[i] != 0) {
nums[i + 1] = nums[i];
}
}
nums[p - 1] = n;
}
/**
* 旧数组复制到新数组
*/
public void resize() {
int[] numsNew = new int[nums.length * 2];
System.arraycopy(nums, 0, numsNew, 0, nums.length);
nums = numsNew;
}
public void deleteMiddle(int p) {
for (int i = p; i < nums.length; i++) {
nums[i - 1] = nums[i];
}
}
public void display() {
for (int n : nums) {
System.out.println(n);
}
}
public static void main(String[] args) {
ArrayDemo1 demo1 = new ArrayDemo1();
demo1.resize();
demo1.insertMiddle(3,10);
demo1.deleteMiddle(4);
demo1.display();
}
}
1.2链表
概念
链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。
链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。（百度百科）
常见的链表包括：单链表、双向链表、循环链表
-
单链表
单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next
-
双向链表
双向链表的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。
-
循环链表
链表的尾节点指向头节点形成一个环，称为循环链表
优缺点
优势
插入、删除、更新效率高 ，省空间
劣势
查询效率较低，不能随机访问
应用
链表的应用也非常广泛，比如树、图、Redis的列表、LRU算法实现、消息队列等
数组与链表的对比
数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些
链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适一些
数组和链表是线性数据存储的物理存储结构：即顺序存储和链式存储。
/**
* 链表节点
*/
public class Node {
int id;
String name;
//下一个节点
Node next;
public Node(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Node{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
/**
* 单链表
*
* @author yancheng
* @since 2024/2/2
*/
public class SingleLinkedList {
//初始化头节点
private Node head = new Node(0, "");
/**
* 添加节点：从头插入
*
* @param node
*/
public void addNode(Node node) {
//从头插入
Node tmp = head;
while (true) {
//到尾节点
if (tmp.next == null) {
break;
}
//后移一个节点
tmp = tmp.next;
}
tmp.next = node;
}
public void addByIdOrder(Node node) {
//从头插入
Node tmp = head;
while (true) {
//到尾节点
if (tmp.next == null) {
break;
}
//节点存在
if (tmp.next.id == node.id) {
break;
}
if (tmp.next.id > node.id) {
break;
}
tmp = tmp.next;
}
//交换位置
node.next = tmp.next;
tmp.next = node;
}
//遍历链表
public void showList() {
//空链表
if (head.next == null) {
System.out.println("链表为空");
return;
}
Node temp = head.next;
while (true) {
if (temp == null) {
return;
}
System.out.println(temp);
//指针下移
temp = temp.next;
}
}
public static void main(String[] args) {
Node n1 = new Node(1, "张飞");
Node n2 = new Node(2, "关羽");
Node n3 = new Node(3, "赵云");
Node n4 = new Node(4, "黄忠");
Node n5 = new Node(5, "马超");
SingleLinkedList sll = new SingleLinkedList();
sll.addByIdOrder(n4);
sll.addByIdOrder(n5);
sll.addByIdOrder(n1);
sll.addByIdOrder(n2);
sll.addByIdOrder(n3);
sll.showList();
}
}
1.3栈
栈和队列都属于线性数据的逻辑存储结构
概念
栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。
最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶 （top）。
应用
- 函数调用
每进入一个函数，就会将临时变量作为一个栈入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈 - 浏览器的后退功能
我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了
数组实现
/**
* 栈--数组实现
*
* @author yancheng
* @since 2024/2/2
*/
public class ArrayStack {
private int[] nums; // 数组
private int count; // 栈中元素个数
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.nums = new int[n];
this.count = 0;
}
// 入栈操作
public boolean push(int n) {
// 数组空间不够了，直接返回false，入栈失败。 没有扩容
// nums.len*2 arraycopy
if (count >= nums.length) return false;
// 将item放到下标为count的位置，并且count加一
nums[count] = n;
count++;
return true;
}
// 出栈操作
public int pop() {
// 栈为空，则直接返回0
if (count == 0) return 0;
// 返回下标为count-1的数组元素，并且栈中元素个数count减一
int n = nums[count - 1];
count--;
return n;
}
public static void main(String[] args) {
ArrayStack as = new ArrayStack(8);
as.push(3);
as.push(5);
as.push(1);
as.push(4);
System.out.println(as.pop());
System.out.println(as.pop());
System.out.println(as.pop());
System.out.println(as.pop());
}
}
链表实现
/**
* 链表节点
* @author yancheng
* @since 2024/2/2
*/
public class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
}
}
/**
* 栈--链表实现
*
* @author yancheng
* @since 2024/2/2
*/
public class LinedStack {
int size;
Node head; //头节点
/**
* 初始化
*/
public LinedStack() {
head = null;
size = 0;
}
/**
* 入栈
*
* @param node
*/
public void push(Node node) {
//head
if (size == 0) {
head = node;
}
//非head
else {
node.next = head;
head = node;
}
size++;
}
/**
* 出栈
*
* @return Node
*/
public Node pop() {
if (size > 0) {
Node oldHead = head;
head = head.next;
size--;
return oldHead;
} else {
return null;
}
}
public static void main(String[] args) {
Node n1 = new Node(3);
Node n2 = new Node(5);
Node n3 = new Node(1);
Node n4 = new Node(4);
LinedStack ls = new LinedStack();
ls.push(n1);
ls.push(n2);
ls.push(n3);
ls.push(n4);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
}
}
1.4队列
概念
队列（queue）是一种线性数据结构，队列中的元素只能先入先出（First In First Out，简称 FIFO）。
队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。
应用
资源池、消息队列、命令队列等等
数组实现
/**
* 用数组实现的队列
*
* @author yancheng
* @since 2024/2/2
*/
public class ArrayQueue {
// 数组：items，数组大小：n
int[] nums;
// head表示队头下标，tail表示队尾下标
int head = 0;
int tail = 0;
// 申请一个大小为capacity的数组
public ArrayQueue(int size) {
nums = new int[size];
}
// 入队
public boolean enqueue(int n) {
// 如果tail == n 表示队列已经满了
if (tail == nums.length) return false;
nums[tail] = n;
++tail;
return true;
}
// 出队
public int dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) return 0;
int ret = nums[head];
++head;
return ret;
}
public static void main(String[] args) {
ArrayQueue aq = new ArrayQueue(8);
aq.enqueue(3);
aq.enqueue(5);
aq.enqueue(1);
aq.enqueue(4);
System.out.println(aq.dequeue());
System.out.println(aq.dequeue());
System.out.println(aq.dequeue());
System.out.println(aq.dequeue());
}
}
链表实现
/**
* 链表节点
* @author yancheng
* @since 2024/2/2
*/
public class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
}
}
/**
* 链表实现的队列
*
* @author yancheng
* @since 2024/2/2
*/
public class LinkedQueue {
//头
Node head;
//尾
Node tail;
int size;
/**
* 入队列
* @param node
*/
public void enqueue(Node node) {
if (tail == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
size++;
}
/**
* 出队列
* @return
*/
public Node dequeue() {
if (head == null) return null;
Node h = head;
//将拉取的节点的下一个节点变成新的表头
head = head.next;
//把旧的表头的下一个节点指向设置为null，让gc回收
h.next = null;
//队列为空
if (head == null)
tail = null;
size--;
return h;
}
public static void main(String[] args) {
Node n1 = new Node(3);
Node n2 = new Node(5);
Node n3 = new Node(1);
Node n4 = new Node(4);
LinkedQueue lq = new LinkedQueue();
lq.enqueue(n1);
lq.enqueue(n2);
lq.enqueue(n3);
lq.enqueue(n4);
System.out.println(lq.dequeue().value);
System.out.println(lq.dequeue().value);
System.out.println(lq.dequeue().value);
System.out.println(lq.dequeue().value);
}
}
2.散列表
概念
散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。
优缺点
优点：读写快
缺点：哈希表中的元素是没有被排序的、Hash冲突、扩容 重新计算
应用
-
HashMap
JDK1.7中HashMap使用一个table数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同，那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表，在极端情况下比如说所有key的hashcode都相同，将会导致这个链表会很长，那么put/get操作需要遍历整个链表，那么最差情况下时间复杂度变为O（n）。
扩容死链
针对JDK1.7中的这个性能缺陷，JDK1.8中的table数组中可能存放的是链表结构，也可能存放的是红黑树结构，如果链表中节点数量不超过8个则使用链表存储，超过8个会调用treeifyBin函数，将链表转换为红黑树。那么即使所有key的hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要O（logn）的开销。 -
字典
Redis字典dict又称散列表（hash），是用来存储键值对的一种数据结构。
Redis整个数据库是用字典来存储的。（K-V结构）
对Redis进行CURD操作其实就是对字典中的数据进行CURD操作。
Redis字典实现包括：字典(dict)、Hash表(dictht)、Hash表节点(dictEntry)。 -
布隆过滤器
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机hash映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法。
布隆过滤器的原理是，当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。 -
位图
Bitmap 的基本原理就是用一个 bit 来标记某个元素对应的 Value，而 Key 即是该元素。由于采用一个bit 来存储一个数据，因此可以大大的节省空间。
Java 中 int 类型占用 4 个字节，即 4 byte，又 1 byte = 8 bit。
试想以下，如果有一个很大的 int 数组，如 10000000，数组中每一个数值都要占用 4 个字节，则一共需要占用 10000000 * 4 = 40000000 个字节，即 40000000 / 1024.0 / 1024.0 = 38 M 如果使用 bit 来存放上述 10000000 个元素，只需要 10000000 个 bit 即可， 10000000 / 8.0 / 1024.0 / 1024.0 = 1.19 M 左右，可以看到 bitmap 可以大大的节约内存。
/**
* 结点
*/
public class Node {
String key;
String value;
//指向下一个结点
Node next;
public Node(String key, String value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
/**
* 单链表
*/
public class ListNode {
Node head; //头结点
/**
* 添加单链表结点
*
* @param key
* @param value
*/
public void addNode(String key, String value) {
//在外界设置好head了
if (head == null) return;
// 创建结点
Node node = new Node(key, value, null);
// 临时变量
Node tmp = head;
//循环单链表
while (true) {
//key相同覆盖值 从head开始
if(key.equals(tmp.key)){
tmp.value=value;
}
//是否是链表最后一个结点
if(tmp.next==null){
break;
}
//指向下一个
tmp=tmp.next;
}
//在循环外挂载最后一个结点
tmp.next=node;
}
/**
* 获得值
*
* @param key
* @return
*/
public String getVal(String key) {
if (head == null) return null;
//只有一个结点
if (head.next == null) {
return head.value;
}
//遍历单链表
else {
Node tmp = head;
while (tmp != null) {
//找到匹配的key
if (key.equals(tmp.key)) {
return tmp.value;
}
//指向下一个
tmp = tmp.next;
}
return null;
}
}
}
/**
* 手动HashMap
*/
public class MyHashMap {
//数组初始化 2的n次方
ListNode[] map = new ListNode[8];
//ListNode的个数
int size;
/**
* 设置值
*
* @param key
* @param value
*/
public void put(String key, String value) {
//该扩容了
if (size >= map.length * 0.75) {
System.out.println("map需要扩容");
return;
}
//计算索引 数组下标
int index = Math.abs(key.hashCode()) % map.length;
//获得该下标处的ListNode
ListNode ln = map[index];
//该下标处无值
if (ln == null) {
//创建单链表
ListNode lnNew = new ListNode();
//创建头结点
Node head = new Node(key, value, null);
//挂载头结点
lnNew.head = head;
//把单链放到数组里
map[index] = lnNew;
size++;
}
//该下标有值，hash碰撞
else {
//单链表挂结点
ln.addNode(key, value);
}
}
/**
* 取值
*
* @param key
* @return
*/
public String get(String key) {
int index = Math.abs(key.hashCode()) % map.length;
ListNode ln = map[index];
if (ln == null) return null;
return ln.getVal(key);
}
public static void main(String[] args) {
MyHashMap hashMap = new MyHashMap();
hashMap.put("m3", "cccccc");
hashMap.put("A", "AAAAAAAA");
hashMap.put("B", "BBBBBBBB");
hashMap.put("c1", "mmmmmmm");
System.out.println(hashMap.get("c1"));
}
}
3.递归
概念
递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。
递归三要素
- 递归结束条件
既然是循环就必须要有结束，不结束就会OOM了 - 函数的功能
这个函数要干什么，打印，计算… - 函数的等价关系式
递归公式，一般是每次执行之间，或者与个数之间的逻辑关系
打印5次 ‘‘Hello Worl’’
public class HelloWorld {
public static void printRa(String ss,int n){
//递归结束条件
if(n<=0) return ;
//函数功能
System.out.println(ss);
//调用自己，让参数趋近于递归结束条件
printRa(ss,n-1);
}
public static void main(String[] args) {
printRa("HelloWorld",5);
}
}
斐波那契数列：0、1、1、2、3、5、8、13、21、34、55…
规律：从第3个数开始，每个数等于前面两个数的和
递归分析：
函数的功能：返回n的前两个数的和
递归结束条件：从第三个数开始，n<=2
函数的等价关系式：fun(n)=fun(n-1)+fun(n-2)
/**
* 斐波那契数列
*/
public class Fiber {
public static int fun(int n){
// 递归结束条件
if(n<=1) return n;
//等价关系式 实现功能
return fun(n-1)+fun(n-2);
}
public static void main(String[] args) {
System.out.println(fun(9));
}
}
优缺点
优点：代码简单
缺点：占用空间较大、如果递归太深，可能会发生栈溢出、可能会有重复计算 通过备忘录或递归的方式去优化（动态规划）
应用
递归作为基础算法，应用非常广泛，比如在二分查找、快速排序、归并排序、树的遍历上都有使用递归
回溯算法、分治算法、动态规划中也大量使用递归算法实现
4.二分查找
概念
二分查找（Binary Search）算法，也叫折半查找算法
当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法
二分查找是针对有序数据集合的查找算法，如果是无序数据集合就遍历查找
本质
二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。
/**
* 二分法查找--在有序数组中找到某个数的位置
*/
public class HalfDemo1 {
public static int binarySerachComm(int[] nums, int n) {
//低位索引
int low = 0;
//高位索引
int high = nums.length - 1;
//中间索引
int mid = 0;
//可查找
while (low <= high) {
mid = (low + high) / 2;
if (n == nums[mid]) {
return mid;
} else if (n > nums[mid]) {
low = mid + 1;
}
// n<nums[mid]
else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 7, 9, 12, 15, 18, 20};
System.out.println(binarySerachComm(nums, 7));
}
}
/**
* 用递归的方式实现二分查找
*/
public class HalfDemo2 {
/**
* 查找
*
* @param nums 有序数组
* @param num 数字的最大个数
* @param n 要找的数
* @return
*/
public static int binarySearchRa(int[] nums, int num, int n) {
return bsearchUnit(nums, 0, num - 1, n);
}
private static int bsearchUnit(int[] nums, int low, int high, int n) {
//没找到
if (low > high) return -1;
int mid = (low + high) / 2;
//找到了
if (nums[mid] == n) {
return mid;
}
//low -->right
else if (nums[mid] < n) {
return bsearchUnit(nums, mid + 1, high, n);
}
//high --->left
else {
return bsearchUnit(nums, low, mid - 1, n);
}
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 7, 9, 12, 15, 18, 20};
System.out.println(binarySearchRa(nums, nums.length, 18));
}
}
经典案例
一个有序数组有一个数出现1次，其他数出现2次，找出出现一次的数
比如：1 1 2 2 3 3 4 4 5 5 6 6 7 出现1次的数是7
public class HalfDemo3 {
public static int binarySearch(int[] nums) {
int low = 0; //低位
int high = nums.length - 1; //高位
int mid; //中间
while (low < high) {
mid = (low + high) / 2;
//偶数位
if (mid % 2 == 0) {
// 跟后面的比相等
if (nums[mid] == nums[mid + 1]) {
//前面的对，向后折半查
low = mid + 1;
}
//跟前面的比相同
else if (mid > 0 && nums[mid] == nums[mid - 1]) {
//后面的都对，向前折半查找
high = mid - 1;
} else {
return nums[mid];
}
}
//奇数位
else {
// 跟后面的比相等
if (nums[mid] == nums[mid + 1]) {
//后面的对，向前折半查
high = mid - 1;
}
//跟前面的比相同
else if (nums[mid] == nums[mid - 1]) {
//前面的都对，向后折半查找
low = mid + 1;
} else {
return nums[mid];
}
}
}
return nums[low];
}
public static void main(String[] args) {
int[] nums = {1, 1, 2, 2, 3, 3, 6};
System.out.println(binarySearch(nums));
}
}
优缺点
优点：速度快，不占空间，不开辟新空间
缺点：必须是有序的数组，数据量太小没有意义，但数据量也不能太大，因为数组要占用连续的空间
应用
有序的查找都可以使用二分法。
如何快速定位出一个 IP 地址的归属地？
如果 IP 区间与归属地的对应关系不经常更新，我们可以先预处理这 12 万条数据，让其按照起始 IP 从小到大排序。如何来排序呢？我们知道，IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。
当我们要查询某个 IP 归属地时，我们可以先通过二分查找，找到最后一个起始 IP 小于等于这个 IP 的IP 区间，然后，检查这个 IP 是否在这个 IP 区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到
5.树
概念
有很多数据的逻辑关系并不是线性关系，在实际场景中，常常存在着一对多，甚至是多对多的情况。
树的分类如下：
5.1二叉树
二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。
-
满二叉树
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树
-
完全二叉树
对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树
满二叉树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前的节点都齐全即可
5.2二叉查找树
二叉查找树(binary search tree)，二叉查找树在二叉树的基础上增加了以下几个条件：
如果左子树不为空，则左子树上所有节点的值均小于根节点的值
如果右子树不为空，则右子树上所有节点的值均大于根节点的值
左、右子树也都是二叉查找树
二叉查找树要求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性。
因此二叉查找树还有另一个名字——二叉排序树（binary sort tree）。
5.3二叉树的遍历
二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。
二叉树的遍历包括
-
深度优先遍历
所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。它包括：
前序遍历
二叉树的前序遍历，输出顺序是根节点、左子树、右子树
步骤如下：
1、首先输出的是根节点1
2、由于根节点1存在左孩子，输出左孩子节点2
3、由于节点2也存在左孩子，输出左孩子节点4
4、节点4既没有左孩子，也没有右孩子，那么回到节点2，输出节点2的右孩子节点5
5、节点5既没有左孩子，也没有右孩子，那么回到节点1，输出节点1的右孩子节点3
6、节点3没有左孩子，但是有右孩子，因此输出节点3的右孩子节点6
到此为止，所有的节点都遍历输出完毕
中序遍历
二叉树的中序遍历，输出顺序是左子树、根节点、右子树
步骤如下：
1、首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不
再有左孩子 的节点，并输出该节点。显然，第一个没有左孩子的节点是节点4
2、依照中序遍历的次序，接下来输出节点4的父节点2
3、再输出节点2的右孩子节点5
4、以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的根节点1
5、由于节点3没有左孩子，所以直接输出根节点1的右孩子节点3
6、最后输出节点3的右孩子节点6
到此为止，所有的节点都遍历输出完毕
后序遍历
二叉树的后序遍历，输出顺序是左子树、右子树、根节点
步骤如下：
1、首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不
再有左孩子 的节点，并输出该节点。显然，第一个没有左孩子的节点是节点4
2、输出右节点5
3、输出节点4的父节点2
4、以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的右子树
5、访问根节点的右孩子，如果这个右孩子拥有左孩子，则继续深入访问下去，一直找到不再有左
孩子 的节点，如果没有左孩子则找右孩子，并输出该节点6
6、输出节点6的父节点3
到此为止，所有的节点都遍历输出完毕 -
广度优先遍历
也叫层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。
二叉树同一层次的节点之间是没有直接关联的，利用队列可以实现
/**
* 树的节点
*/
public class TreeNode {
//值
int data;
//左孩子
TreeNode leftChild;
//右孩子
TreeNode rightChild;
public TreeNode(int data) {
this.data = data;
}
}
/**
* 二叉查找树
*/
public class BinarySerachTree {
//根节点
TreeNode root;
//插入数据
public void insertNode(int data){
root=insert(root,data);
}
//递归插入节点
private TreeNode insert(TreeNode node, int data){
//结束条件
if(node==null) return new TreeNode(data);
//左孩子
if(data<node.data){
node.leftChild=insert(node.leftChild,data);
}
//右孩子
else if(data>node.data){
node.rightChild=insert(node.rightChild,data);
}
//自己
else{
node.data=data;
}
return node;
}
/**
* 前序遍历--递归 父 左 右
*/
public void beforeTraver(TreeNode node){
//结束条件
if(node==null) return ;
System.out.println(node.data); //节点
beforeTraver(node.leftChild); //左孩子
beforeTraver(node.rightChild); //右孩子
}
/**
* 中序遍历 左 父 右
* @param node
*/
public void midTraver(TreeNode node){
//结束条件
if(node==null) return ;
midTraver(node.leftChild);
System.out.println(node.data);
midTraver(node.rightChild);
}
/**
* 后序遍历 左 父 右
* @param node
*/
public void afterTraver(TreeNode node){
//结束条件
if(node==null) return ;
afterTraver(node.leftChild);
afterTraver(node.rightChild);
System.out.println(node.data);
}
/**
* 广度遍历
* @param root
*/
public void levelTraver(TreeNode root){
//队列
Queue<TreeNode> queue=new LinkedList<>();
//从队尾入队
queue.offer(root);
//队列不为空
while(!queue.isEmpty()){
//出队 队头出并删除
TreeNode node=queue.poll();
System.out.println(node.data);
//左孩子入队
if(node.leftChild!=null){
queue.offer(node.leftChild);
}
//右孩子入队
if(node.rightChild!=null){
queue.offer(node.rightChild);
}
}
}
public static void main(String[] args) {
BinarySerachTree bst=new BinarySerachTree();
bst.insertNode(10);
bst.insertNode(8);
bst.insertNode(11);
bst.insertNode(7);
bst.insertNode(9);
bst.insertNode(12);
bst.beforeTraver(bst.root);
System.out.println("===========================");
bst.midTraver(bst.root);
System.out.println("=============================");
bst.afterTraver(bst.root);
System.out.println("==============================");
bst.levelTraver(bst.root);
}
}
时间复杂度
二叉查找树的插入和查找时间复杂度为:O(logn)
极端情况下二叉查找树退化成链表，时间复杂度为O(n)，所以需要平衡二叉查找树。
应用
非线性数据：菜单，组织结构、家谱等等
线性数据：二叉查找树
二叉查找树是有序的，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
二叉查找树的性能非常稳定，扩容很方便(链表实现)
5.4红黑树
平衡二叉查找树
这种二叉查找树就退化成了链表，由于树的深度变得多了，查找的效率也会大幅下降
所以需要对这种二叉树进行自平衡，红黑树就是一种自平衡的二叉查找树。
红黑树（Red Black Tree）
除了二叉查找树(BST)的特征外，还有以下特征：
- 每个节点要么是黑色，要么是红色
- 根节点是黑色
- 每个叶子节点都是黑色的空结点（NIL结点）（为了简单期间，一般会省略该节点）
- 如果一个节点是红色的，则它的子节点必须是黑色的（父子不能同为红）
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点（平衡的关键）
- 新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡
一颗典型的红黑树：
在对红黑树进行添加或者删除操作时可能会破坏这些特点，所以红黑树采取了很多方式来维护这些特点，从而维持平衡。主要包括：左旋转、右旋转和颜色反转
左旋（RotateLeft）
逆时针旋转红黑树的两个结点，使得父结点被自己的右孩子取代，而自己成为自己的左孩子
上图所示过程如下：
- 以X为基点逆时针旋转
- X的父节点被x原来的右孩子Y取代
- c保持不变
- Y节点原来的左孩子c变成X的右孩子
右旋（RotateRight）
顺时针旋转红黑树的两个结点，使得父结点被自己的左孩子取代，而自己成为自己的右孩子
上图所示过程如下：
5. 以X为基点顺时针旋转
6. X的父节点被x原来的左孩子Y取代
7. b保持不变
8. Y节点原来的右孩子c变成X的左孩子
颜色反转
就是当前节点与父节点、叔叔节点同为红色，这种情况违反了红黑树的规则，需要将红色向祖辈上传，父节点和叔叔节点红色变为黑色，爷爷节点从黑色变为红色（爷爷节点必为黑色，因为此前是符合红黑树规则的）。这样每条叶子结点到根节点的黑色节点数量并未发生变化，因此都其他树结构不产生影响
/**
* 红黑树结点
*/
public class RBTreeNode {
private int key;
private boolean isBlack;
private RBTreeNode left;
private RBTreeNode right;
private RBTreeNode parent;
public RBTreeNode(int key) {
this.key = key;
isBlack = false;// 新增节点默认为红色
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public boolean isBlack() {
return isBlack;
}
public void setBlack(boolean black) {
isBlack = black;
}
public RBTreeNode getLeft() {
return left;
}
public void setLeft(RBTreeNode left) {
this.left = left;
}
public RBTreeNode getRight() {
return right;
}
public void setRight(RBTreeNode right) {
this.right = right;
}
public RBTreeNode getParent() {
return parent;
}
public void setParent(RBTreeNode parent) {
this.parent = parent;
}
@Override
public String toString() {
return "RBTreeNode{" + "key=" + key + ", isBlack=" + (isBlack == true ? "BLACK" : "RED") + '}';
}
}
/**
* 红黑树
*/
public class RBTree {
RBTreeNode root;//根节点
/**
* 遍历节点
*
* @param node
*/
public void list(RBTreeNode node) {
if (node == null)
return;
//递归终止条件
if (node.getLeft() == null && node.getRight() == null) {
System.out.println(node);
return;
}
System.out.println(node);
list(node.getLeft());
list(node.getRight());
}
/**
* 插入节点
*
* @param key
*/
public void insert(int key) {
RBTreeNode node = new RBTreeNode(key);
//插入根节点
if (root == null) {
node.setBlack(true);//根是黑的
root = node;
return;
}
RBTreeNode parent = root;
RBTreeNode son = null;
//左孩子
if (key <= parent.getKey()) {
son = parent.getLeft();
}
//右孩子
else {
son = parent.getRight();
}
//递归查找
while (son != null) {
parent = son;
if (key <= parent.getKey()) {
son = parent.getLeft();
} else {
son = parent.getRight();
}
}
//添加左孩子
if (key <= parent.getKey()) {
parent.setLeft(node);
}
//添加右孩子
else {
parent.setRight(node);
}
node.setParent(parent);
//自平衡
balanceInsert(node);
}
/**
* 插入自平衡
*
* @param node
*/
private void balanceInsert(RBTreeNode node) {
RBTreeNode father, gFather;
//父节点是红的
while ((father = node.getParent()) != null && father.isBlack() == false) {
gFather = father.getParent();
//父节点在祖父节点的左边
if (gFather.getLeft() == father) {
RBTreeNode uncle = gFather.getRight();
if (uncle != null && uncle.isBlack() == false) {
//颜色反转
setBlack(father);
setBlack(uncle);
setRed(gFather);
node = gFather;
continue;
}
if (node == father.getRight()) {
//左旋
leftRotate(father);
//交换
RBTreeNode tmp = node;
node = father;
father = tmp;
}
setBlack(father);
setRed(gFather);
//右旋
rightRotate(gFather);
}
//父节点在祖父节点右边
else {
RBTreeNode uncle = gFather.getLeft();
if (uncle != null && uncle.isBlack() == false) {
//颜色反转
setBlack(father);
setBlack(uncle);
setRed(gFather);
node = gFather;
continue;
}
if (node == father.getLeft()) {
//右旋
rightRotate(father);
//交换
RBTreeNode tmp = node;
node = father;
father = tmp;
}
setBlack(father);
setRed(gFather);
//左旋
leftRotate(gFather);
}
}
setBlack(root);
}
/**
* 左旋
*
* @param node
*/
private void leftRotate(RBTreeNode node) {
RBTreeNode right = node.getRight();
RBTreeNode parent = node.getParent();
// root
if (parent == null) {
root = right;
right.setParent(null);
} else {
if (parent.getLeft() != null && parent.getLeft() == node) {
parent.setLeft(right);
} else {
parent.setRight(right);
}
right.setParent(parent);
}
node.setParent(right);
node.setRight(right.getLeft());
if (right.getLeft() != null) {
right.getLeft().setParent(node);
}
right.setLeft(node);
}
/**
* 右旋
*
* @param node
*/
private void rightRotate(RBTreeNode node) {
RBTreeNode left = node.getLeft();
RBTreeNode parent = node.getParent();
if (parent == null) {
root = left;
left.setParent(null);
} else {
if (parent.getLeft() != null && parent.getLeft() == node) {
parent.setLeft(left);
} else {
parent.setRight(left);
}
left.setParent(parent);
}
node.setParent(left);
node.setLeft(left.getRight());
if (left.getRight() != null) {
left.getRight().setParent(node);
}
left.setRight(node);
}
/**
* 设置黑色
*
* @param node
*/
private void setBlack(RBTreeNode node) {
node.setBlack(true);
}
private void setRed(RBTreeNode node) {
node.setBlack(false);
}
public static void main(String[] args) {
RBTree rb = new RBTree();
rb.insert(10);//根节点
rb.insert(5);
rb.insert(9);
rb.insert(3);
rb.insert(6);
rb.insert(7);
rb.insert(19);
rb.insert(32);
rb.insert(24);
rb.insert(17);
rb.list(rb.root);
}
}
时间复杂度：O(logn)
应用
在JDK1.8中HashMap使用数组+链表+红黑树的数据结构。内部维护着一个数组table，该数组保存着每个链表的表头结点或者树的根节点。HashMap存储数据的数组定义如下，里面存放的是Node<K,V>实体：
transient Node<K, V>[] table;//序列化时不自动保存
/**
* 桶的树化阈值：即 链表转成红黑树的阈值， * 在存储数据时，当链表长度 > 该值时，则将链表转换
* 成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
5.5多路查找树
多路查找树(muitl-way search tree)，其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素。
B树
B树（BalanceTree）是对二叉查找树的改进。它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数。
一棵m阶的B 树 (m叉树)的特性如下：
- B树中所有节点的孩子节点数中的最大值称为B树的阶，记为M
- 树中的每个节点至多有M棵子树 —即：如果定了M，则这个B树中任何节点的子节点数量都不能超过M
- 若根节点不是终端节点，则至少有两棵子树
- 除根节点和叶节点外，所有点至少有m/2棵子树
- 所有的叶子结点都位于同一层
B+树
B+树是B-树的变体，也是一种多路搜索树，其定义基本与B树相同，它的自身特征是：
- 非叶子结点的子树指针与关键字个数相同
- 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
- 为所有叶子结点增加一个链指针
- 所有关键字都在叶子结点出现
典型应用
MySQL索引B+Tree
B树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。 多叉平衡
- B树的高度一般都是在2-4这个高度，树的高度直接影响IO读写的次数。
- 如果是三层树结构—支撑的数据可以达到20G，如果是四层树结构—支撑的数据可以达到几十T
B和B+的区别
- B树和B+树的最大区别在于非叶子节点是否存储数据的问题。
- B树是非叶子节点和叶子节点都会存储数据。
- B+树只有叶子节点才会存储数据，而且存储的数据都是在一行上，而且这些数据都是有指针指向的，也就是有顺序的
5.6二叉堆
二叉堆本质上是一种完全二叉树，它分为两个类型
- 大顶堆(最大堆)
最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值
- 小顶堆(最小堆)
最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值
二叉堆的根节点叫作堆顶
最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素
二叉堆的存储原理
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。
从图中我们可以看到，数组中下标为 i 的节点的左子节点，就是下标为 i∗2 的节点，右子节点就是下标为 i∗2+1 的节点，父节点就是下标为 i/2 取整的节点
二叉堆的典型应用
优先队列
利用堆求 Top K问题
在一个包含 n 个数据的数组中，我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了
6.排序
根据时间复杂度的不同，主流的排序算法可以分为3大类
- 时间复杂度为O( )的排序算法
冒泡排序、选择排序、插入排序、希尔排序 - 时间复杂度为O(nlogn)的排序算法
快速排序 、归并排序、堆排序 - 时间复杂度为线性的排序算法
计数排序、桶排序、基数排序
根据其稳定性，可以分为稳定排序和不稳定排序
稳定排序：值相同的元素在排序后仍然保持着排序前的顺序
不稳定排序：值相同的元素在排序后打乱了排序前的顺序
6.1 冒泡排序
冒泡排序是最基础的排序算法
冒泡排序的英文是bubble sort，它是一种基础的交换排序
冒泡排序这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。
按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。
时间复杂度：O( n^2)
6.2 快速排序
同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分，这种思路就叫作分治法。
快速排序的时间复杂度是：O(nlogn)
6.3 堆排序
堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆排序的时间复杂度是： O(nlogn)
6.4 计数排序
计数排序，这种排序算法是利用数组下标来确定元素的正确位置的。
计数排序的时间复杂度是O(n+m)
n: 数据个数
m: 数据范围
6.5 桶排序
桶排序同样是一种线性时间的排序算法
桶排序需要创建若干个桶来协助排序
每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素
桶排序的第1步，就是创建这些桶，并确定每一个桶的区间范围具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外， 前面各个桶的区间按照比例来确定。
区间跨度 = （最大值-最小值）/ （桶的数量 - 1）
桶排序的时间复杂度是O(n)
各个排序比对表：
7.字符串匹配
字符串匹配这个功能，是非常常见的功能，比如"Hello"里是否包含"el"?
Java里用的是indexOf函数，其底层就是字符串匹配算法。主要分类如下：
7.1 BF 算法
BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。
这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高
比方说，我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串
我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。
/**
* 暴力匹配法
*/
public class BFMatch {
/**
* 检测匹配
*
* @param main 主串
* @param pattern 模式串
* @return
*/
public static boolean isMatch(String main, String pattern) {
//循环主串 n
for (int i = 0; i <= (main.length() - pattern.length()); i++) {
//有匹配 循环子串 m
if (main.substring(i, i + pattern.length()).equals(pattern)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(isMatch("hello", "lo"));
}
}
时间复杂度
我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)。
m:为匹配串长度
n:为主串长度
应用
虽然BF算法效率不高但在实际情况下却很常用。因为：主串不会太长，实现简单
7.2 RK 算法
RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的
每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是O(n*m)。我们对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低
RK 算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了
/**
* hash匹配法
*/
public class RKMatch {
/**
* Hash匹配
*
* @param main 主串
* @param pattern 模式串
* @return
*/
public static boolean isMatch(String main, String pattern) {
//计算模式串的hash值
int ph = strTohash(pattern);
for (int i = 0; i <= (main.length() - pattern.length()); i++) {
if (ph == strTohash(main.substring(i, i + pattern.length()))) {
return true;
}
}
return false;
}
/**
* 简单hash计算法
*
* @param src
* @return
*/
public static int strTohash(String src) {
int hash = 0;
for (int i = 0; i < src.length(); i++) {
//26进制 小写字母 a-z
hash *= 26;
hash += src.charAt(i) - 97;
}
return hash;
}
public static void main(String[] args) {
//System.out.println(strTohash("abc"));
System.out.println(isMatch("abcddff", "abe"));
}
}
时间复杂度
RK 算法的的时间复杂度为O(m+n)
m:为匹配串长度
n:为主串长度
应用
适用于匹配串类型不多的情况，比如：字母、数字或字母加数字的组合 62 (大小写字母+数字)
7.3 BM 算法
BF 算法性能会退化的比较严重，而 RK 算法需要用到哈希算法，而设计一个可以应对各种类型字符的哈希算法并不简单。
BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，滑动算法
在这个例子里，主串中的 c，在模式串中是不存在的，所以，模式串向后滑动的时候，只要 c 与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 c 的后面。
BM 算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。
/**
* 滑动匹配法
*/
public class BmMatch {
/**
* 模式串字典
*
* @param b
* @param m
* @param dc
*/
private static void genBC(char[] b, int m, int[] dc) {
//初始化字典
for (int i = 0; i < 256; i++) {
dc[i] = -1;
}
//将模式串中的字符写入字典中
for (int i = 0; i < m; i++) {
int asc = (int) b[i];
//asc 是下标 i 是模式串中的位置
dc[asc] = i;
}
}
/**
* BM算法匹配
*
* @param main
* @param pattern
* @return
*/
public static int bad(char[] main, char[] pattern) {
int n = main.length;
int m = pattern.length;
int[] bc = new int[256];
genBC(pattern, m, bc);
//对齐的第一个字符
int i = 0;
while (i <= n - m) {
//坏字符在模式串中的下标
int j;
for (j = m - 1; j >= 0; j--) {
if (main[i + j] != pattern[j])
break;
}
//匹配成功
if (j < 0) {
//返回位置
return i;
}
//滑动位 si-xi
i = i + (j - bc[(int) main[i + j]]);
}
return -1;
}
public static void main(String[] args) {
String s1 = "abcabcabcd";
String s2 = "cabcd";
System.out.println(bad(s1.toCharArray(), s2.toCharArray()));
}
}
BM算法的时间复杂度是O(N/M)
n:主串长度
m:模式串长度
应用
BM算法比较高效，在实际开发中，特别是一些文本编辑器中，用于实现查找字符串功能。
7.4 Trie 树
Trie 树，也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
比如：有 6 个字符串，它们分别是：how，hi，her，hello，so，see，我们可以将这六个字符串组成Trie树结构。
Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。
其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（红色节点为叶子节点）
/**
* Trie树节点
*/
public class TrieNode {
char data;//数据
TrieNode[] children = new TrieNode[26]; //孩子节点
boolean isLeaf = false; //是否叶子
public TrieNode(char data) {
this.data = data;
}
}
/**
* Trie树
*/
public class Trie {
TrieNode root = new TrieNode('/');//根节点
/**
* 插入到Trie树
*
* @param txt
*/
public void insert(char[] txt) {
TrieNode p = root;
for (int i = 0; i < txt.length; i++) {
//索引位
int idx = txt[i] - 97;
if (p.children[idx] == null) {
TrieNode node = new TrieNode(txt[i]);
p.children[idx] = node;
}
//指向下一个孩子
p = p.children[idx];
}
//最后一个字母
p.isLeaf = true;
}
/**
* 在Trie树中查找一个字符串
*
* @param pattern
* @return
*/
public boolean find(char[] pattern) {
TrieNode p = root;
for (int i = 0; i < pattern.length; i++) {
int idx = pattern[i] - 97;
//只要一个字母不匹配没有匹配
if (p.children[idx] == null) {
return false;
}
p = p.children[idx];
}
//没有找到最后一个字母
if (p.isLeaf == false) {
//只能匹配前缀
return false;
} else {
//完全匹配
return true;
}
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("hello".toCharArray());
trie.insert("her".toCharArray());
trie.insert("hi".toCharArray());
trie.insert("how".toCharArray());
trie.insert("see".toCharArray());
trie.insert("so".toCharArray());
System.out.println(trie.find("ho".toCharArray()));
}
}
时间复杂度
如果要在一组字符串中，频繁地查询某些字符串，用 Trie 树会非常高效。构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。但是一旦构建成功之后，后续的查询操作会非常高效。每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。
典型应用
利用 Trie 树，实现搜索关键词的提示功能
我们假设关键词库由用户的热门搜索关键词组成。我们将这个词库构建成一个 Trie 树。当用户输入其中某个单词的时候，把这个词作为一前缀子串在 Trie 树中匹配。为了讲解方便，我们假设词库里只有hello、her、hi、how、so、see 这 6 个关键词。当用户输入了字母 h 的时候，我们就把以 h 为前缀的hello、her、hi、how 展示在搜索提示框内。当用户继续键入字母 e 的时候，我们就把以 he 为前缀的hello、her 展示在搜索提示框内。这就是搜索关键词提示的最基本的算法原理。
8.图
8.1 图的概念
图（Graph），是一种复杂的非线性表结构。
图中的元素我们就叫做顶点（vertex）
图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边（edge）
跟顶点相连接的边的条数叫做度（degree）
图这种结构有很广泛的应用，比如社交网络，电子地图，多对多的关系就可以用图来表示。
边有方向的图叫做有向图，比如A点到B点的直线距离，微信的添加好友是双向的
边无方向的图叫无向图，比如网络拓扑图
带权图（weighted graph）。在带权图中，每条边都有一个权重（weight），我们可以通过这个权重来表示 一些可度量的值
8.2 图的存储
图最直观的一种存储方法就是，邻接矩阵（Adjacency Matrix）。
邻接矩阵的底层是一个二维数组
无向图：如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j]和 A[j][i]标记为 1
有向图：
如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，那我们就将 A[i][j]标记为 1。同理，如
果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i]标记为 1
带权图
数组中就存储相应的权重
/**
* 用邻接矩阵实现图
*/
public class Graph1 {
//存储顶点的链表
List vertexList;
//二维数组 存储边 值是权值
int[][] edges;
int numEdge; //边数
public Graph1(int n) {
edges = new int[n][n];
vertexList = new ArrayList();
numEdge = 0;
}
public int getVertexNums() {
return vertexList.size();
}
public int getNumEdge() {
return numEdge;
}
public Object getVertex(int i) {
return vertexList.get(i);
}
public int getWeight(int i, int j) {
return edges[i][j];
}
//插入结点
public void insertVertex(Object v) {
vertexList.add(v);
}
/**
* 插入边
*
* @param i 顶点1
* @param j 顶点2
* @param w 权值
*/
public void insertEdge(int i, int j, int w) {
edges[i][j] = w;
numEdge++;
}
public static void main(String[] args) {
Graph1 graph1 = new Graph1(4);
graph1.insertVertex("A"); // 0
graph1.insertVertex("B"); //1
graph1.insertVertex("C"); //2
graph1.insertVertex("D"); // 3
//A-B 2
graph1.insertEdge(0, 1, 2);
// B-C 4
graph1.insertEdge(1, 2, 4);
// C-D 2
graph1.insertEdge(2, 3, 2);
// A-D 4
graph1.insertEdge(0, 3, 4);
System.out.println(graph1.getNumEdge());
System.out.println(graph1.getVertexNums());
System.out.println(graph1.getWeight(2, 3));
}
}
邻接表
用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间
对于无向图来说，如果 A[i][j]等于 1，那 A[j][i]也肯定等于 1。实际上，我们只需要存储一个就可以了。也就是说，无向图的二维数组中，如果我们将其用对角线划分为上下两部分，那我们只需要利用上面或者下面这样一半的空间就足够了，另外一半白白浪费掉了
还有，如果我们存储的是稀疏图（Sparse Matrix），也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户，对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多，一般也就三五百个而已。如果我们用邻接矩阵来存储，那绝大部分的存储空间都被浪费了
针对上面邻接矩阵比较浪费内存空间的问题，我们来看另外一种图的存储方法，邻接表（AdjacencyList）。
每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。
图中画的是一个有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。
前面的数组存储的是所有的顶点，每一个顶点后面连接的块代表前面顶点所指向的顶点和路线的权值。
如果该点还指向其他顶点，则继续在块后面添加。例如A指向了B权值是4，那么A后面就加上一块，之后发现A还指向D权值是5，那么就在块尾继续添加一块。其实也就是数组+链表的结构
根据邻接表的结构和图，我们不难发现，图其实是由顶点和边组成的。所以我们就抽象出两种类，一个是Vertex顶点类，一个是Edge边类
/**
* 边
*/
public class Edge {
String name; // 到达的顶点名称
int weight; //权重
Edge next;//指向的下一个边
public Edge(String name, int weight, Edge next) {
this.name = name;
this.weight = weight;
this.next = next;
}
}
/**
* 顶点
*/
public class Vertex {
String name;//出发点名称
Edge next;//从该顶点出发的边
public Vertex(String name, Edge next) {
this.name = name;
this.next = next;
}
}
/**
* 邻接表实现图
*/
public class Graph2 {
Map<String, Vertex> vertexMap = new HashMap<>(); //存储顶点
/**
* 插入顶点
*
* @param name
*/
public void insertVertex(String name) {
Vertex vertex = new Vertex(name, null);
vertexMap.put(name, vertex);
}
/**
* 插入边
*
* @param start
* @param end
* @param weight
*/
public void insertEdge(String start, String end, int weight) {
Vertex vstart = vertexMap.get(start);
if (vstart == null) {
return; //没有顶点 不许插入边
}
Edge edge = new Edge(end, weight, null);
//无边
if (vstart.next == null) {
vstart.next = edge;
}
//有边 循环找到最后一条边
else {
Edge last = vstart.next;
while (last.next != null) {
last = last.next;
}
last.next = edge;
}
}
/**
* 打印图
*/
public void print() {
Set<Map.Entry<String, Vertex>> set = vertexMap.entrySet();
Iterator<Map.Entry<String, Vertex>> its = set.iterator();
while (its.hasNext()) {
Map.Entry<String, Vertex> entry = its.next();
Vertex vertex = entry.getValue();
Edge edge = vertex.next;
while (edge != null) {
System.out.println(vertex.name + "指向" + edge.name + "权值为：" + edge.weight);
edge = edge.next;
}
}
}
public static void main(String[] args) {
Graph2 graph2 = new Graph2();
//插入顶点
graph2.insertVertex("A");
graph2.insertVertex("B");
graph2.insertVertex("C");
graph2.insertVertex("D");
graph2.insertVertex("E");
graph2.insertVertex("F");
//插入边
graph2.insertEdge("A", "B", 4);
graph2.insertEdge("A", "D", 5);
graph2.insertEdge("C", "A", 1);
graph2.insertEdge("D", "E", 3);
graph2.insertEdge("D", "F", 4);
graph2.insertEdge("E", "B", 2);
graph2.insertEdge("F", "C", 2);
graph2.print();
}
}
8.3 图的遍历
遍历是指从某个节点出发，按照一定的的搜索路线，依次访问对数据结构中的全部节点，且每个节点仅
访问一次
前面已经讲过了二叉树的节点遍历
类似的，图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列
图的遍历过程中，根据搜索方法的不同，又可以划分为两种搜索策略：
- 深度优先搜索
- 广度优先搜索
深度优先搜索（DFS，Depth First Search）
深度优先搜索，从起点出发，从规定的方向中选择其中一个不断地向前走，直到无法继续为止，然后尝试另外一种方向，直到最后走到终点。就像走迷宫一样，尽量往深处走。
DFS 解决的是连通性的问题，即，给定两个点，一个是起始点，一个是终点，判断是不是有一条路径能从起点连接到终点。起点和终点，也可以指的是某种起始状态和最终的状态。问题的要求并不在乎路径是长还是短，只在乎有还是没有。
假设我们有这么一个图，里面有A、B、C、D、E、F、G、H 8 个顶点，点和点之间的联系如下图所示，对这个图进行深度优先的遍历。
必须依赖栈（Stack），特点是后进先出（LIFO）。
时间复杂度
邻接表
访问所有顶点的时间为 O(V)，而查找所有顶点的邻居一共需要 O(E) 的时间，所以总的时间复杂度是O(V + E)。
邻接矩阵
查找每个顶点的邻居需要 O(V) 的时间，所以查找整个矩阵的时候需要 O( ) 的时间
广度优先搜索（BFS，Breadth First Search）
直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。
假设我们有这么一个图，里面有A、B、C、D、E、F、G、H 8 个顶点，点和点之间的联系如下图所示，对这个图进行深度优先的遍历。
依赖队列（Queue），先进先出（FIFO）。
最短路径问题
广度优先搜索，一般用来解决最短路径的问题。
时间复杂度
邻接表
每个顶点都需要被访问一次，时间复杂度是 O(V)；相连的顶点（也就是每条边）也都要被访问一次，加起来就是 O(E)。因此整体时间复杂度就是 O(V+E)。
邻接矩阵
V 个顶点，每次都要检查每个顶点与其他顶点是否有联系，因此时间复杂度是 O( )。
应用
广度优先的搜索可以同时从起始点和终点开始进行，称之为双端 BFS。这种算法往往可以大大地提高搜索的效率。
社交网络可以用图来表示。这个问题就非常适合用图的广度优先搜索算法来解决，因为广度优先搜索是层层往外推进的。首先，遍历与起始顶点最近的一层顶点，也就是用户的一度好友，然后再遍历与用户距离的边数为 2 的顶点，也就是二度好友关系，以及与用户距离的边数为 3 的顶点，也就是三度好友关系。
9.算法思维
9.1 贪心算法
概念
贪婪算法（Greedy）的定义：是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
贪婪算法：当下做局部最优判断，不能回退
（能回退的是回溯，最优+回退是动态规划）
由于贪心算法的高效性以及所求得答案比较接近最优结果，贪心算法可以作为辅助算法或解决一些要求结果不特别精确的问题
经典问题：部分背包
背包问题是算法的经典问题，分为部分背包和0-1背包，主要区别如下：
部分背包：某件物品是一堆，可以带走其一部分
0-1背包：对于某件物品，要么被带走（选择了它），要么不被带走（没有选择它），不存在只带走一部分的情况。
部分背包问题可以用贪心算法求解，且能够得到最优解。
假设一共有N件物品，第 i 件物品的价值为 Vi ，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，可以带走某件物品的一部分，请问：他应该选择哪些物品？
假设背包可容纳50Kg的重量，物品信息如下表：
贪心算法的关键是贪心策略的选择
将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品
按照我们的贪心策略，单位重量的价值排序： 物品A > 物品B > 物品C
因此，我们尽可能地多拿物品A，直到将物品1拿完之后，才去拿物品B，然后是物品C 可以只拿一部分…
/**
* 物品
*/
public class Goods {
String name; //名称
double weight; //重量
double price; //价格
double value; //价值
public Goods(String name, double weight, double price) {
this.name = name;
this.weight = weight;
this.price = price;
this.value=price/weight;
}
}
/**
* 部分背包——贪心算法
*/
public class Bag1 {
//最大承重
double max = 0;
public void getMaxValue(Goods[] glist) {
Goods[] glist2 = sort(glist); //价值排序
//当前总重
double sum_w = 0;
for (int i = 0; i < glist2.length; i++) {
sum_w += glist2[i].weight;
if (sum_w <= max) {
System.out.println(glist2[i].name + "取" + glist2[i].weight + "kg");
} else {
System.out.println(glist2[i].name + "取" + (max - (sum_w - glist2[i].weight)) + "kg");
return;
}
}
}
//按价值排序
private Goods[] sort(Goods[] goods) {
return goods;
}
public static void main(String[] args) {
Bag1 bag1 = new Bag1();
Goods g1 = new Goods("A", 10, 60); //6
Goods g2 = new Goods("B", 20, 100); //5
Goods g3 = new Goods("C", 30, 120); //4
Goods[] goods = {g1, g2, g3}; // 价值倒序
bag1.max = 50;
bag1.getMaxValue(goods);
}
}
时间复杂度
在不考虑排序的前提下，贪心算法只需要一次循环，所以时间复杂度是O(n)
优缺点
优点：性能高，能用贪心算法解决的往往是最优解
缺点：在实际情况下能用的不多，用贪心算法解的往往不是最好的
适用场景
针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据（局部最优而全局最优）
大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明
在实际情况下，用贪心算法解决问题的思路，并不总能给出最优解
9.2 分治算法
概念
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n
个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
关于分治和递归的区别
分治算法是一种处理问题的思想，递归是一种编程技巧
分治算法的递归实现中，每一层递归都会涉及这样三个操作：
分解：将原问题分解成一系列子问题
解决：递归地求解各个子问题，若子问题足够小，则直接求解
合并：将子问题的结果合并成原问题
比如：
将字符串中的小写字母转化为大写字母
“abcde”转化为"ABCDE"
我们可以利用分治的思想将整个字符串转化成一个一个的字符处理
/**
* 字符串小写字母转大写字母---分治算法
*/
public class CharUpCase {
public static char[] toUpCase(char[] arr, int i) {
//递归结束条件
if (i >= arr.length) {
return arr;
}
arr[i] = toUpCaseUnit(arr[i]);
return toUpCase(arr, i + 1);
}
/**
* 单元方法 小写转大写
*
* @param a
* @return
*/
private static char toUpCaseUnit(char a) {
//不是字母
if ((int) a < 97 || (int) a > 122) {
return ' ';
}
return (char) Integer.parseInt(String.valueOf((int) a - 32));
}
public static void main(String[] args) {
char[] arr = toUpCase("abcdde".toCharArray(), 0);
System.out.println(arr);
}
}
求 X^n问题
比如: 2^10 2的10次幂
一般的解法是循环10次
public static int commpow(int x,int n){
int s=1;
while(n>=1){
s*=x;
n--;
}
return s;
}
该方法的时间复杂度是：O(n)
采用分治法
2^10拆成
我们看到每次拆成n/2次幂，时间复杂度是O(logn)
/**
* 计算n次幂——分治
*/
public class Pow {
/**
* 计算x的n次幂
*
* @param x
* @param n
* @return
*/
public static int pow(int x, int n) {
//递归结束 任何数的1次方都是它本身
if (n == 1)
return x;
int half = pow(x, n / 2);
//偶数
if (n % 2 == 0) {
return half * half;
}
//奇数
else {
return half * half * x;
}
}
public static void main(String[] args) {
System.out.println(pow(2, 10));
}
}
时间复杂度
根据拆分情况可以是O(n)或O(logn)
优缺点
优势：将复杂的问题拆分成简单的子问题，解决更容易，另外根据拆分规则，性能有可能提高。
劣势：子问题必须要一样，用相同的方式解决
适用场景
分治算法能解决的问题，一般需要满足下面这几个条件：
- 原问题与分解成的小问题具有相同的模式；
- 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别
- 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
- 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。
9.3 回溯算法
概念
回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。
回溯的处理思想，有点类似枚举（列出所有的情况）搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
经典问题
N皇后问题
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。
/**
* N皇后问题---回溯算法
*/
public class NQueens {
static final int QUEENS = 8;//皇后数
// 下标是行 值是列
int[] result = new int[QUEENS]; // 存储放好的皇后
static int sum = 0;
/**
* 在指定行放皇后
*
* @param row
*/
public void setQueens(int row) {
//放置完成
if (row == QUEENS) {
print();
return;
}
//循环列
for (int col = 0; col < QUEENS; col++) {
if (isOK(row, col)) {
//存入数组
result[row] = col;
//开始下一行
setQueens(row + 1);
}
}
}
/**
* 判断是否可以放置
*
* @param row
* @param col
* @return
*/
private boolean isOK(int row, int col) {
int leftup = col - 1;//左对角线
int rightup = col + 1;//右对角线
for (int i = row - 1; i >= 0; i--) {
//等于列 原列存在
if (result[i] == col) {
return false;
}
//左对角线
if (leftup >= 0) {
if (result[i] == leftup)
return false;
}
if (rightup < QUEENS) {
if (result[i] == rightup)
return false;
}
leftup--;
rightup++;
sum++;
}
return true;
}
/**
* 打印结果
*/
private void print() {
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result.length; j++) {
if (result[i] == j) {
System.out.print("Q|");
} else {
System.out.print("*| ");
}
}
System.out.println();
}
System.out.println("-------------------");
}
public static void main(String[] args) {
NQueens queens = new NQueens();
queens.setQueens(0);
System.out.println(sum);
System.out.println(8 * 7 * 6 * 5 * 4 * 3 * 2 * 1);
}
}
时间复杂度
N皇后问题的时间复杂度为：o(n!) 实际为n!/2
优缺点
优点：
回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。
劣势：
效率相对于低（动态规划）
适用场景
回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了
9.4 动态规划
概念
动态规划(Dynamic Programming)，是一种分阶段求解的方法。
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
首先是拆分问题,我的理解就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现. 关键就是这个步骤,动态规划有一类问题就是从后往前推到,有时候我们很容易知道:如果只有一种情况时,最佳的选择应该怎么做.然后根据这个最佳选择往前一步推导,得到前一步的最佳选择 然后就是定义问题状态和状态之间的关系,我的理解是前面拆分的步骤之间的关系,用一种量化的形式表现出来,类似于
高中学的推导公式,因为这种式子很容易用程序写出来,也可以说对程序比较亲和(也就是最后所说的状态转移方程式) 我们再来看定义的下面的两段,我的理解是比如我们找到最优解,我们应该讲最优解保存下来,为了往前推导时能够使用前一步的最优解,在这个过程中难免有一些相比于最优解差的解,此时我们应该放弃,只保存最优解,这样我们每一次都把最优解保存了下来,大大降低了时间复杂度
动态规划中有三个重要概念：
- 最优子结构
- 边界
- 状态转移公式（递推方程）dp方程
经典问题
再谈斐波那契数列
优化递归：
通过上边的递归树可以看出在树的每层和上层都有大量的重复计算，可以把计算结果存起来，下次再用的时候就不用再计算了，这种方式叫记忆搜索，也叫做备忘录模式
/**
* 斐波那契数列：递归分治+备忘录(动态规划)
*/
public class Fib2 {
//用于存储每次计算的结果
static long[] sub = new long[1000000];
public static long fib(int n) {
if (n <= 1)
return n;
//该数字已被计算
if (sub[n] != 0) {
return sub[n];
} else {
sub[n] = fib(n - 1) + fib(n - 2);
}
return sub[n];
}
public static void main(String[] args) {
System.out.println(fib(64));
}
}
if(i<2) 则
if(i>=2) 则
最优子结构： fib[9]=finb[8]+fib[7]
边界：a[0]=0; a[1]=1;
dp方程：fib[n]=fib[n-1]+fib[n-2]
/**
* 斐波那契数列——DP方程（动态规划）
*/
public class Fib3 {
public static long fib(int n) {
long a[] = new long[n + 1];
//初始值
a[0] = 0;
a[1] = 1;
int i = 0;
for (i = 2; i <= n; i++) {
//dp方程 dp(n)=dp(n-1)+dp(n-2)
a[i] = a[i - 1] + a[i - 2];
}
return a[i - 1];
}
public static void main(String[] args) {
System.out.println(fib(64));
}
}
使用动态规划四个步骤
- 把当前的复杂问题转化成一个个简单的子问题（分治）
- 寻找子问题的最优解法（最优子结构）
- 把子问题的解合并，存储中间状态
- 递归+记忆搜索或自底而上的形成递推方程(dp方程)
时间复杂度
新的斐波那契数列实现时间复杂度为O(n)
优缺点
优点：时间复杂度和空间复杂度都相当较低
缺点：难，有些场景不适用
适用场景
尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。
10.实战
10.1 环形链表问题
给定一个链表，判断链表中是否有环。存在环返回 true ，否则返回 false
分析：
该题可以理解为检测链表的某节点能否二次到达（重复访问）的问题。
需要一个容器记录已经访问过的节点 每次访问到新的节点，都与容器中的记录进行匹配，若相同则存在环 若匹配之后没有相同节点，则存入容器，继续访问新的节点 直到访问节点的next指针返回null，或者当前节点与容器的某个记录相同，操作结束。
实现简单，时间复杂度为：O(n^2)
遍历整个链表：O(n)
每次遍历节点，再遍历数组进行匹配：O(n)
换个思路：
该题可以理解为“追击相遇”问题，如果存在环，跑得快的一定能追上跑得慢的。
比如：一快一慢两个运动员，如果在直道赛跑，不存在追击相遇问题；如果是在环道赛跑，快的绕了一圈肯定可以追上慢的。
解法：
- 定义快慢两个指针：
slow=head; fast=head.next; - 遍历链表：
快指针步长为2：fast=fast.next.next; 慢指针步长为1：slow=slow.next; - 当且仅当快慢指针重合(slow==fast)，有环，返回true
- 快指针为null，或其next指向null，没有环，返回false，操作结束
/**
* 判断链表是否有环
*/
public class RingList {
/**
* 判断链表是否有环
* @param head
* @return
*/
public static boolean isRing(Node head){
if(head==null) return false;
//定义快慢指针
Node slow=head; //慢
Node fast=head.next; //快
while(fast!=null&&fast.next!=null){
//追击相遇 有环
if(slow==fast){
return true;
}
fast=fast.next.next; //步长为2
slow=slow.next;//步长为1
}
//无环
return false;
}
public static void main(String[] args) {
Node n1=new Node(1,"张飞");
Node n2=new Node(2,"赵云");
Node n3=new Node(3,"关羽");
Node n4=new Node(4,"黄忠");
Node n5=new Node(5,"狄仁杰");
n1.next=n2;
n2.next=n3;
n3.next=n4;
n4.next=n5;
n5.next=null;
System.out.println(isRing(n1));
}
}
10.2 0-1背包问题
有n件物品和一个最大承重为W的背包，每件物品的重量是w[i]，价值是v[i]
在保证总重量不超过W的前提下，选择某些物品装入背包，背包的最大总价值是多少？
注意：每个物品只有一件，也就是每个物品只能选择0件或者1件
分析：
假设：W=10，有5件物品，重量和价值如下：
w[1]=2,v[1]=6
w[2]=2,v[2]=3
w[3]=6,v[3]=5
w[4]=5,v[4]=4
w[5]=4,v[5]=6
dp数组的计算结果如下表：
i:选择i件物品 j:最大承重
/**
* 0-1背包，计算最大价值 DP方程
*/
public class Gold {
/**
* 计算最大价值
*
* @param values 物品的价值数组
* @param weights 物品的重量数组
* @param max 背包最大承重
* @return
*/
public static int maxValue(int[] values, int[] weights, int max) {
if (values == null || values.length == 0)
return 0;
if (weights == null || weights.length == 0)
return 0;
if (values.length != weights.length || max <= 0)
return 0;
//dp数组 dp[i-1] i从1开始
int[][] dp = new int[values.length + 1][max + 1];
for (int i = 1; i <= values.length; i++) {
for (int j = 1; j <= max; j++) {
//选择的物品超过最大承重
if (weights[i - 1] > j) {
//不能选该物品 等于上轮的最大价值
dp[i][j] = dp[i - 1][j];
}
//选择的物品不超过最大承重
else {
//上轮的最大价值
int proValue = dp[i - 1][j];
//选择该商品后的最大价值
int curValue = values[i - 1] + dp[i - 1][j - weights[i - 1]];
//两者取最大值
dp[i][j] = Math.max(proValue, curValue);
}
}
}
int mv = dp[values.length][max];
//逆推找出装入背包的所有商品的编号（选的矿的编号）
int j = max;
String numStr = "";
for (int i = values.length; i > 0; i--) {
//若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的（第i个矿挖）
if (dp[i][j] > dp[i - 1][j]) {
numStr = i + " " + numStr;
j = j - weights[i - 1];
}
if (j == 0)
break;
}
System.out.println("选择的金矿有：" + numStr);
return mv;
}
public static void main(String[] args) {
int[] values = {60, 30, 50, 40, 60};
int[] weights = {2, 2, 6, 5, 4};
int max = 10;
System.out.println("挖出的最大储量是：" + maxValue(values, weights, max));
}
}
时间复杂度为：O(i * j)
可以看出动态规划是计算的值是上次的某个值+这次的值
是一种用空间换时间的算法。
扫一扫
7691
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
