算法
2021-08-25 14:50:22 0 举报AI智能生成
算法
作者其他创作
大纲/内容
常用的算法
1. 基础
概述
数据结构
数据结构是计算存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合
一句话：存数据的，且实在内存中存
常见
线性表
数组、链表、栈、队列
散列表
hash、位图
树
二叉树、多路树、堆
图
有向图、无向图、带权图
算法
指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制
一句话：一种解决特定问题的思路
常见
排序
冒泡、快速、插入、归并、计数、选择、推排序、桶排序
其他
LRU、LFU、Hash、一致性Hash
算法思维
递归、回溯、分治、贪心、动态规划
复杂度
数据结构和算法本质上是“快”和“省”，所以代码的执行效率是非常重要的度量
时间复杂度
也称为渐进时间复杂度，计算技巧
计算循环执行次数最多的代码
总复杂度 = 量级最大的复杂度
嵌套代码的复杂度 = 嵌套内外代码复杂度的乘积
常见
O(1)
最简单，也最好理解的，即常量级
只要代码的执行不随着数据规模(n)的增加而增加，就是常量级
实际应用中，通常使用冗余字段存储来讲O(n)变成O(1)
O(logn)、O(nlogn)
快速排序、归并排序的时间复杂度都是O(nlogn)
O(n)
很多线性表的操作都是O(n)，这是最常见的一个时间复杂度
如数组插入删除、链表的遍历
O(m+n)
代码的时间复杂度由两个数据的规模来决定
O(m*n)
两段时间复杂度之积
空间复杂度
全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系
由于现在硬件相对便宜，所以开发中常常利用空间来换时间，如缓存技术
典型的数据结构中空间换时间是：跳跃表
线性表
介绍
就是数据排成像一条线一样的结构，数据只有前后两个方向
数组
概念
数组是有限个相同类型的变量所组成的有序集合，其中每一个变量被称为元素
它是最简单、最常见的数据结构
数组下标从零开始
存储原理
数组使用一组连续的内存空间来存储一组具有相同类型的数据
数组可以根据下标随机访问数据
操作
读取数据
根据下标读取元素的方式叫做随机读取
时间复杂度为O(1)
更新元素
时间复杂度为O(1)
插入元素
尾部插入
在数据的实际元素数量小于数组长度的情况下，直接把插入的元素放在数组尾部的空闲位置即可，等同于更新操作
中间插入
在数据的实际元素数量小于数组长度的情况下，由于数组的每一个元素都有其固定下标，所以首先把插入位置及后面的元素向后移动，再把要插入的元素放到对应的数组位置上
超范围插入
需要对原数组进行扩容，可以创建一个新数组，长度是原数组的2倍，再把原数组中的元素统一复制过去，即实现了数组的扩容
删除元素
和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前移动1位
时间复杂度
读取和更新都是随机访问，所以是O(1)
插入数组扩容的是O(n)，插入并移动元素也是O(n)，综合起来插入操作是O(n)
删除操作，只涉及元素的移动，也是O(n)
优点
数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素
缺点
插入和删除操作，由于数组元素连续紧密地存储在内存中，会导致大量元素被迫移动，影响效率
申请的空间必须是连续的，即使有空间也可能因为没有足够的连续空间而创建失败
如果超出范围，需要重新申请内存进行存储，原空间就浪费了
应用
数组是基础的数据结构，如ArrayList、Redis、消息队列等
链表
概念
是一种在物理上非连续、非顺序的数据结构，由若干节点组成
链表中的数据元素的逻辑顺序是通过链表中的指针链接次序实现的
链表由一系列结点（链表中的每个元素称为结点）组成，结点可以在运行时动态生成
每个结点包括
一个存储数据元素的数据域
一个存储下一个结点地址的指针域
常见
单链表
每一个结点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个结点的指针next
双向链表
每一个结点除了拥有data和next指针，还拥有指向前置结点的prev指针
循环链表
链表的尾结点指向头结点形成一个环，称为循环链表
存储原理
数组在内存中的存储方式是顺序存储，链表在内存中则是随机存储
链表的每一个结点分布在内存的不同位置，依靠next指针关联起来，这样可以灵活有效地利用零散的碎片空间
链表的第一个结点被称为头结点，没有任何结点的next指针指向它，或它的前置结点为空，头结点用来记录链表的基地址，可以利用它遍历得到整条链表
链表的最后一个结点被称为尾结点，它指向的next为空
操作
查找节点
在查找元素时，链表只能从头结点开始往后一个一个节点逐一查找
更新节点
找到要更新的节点，然后把旧数据替换成新数据
插入节点
尾部插入
把最后一个节点的next指针指向新插入的节点即可
头部插入
1、把新节点的next指针指向原先的头结点
2、把新节点变为链表的头结点
中间插入
1、新节点的next指针，指向插入位置的节点
2、插入位置前置节点的next指针，指向新节点
只要内存空间允许，能够插入链表的元素是无限的，不需要像数组那样考虑扩容的问题
删除节点
尾部删除
把倒数第二个节点的next指针指向为空即可
头部删除
把链表的头结点设为原先头结点的next指针即可
中间删除
把要删除结点的前置结点的next指针，指向要删除元素的下一个结点即可
时间复杂度
查找
O(n)
插入
O(1)
更新
O(1)
删除
O(1)
优点
插入、删除、更新效率高
省空间
缺点
查询效率较低，不能随机访问
应用
如树、图、Redis的列表、LRU算法实现、消息队列等
对比数组
数组优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更为适合
链表的优势在于能够灵活的进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更为适合
它们都是线性数据存储的物理存储结构，即顺序存储和链式存储
栈
栈和队列都属线性数据的逻辑存储结构
概念
一种线性数据结构，栈中的元素只能先入后出（FILO）
最早进入的元素存放的位置称为栈底（bottom），最后进入的元素存放的位置称为栈顶（top）
存储原理
栈既可以用数组实现，也可以用链表实现
数组实现的栈也叫顺序栈或静态栈
链表实现的栈也叫链式栈或动态栈
操作
入栈（push）
即把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会称为新的栈顶
出栈（pop）
即把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会称为新的栈顶
时间复杂度
入栈和出栈时间复杂度都是O(1)
支持动态扩容的顺序栈
当数组空间不够时，就重新申请一块更大内存，将原来数组中数据拷贝过去，这样就实现了一个支持动态扩容的数据，此时入栈的时间复杂度是O(n)
应用
函数调用
每进入一个函数，就会将临时变量作为一个栈入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈
浏览器的回退
队列
概念
一种线性数据结构，队列中的元素只能先入先出（FIFO）
队列的出口端叫做队头，队列的入口端叫做队尾
存储原理
数组实现
为了方便入队操作，把队尾位置规定为最后入队元素的下一个位置
数组实现的队列叫做顺序队列
链表实现
叫做链式队列
操作
入队（enqueue）
即把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾
出队（dequeue）
把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头
时间复杂度
入队和出队都是O(1)
应用
资源池、消息队列、命令队列等
散列表
概念
也叫做Hash表，这种数据结构提供了键/值的映射关系，只要给出一个Key，就可以高效查找它所匹配的Value，时间复杂度接近于O(1)
存储原理
哈希函数
散列表本质上也是一个数组，它的Key以字符串类型为主，通过Hash函数把key和数组下标进行转换，作用是把任意长度的输入通过散列算法转换为固定类型、固定长度的散列值
操作
写操作（put）
即在散列表中插入新的键值对（Entry/Node）
1、通过哈希函数，把key转化为数组下标
2、如果数组下标对应的位置没有元素，就把这个Entry填充到数组下标的位置
读操作（get）
通过给定的Key，在散列表中查找对应的Value
1、通过哈希函数，把key转化成对应的Value
2、找到数组下标所对应的元素，如果Key不正确，说明产生了hash冲突，则顺着头节点遍历该单链表，再根据Key即可取值
Hash冲突（碰撞）
由于数组长度有限，当插入的Entry足够多时，不同的key通过哈希函数获得的下标有可能是相同的，这种情况，叫做哈希冲突
解决方法
开放寻址法
原理是当一个key通过哈希函数获得对应的数组下标已被占用时，就寻找下一个空挡位置
ThreadLocal所使用的就是开放寻址法
链表法
数组的每一个元素不仅是一个Entry对象，还是一个链表的头结点，每个Entry对象通过next指针指向它的下一个Entry结点
当新的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可，默认next指向null
Hash扩容（resize）
说明
散列表基础数组实现，所以需要扩容
当经过多次元素插入，散列表达到一定饱和度，Key映射位置发生冲突的概率会逐渐提高，这样大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响
影响因素
Capacity
Hash表当前的长度
LoadFactor
Hash表的负载因子（阈值），默认为0.75f
当HashMap.Size >= Capacity * LoadFactor时，需要进行扩容
步骤
1、扩容，创建一个新的Entry空数组，长度是原数组的2倍
2、重新hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中
时间复杂度
写操作
O(1) + O(m) = O(m)，m为单链元素个数
读操作
O(1) + O(m) = O(m)，m为单链元素个数
hash冲突写单链表
O(m)
hash扩容
O(n)，n为数组元素个数
优点
读写快
缺点
元素是没有被排序的
Hash冲突，扩容，需要重新计算
应用
HashMap
JDK1.7中HashMap使用一个Table数组来存储数据，用key的hashcode取模来决定key会被存放到数组里的位置
如果hashcode相同，或取模后结果相同，则这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表
在极端情况下（如所有key的hashcode都相同），将会导致该链表很长，则put/get操作需要遍历整个链表，最差情况下时间复杂度为O(n)
针对JDk1.7的这个性能缺陷，1.8中table数组中可能存放的是链表结构，也可能存放红黑树结构
如果链表中结点数量不超过8个则使用链表存储，超过8个会调用treeifyBin函数，将链表转换为红黑树
即使所有key的hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要O(logn)的开销
字典
Redis字典dict又称散列表，是用来存储键值对的一种数据结构
Redis整个数据库使用字典存储的，对Redis的CURD操作其实就是对字典中的数据进行CRUD
Redis字典实现包括：Dict、dictht、dictEntry
布隆过滤器
可以用于检索一个元素是否在一个集合中，它的优点是空间效率和查询时间都远远超过一般的算法
位图
Bitmap基本原理就是用一个bit来标记某个元素对应的Value，而key即是该元素，由于采用一个bit来存储一个数据，因此可以大大节省空间
递归
概念
在数学和计算机科学中，指在函数定义中使用函数自身的方法
递归算法是一种直接或间接调用自身函数或方法的算法
本质
它是一种循环，且在循环中执行的就是调用自己，递归调用将每次返回的结果存在栈帧中
三要素
递归结束条件
函数功能
函数的等价关系式
递归公式，一般每次执行之间，或与个数之间的逻辑关系
时间复杂度
优点
代码简单
缺点
占用空间较大，如果递归太深，可能发生栈溢出，可能会有重复计算
应用
作为基础算法，应用非常广泛，如二分查找、快速排序、归并排序，树的遍历
回溯算法、分治算法、动态规划中也大量使用递归算法实现
二分查找
概念
也叫折半查找算法，当要从一个序列中查找一个元素时，二分查找是一种非常快速的查找算法
它是针对有序数据集合的查找算法，如果是无序数据集合就用遍历查找
本质
之所以快速，是因为它在匹配不成功时，每次都能排除剩余元素的一半，因此可能包含目标元素的有效范围收缩很快
时间复杂度
O(logn)
优点
速度快，不占空间，不开辟新空间
缺点
必须是有序数组，数据量太大没有意义
但数据量也不能太大，因为数组要占用连续空间
应用
有序的查找都可以使用二分法
2. 高级
树
概念
很多数据的逻辑关系并不是线性关系，实际场景中，常常存在一对多，甚至多对多的情况，这类数据结构称为树
定义
树是n(>=0)个节点的有限集
当n=0时，称为空树
n>1时，非根节点可分为m个互不相交的有限集，每个集合本身又是一个树，并称为根的子树
任意一个非空树，有且仅有一个特定的称为根的节点
树的最大层级数，本成为树的高度或深度
分类
二叉树
满二叉树、完全二叉树、平衡二叉树、二叉查找树
平衡二叉查找树
AVL树、红黑树
多路树
B树、B+树、2-3树、2-3-4树
堆
小顶堆、大顶堆、优先级队列、斐波那契堆、二顶堆
其他
树状数组、线段树
二叉树
概念
树的一种特殊形式，每个节点最多由2个孩子节点
二叉树的两个孩子节点，一个被称为左孩子，一个被称为右孩子，它们的顺序是固定的，左孩子小于右孩子
满二叉树
一个二叉树的所有非叶子节点都存在左右孩子，且所有叶子节点都在同一层级上，则这个树就是满二叉树
完全二叉树
对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号从1到n，如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则称为完全二叉树
满二叉树要求所有分支是满的，而完全二叉树只需保证最后一个节点之前的节点都齐全即可
存储
二叉树属于逻辑结构，可以使用链表和数组进行存储
链式
每一个节点包含3部分
存储数据的data变量
指向左孩子的left指针
指向右孩子的right指针
数组
会按照层级顺序把二叉树的节点放到数组中对应的位置上
如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来
寻址方式
一个父节点的下标是n，则它的左孩子节点的下标就是2*n+1，右孩子的节点下标是2*(n+1)
对于一个稀疏的二叉树来说，用数组表示法非常浪费空间，所以一般用链表存储实现（二叉堆除外）
二叉查找树
概念
在二叉树的基础上增加了几个条件
如果左子树不为空，则左子树所有节点的指均小于根节点的值
如果右子树不为空，则右子树上所有节点的值大于根节点的值
左、右子树也都是二叉查找树
二叉查找树要求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性
查找
对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，则搜索节点的时间复杂度是O(logn)，和树的深度是一样的
二叉树遍历
说明
二叉树是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同
方式
深度优先遍历
即偏向于纵深的访问方式
前序遍历
输出顺序是根节点、左子树、右子树
中序遍历
顺出顺序是左子树、根节点、右子树
后序遍历
输出顺序是左子树、右子树、根节点
广度优先遍历
按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点
时间复杂度
插入和查找时间均为：O(logn)
极端情况下二叉查找树退化为链表，时间复杂度为O(n)，所以需要平衡二叉查找树
应用
非线性数据
菜单、组织结构、家谱等
线性数据
二叉查找树，它是有序的，只需中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列，其性能非常稳定，扩容很方便（链表实现）
红黑树
概念
除了二叉查找树的特征外，还有以下特征
每个节点要么是黑色、要么是红色
根节点是黑色
每个叶子节点都是黑色的空节点（NIL节点）（为了简单起见，一般会省略该节点）
如果一个节点是红色的，则它的子节点必须是黑色的（父子不能同为红）
从任一节点到其每个叶子的所有路径都包含相同数据的黑色节点（平衡的关键）
新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡
在对红黑树进行添加或删除操作时可能会破坏这些特点，所以红黑树采取了很多方式来维护这些特点，从而维持平衡，主要包括：左旋转、右旋转和颜色反转
平衡方式
左旋 RotateLeft
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子
右旋 RotateRight
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子
颜色反转
即当前节点与父节点、叔叔节点同为红色，这违反了红黑树的规则，需要将红色向祖辈上传
父节点和叔叔节点红色变为黑色，爷爷节点从黑色变为红色
这样每条叶子节点到根节点的黑色节点数量并未发生变化，因此其他树结构不产生影响
插入情况
1、新节点位于树根，没有父节点
直接让新节点变色为黑色，规则2满足，同时黑色的根节点使得每条路径上的黑色节点数目都增加1，所以没有打破规则5
2、新节点的父节点是黑色
新插入的红色节点并没有打破红黑树的规则，所以不需要再做任何调整
3、新节点的父节点和叔叔节点都是红色
两个红色节点连续，违反规则4，因此让父节点变为黑色
此时父节点的路径多了一个黑节点，打破了规则5，因此让祖父节点变成红色
祖父节点和叔叔节点又称为连续红色节点，因此让叔叔节点变为黑色
4、新节点的父节点是红色，叔叔节点是黑色或没有叔叔，且新节点是父节点的右孩子，父节点是祖父节点的左孩子
以父节点为轴，做一次左旋，使新节点称为父节点，原父节点称为新节点的左孩子，进入情况5
5、新节点的父节点是红色，叔叔节点是黑色或没有叔叔，且新节点是父节点的左孩子，父节点是祖父节点的左孩子
以祖父节点为轴，做一次右旋，使父节点称为祖父节点，祖父节点称为父节点的右孩子
然后，让新的祖父节点变成黑色，原祖父节点变成红色
构建过程
时间复杂度
O(logn)
应用
在JDK1.8中HashMap使用数组+链表+红黑树的数据结构
内部维护着一个数组table，该数组保存着每个链表的表头节点或树的根节点
多路查找树
概念
其每一个节点的孩子数可以多于2个，且每个节点处可以存储多个元素
B树
概念
BalanceTree，是对二叉查找树的改进，它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数
特性
B树中所有节点的孩子节点中的最大值称为B树的阶，记为M
树中的每个节点至多有M课子树
如果定了M，则该B树中任何节点的子节点数量都不能超过M
若根节点不是终端节点，则至少有两棵子树
除根节点和叶节点外，所有节点至少有m/2棵子树
所有的叶子节点都位于同一层
B+树
B-树的变体，也是一种多路搜索树，定义基本与B树相同
特征
非叶子节点的子树指针与关键字个数相同
非叶子节点的子树指针P[i]，指向关键字值属于(K[i], K[i+1])的子树
为所有叶子节点增加一个链指针
所有关键字都在叶子节点出现
区别B树
最大区别在于非叶子节点是否存储数据
B树是非叶子节点和叶子节点都会存储数据
B+树只有叶子节点才会存储数据，且存储的数据都在一行上，且这些数据都是有指针指向的，即有序的
多叉平衡
B树的高度一般都是在2-4，树的高度直接影响IO读写的次数
如果是三层树结构，支撑的数据可以达到20G，如果是四层，支撑的数据可以达到几十T
典型应用
MySQL索引 B+树
B树为为了磁盘或其他存储设备而设计的一种多叉平衡查找树
相对于二叉，B树每个内节点有多个分支
二叉堆
概念
本质上是一种完全二叉树
二叉堆的根节点叫做堆顶
类型
大顶堆（最大堆）
其任何一个父节点的值，都大于或等于它左右孩子节点的值
下顶堆（最小堆）
其任何一个父节点的值，都小于或等于它左右孩子节点的值
存储原理
完全二叉树比较适合用数组来存储，用数组来存储完全二叉树是非常节省存储空间的
不需要存储左右子节点的指针，单纯通过数组下标，即可找到一个节点的左右子节点和父节点
典型应用
优先队列
利用堆求Top K问题
排序
分类
按时间复杂度
O(n^2)的排序算法
冒泡排序、选择排序、插入排序、希尔排序
O(nlogn)的排序算法
快速排序、归并排序、堆排序
线性的排序算法
计数排序、桶排序、基数排序
按稳定性
稳定排序
值相同的元素在排序后仍然保持着排序前的顺序
不稳定排序
值相同的元素在排序后打乱了排序前的顺序
冒泡排序
概念
最基础的排序算法，bubbel_sort，它是一种基础的交换排序
思想是把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置，当一个元素小于等于右侧相邻元素时，位置不变
时间复杂度
O(n^2)
快速排序
概念
也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的
相比冒泡，快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到另一边，从而把数列拆解成两个部分，这种思路叫做分治法
基准元素的选择
基准元素，pivot，分支过程中，以基准元素为中心，把其他元素移动到它的左右两边
首先可以随机选择一个元素作为基准元素，且让基准元素和数列首元素交换位置
方法
双边循环法
单边循环法
时间复杂度
O(nlogn)
堆排序
概念
指利用堆这种数据结构所设计的一种排序算法
堆是具有以下性质的完全二叉树
大顶堆
每个节点的值大于或等于其左右孩子节点的值
小顶堆
每个节点的值小于或等于其左右孩子节点的值
基本思想
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点，将其与末尾元素进行交换，此时末尾就是最大值
然后将剩余元素重新构造一个堆，重复上面的操作，就能得到一个有序序列
时间复杂度
O(nlogn)
计数排序
概念
利用数组下标来确定元素的正确位置
算法
适用
连续的取值范围不大的数组
不连续或取值范围过大会造成数组过大
时间复杂度
O(n + m)
n：数据个数
m：数据范围
桶排序
概念
同样是一种线性时间的排序算法
需要创建若干桶来协助排序
每个桶代表一个区间范围，里面可以承载一个或多个元素
算法
时间复杂度
O(n)
字符串匹配
说明
Java里用的indexOf函数，其底层就是字符串匹配算法
主要分类
单模式匹配
BF算法
RK算法
BM算法
KMP算法
多模式匹配
Trie树
AC自动机
BF算法
说明
Brute_Force，暴力匹配算法，也叫朴素匹配算法
算法
时间复杂度
每次都比对m个字符，要比对n-m+1次，所以该算法的最坏情况是O(n*m)
m：匹配长度
n：主串长度
应用
虽然BF算法效率不高，但在实际情况下却很常用，因为主串不会太长，实现简单
RK算法
概念
全称叫Rabin-Karp算法
每次检查主串与子串是否匹配，需要依次比对每个字符，所以BF算法的时间复杂度就比较高，是O(n*m)
对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低
思路
通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式的哈希值比较大小
如果某个子串的哈希值与模式串相等，就说明对应的子串和模式串匹配（暂不考虑哈希冲突问题）
因为哈希值是一个数字，数字之间比较是否相等非常快速，所以模式串和子串比较的效率就提高了
时间复杂度
O(m+n)
应用
适用于匹配串类型不多的情况，如：字母、数字或字母加数字的组合
BM算法
概念
它是一种非常高效的字符串匹配算法，滑动算法
本质上就是寻找一种规律，在模式串和主串匹配过程中，当模式串和主串某个字符不匹配时，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位
原理
坏字符规则
BM算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的
从模式串的末尾往前倒着匹配，发现某个字符没法匹配时，把这个没有匹配的字符叫做坏字符（主串中的）
当发生不匹配时，把坏字符对应的主串中的字符下标记作si，如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作xi（不存在：xi=-1），则模式串往后移动的位数等于si-xi
好后缀规则
把已经匹配的字符串{u}，在模式串中查找，如果找到了另一个跟{u}匹配的子串{u2}，那就将模式串滑动到子串{u2}与主串中{}u对齐的位置
如果在模式串中找不到另一个等于{u}的子串，就直接将模式串滑动到主串中{u}的后面，因为之前的任何以此往后滑动，都没有匹配主串中{u}的情况
当模式串滑动到前缀与主串中{u}的后缀有部分重合，且重合部分相等时，可能会存在完全匹配的情况
针对这种情况，不仅要看好后缀在模式串中是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的
选择
分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数
时间复杂度
O(n/m)
n：主串长度
m：模式串长度
应用
BM算法比较高效，实际开发中，特别在一些文本编辑器中，用于实现查找字符串功能
Trie树
概念
也叫“字典树”，是一个树形结构，一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题
Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起
Trie树的根节点不包含任何信息，每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（红色节点为叶子节点）
时间复杂度
如果要在一组字符串中，频繁地查询某些字符串，Trie树会非常高效
构建Trie树的过程，需要扫描所有字符串，时间复杂度是O(n)
但一旦构建成功后，后续的查询操作非常高效，每次查询时，如果查询的字符串长度是K，则只需要对比大约K个节点，就能完成查询操作
构建好Trie树后，在其中查询字符串的时间复杂度是O(k)，k为要查找的字符串的长度
典型应用
搜索关键字的提示功能
图
概念
一种复杂的非线性表结构
图中的元素叫做顶点（vertex）
图中一个顶点可以与任意其他顶点建立连接关系，这种关系叫做边（edge）
跟顶点相连接的边的条数叫做度（degree）
类型
有向图
边有方向的图叫做有向图
无向图
边无方向的图叫做无向图
带权图
每条边都有一个权重，可能通过这个权重来表示一些可度量的值
存储
图最直观的一种存储方法就是邻接矩阵（Adjacency_Matrix）
邻接表
用邻接矩阵来表示一个图，虽然简单直观，但是比较浪费存储空间
每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点
遍历
说明
遍历指从某个节点出发，按照一定的搜索路线，依次访问对数据结构中的全部节点，且每个节点仅访问一次
从给定图中任意指定节点出发，按照某种搜索方法沿着图的边访问途中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历，遍历过程中得到的顶点序列称为图遍历序列
搜索策略
深度优先搜索 DFS
从起点出发，从规定的方向中选择其中一个不断地向前走，直到无法继续为止，然后尝试另一种方向，直到最后走到终点
DFS解决的是连通性问题，即给定两个点，判断是否有一条路径能从起点连接到终点
时间复杂度
邻接表
访问所有顶点的时间为O(V)，而查找所有顶点的邻居需O(E)的时间，所以总复杂度是O(V+E)
邻接矩阵
查找每个顶点邻居需要O(V)的时间，所以查找整个矩阵需要O(V^2)
广度优先搜索 BFS
一种“地毯式”层层推进的搜索策略，即先查找里起始顶点最近的，然后是次近的，依次往外搜索
广度优先搜索，一般用来解决最短路径问题
时间复杂度
邻接表
每个顶点都要被访问依次，时间复杂度是O(V)，相连的顶点都要被访问依次，加起来是O(E)，整体复杂度为O(V+E)
邻接矩阵
V个顶点，每次都要检查每个顶点与其他顶点是否有联系，因此复杂度为O(V^2)
应用
广度优先的搜索可以同时从起始点开始进行，称之为双端BFS，这种算法往往可以大大提高搜索效率
算法思维
贪心算法
定义
一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法
当下做局部最优判断，不能回退
当下是最优的，并不一定是全局最优的
应用
由于贪婪算法的高效性以及所求的答案比较接近最优结果，它可以作为辅助算法或解决一些要求结果不特别精确的问题
经典问题
部分背包
某件物品是一堆，可以带走其一部分
时间复杂度
不考虑排序情况下，只需要依次循环，所以复杂度是O(n)
优点
性能高，能用贪心算法解决的往往是最优解
缺点
在实际情况下能用的不多，且解的往往不是最好的
适用场景
针对一组数据，定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大
每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据（局部最优而非全局最优）
分治算法
概念
分而治之，也就是将原问题划分为n个规模较小，且结构与原问题相似的子问题，递归地解决这些子问题，然后合并其结果，得到原问题的解
区别递归
分治算法是一种处理问题的思想，而递归是一种编程技巧
分治算法的递归实现中，每层递归都会涉及三个操作
分解
将原问题分解成一系列子问题
解决
递归地求解各个子问题，若子问题足够小，则直接求解
合并
将子问题的结果合并成原问题
时间复杂度
根据拆分情况可以是O(n)或O(logn)
优点
将复杂的问题拆分成简单的子问题，解决更容易，另外根据拆分规则，性能有可能提高
缺点
子问题必须要一样，用相同的方式解决
适用场景
分治算法能解决的问题，一般都满足
原问题与分解的小问题具有相同的模式
原问题分解的子问题可以独立求解，子问题之间没有相关性
这是分治算法和动态规划的明显区别
具有分解终止条件，即问题足够小时，可以直接求解
可以将子问题合并成原问题，且合并操作的复杂度不能太高，否则就起不到减小算法总复杂度的效果
回溯算法
概念
实际上类似枚举的深度优先搜索尝试的过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径
枚举所有的解，找到满足期望的解，为了有规律地枚举所有可能的解，避免遗漏和重复，可以把问题求解的过程分为多个阶段，每个阶段，都会面对一个岔路口，先随机选一条路，当发现该路走不通是，就回退到上一个岔路口，另选一条走法
时间复杂度
O(n!)
优点
思想非常简单，大部分情况下，都是用来解决广义的搜索问题，即从一组可能的解中，选择出一个满足要求的解
非常适合用递归来实现，在实现过程中，剪枝操作是提高回溯效率的一种技巧
缺点
效率相对低（动态规划）
适用场景
基本上能用动态规划、贪婪解决的问题，都可以用回溯算法
它相当于穷举搜索，穷举所有的情况，然后对比得到最优解
但是，回溯算法的时间复杂度非常高，是指数级的，只能用来解决小规模数据的问题
动态规划
概念
一种分阶段求解的方法，是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式取解决
说明
首先是拆分问题，根据问题的可能性把问题划分成一步一步，这样可以通过递推或递归来实现
有时很容易直到，如果只有一种情况时，最佳的选择应该怎么做，然后根据这个最佳选择往前一步推导，得到前一步的最佳选择
然后就是定义问题状态和状态之间的关系，即前面拆分的步骤之间的关系，用一种量化的形式表现出来
类似于推导公式，因为这种公式很容易用程序写出来（即状态转移方程式）
找到最优解后，应该将其保存下来，为了往前推导时能够使用前一步的最优解
每次都把最优解保存下来，大大降低了时间复杂度
重要概念
最优子结构
边界
状态转移公式dp方程
适用步骤
1. 把当前的复杂问题转化成一个个简单的子问题
2. 寻找子问题的最优解法
最优子结构
3. 把子问题的解合并，存储中间状态
4. 递归+记忆搜索或自底而上的形成递推方程（DP方程）
优点
时间复杂度和空间复杂度都相当低
缺点
难，有些场景不适用
适用场景
并不是所有问题都可以用动态规划来解决，能够用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题
分治算法要求分隔的子问题不能重复，而动态规划正好相反
0 条评论
下一页
