数据结构与算法
2023-12-01 17:46:02 0 举报AI智能生成
登录查看完整内容
go版本的代码实现
作者其他创作
大纲/内容
时间复杂度
空间复杂度
在一个待排序的数据中存在多个值相等的元素，经过稳定算法排序之后，相等元素之间的原有的先后顺序不变
稳定性
不需要申请新的存储空间来存储待排序数据
原地排序空间复杂度不一定是 O(1)
空间复杂度为 O(1)的排序算法肯定是原地排序算法
原地性
稳定排序
要点
每个元素和相邻的元素比较，不符合条件的交换位置
原理
代码实现
最好情况：O(n)，完全顺序
最坏情况：O(n^2)，完全逆序
平均时间复杂度 O(n^2)
O(1)
原因是只是在本地进行交换，并没有行进多余的空间创建
是
是不是原地排序
是不是稳定排序
算法分析
冒泡排序
将数组中的数据分为：已排序区间 和 未排序区间
初始已排序区间只有一个元素，就是数组中的第一个元素
核心思想是：取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入(遍历倒序已排序区间)，保证已排序区间数据一直有序
最好情况：O(n)，数据是顺序的
最坏情况：O(n^2)，数据是逆序的
平均时间复杂度：O(n^2)
是否是原地排序
是否是稳定排序
插入排序
讲数组划分为 已排序区间 和 未排序区间初始，已排序区间为空，未排序区间为整个数组遍历未排序区间，找到最小的元素放入到已排序区间的末尾
平均时间复杂度O(n^2)
否
它对比数据之后是有一个交换操作，比当前数小就会交换[2，6，4，2，3，1] 第一次交换后[1，6，4，2，3，2]原来的 2 挪到最后去了，并且它之前还有一个2，这个2会优先操作
选择排序
把一个数组从中间分成两部分，分别对其进行排序，然后把两个已经排序好的数组合并
递归，问题拆分成最小子问题，这里的数组，最后就拆分成了一个元素一个数组
O(nlogn)
O(n)
因为有个临时数组 tmp
归并排序
随机取数组中一个值，以它为中点，然后把数组比分为两部分，一部分比它大，一部分比它小
一般这个中点是数组中最后一个值，把比中点小的放左边
然后一直去重复这个操作，到最后把中点放到最后一个比它小的值后面
最好情况：O(nlogn) 分区每次都平均分成2份
如 1，3，5，6，8
越有序，排序越慢
最坏情况：O(n^2) 中点极端，一个数组非常大，一个数组非常小
平均情况下：O(nlogn)
O(logn)
6，8，7，6，2，9，4
快速排序
排序
条件：有序数组
在数组中找一个中点，然后和对比值比较
如果中点比对比值大，则在前半部分查找
如果中点比对比值小，则在后半部分查找
一直到找到和对比值相等的元素，如果最后没找到，返回-1
循环条件永远是：low<=high or p<=r
对于 low==high 必要时特殊处理，在 while 内部补充退出条件 ，这条适用于某些变种问题
返回值永远是mid，而不是 low 、high
low、high 的更新永远是 low=mid+1和high=mid-1
对于非确定性查找，使用前后探测法，来确定搜索区间
先处理命中情况，再处理在左右半部分查找的情况
最好情况：O(1)
最坏情况：O(logn)
平均情况下：O(logn)
二分查找适合数据量适中的数组去查询
常用场景
查找第一个值等于给定值的元素
查找最后一个值等于给定值的元素
查找第一个大于等于给定值的元素
查找最后一个小于等于给定值的元素
问题拆分成：顺序区间，循环顺序区间
然后做对应的处理
如果target 在 非顺序区间，那就在非顺序区间处理，target 最终是会落到顺序区间的
寻找旋转排序数组中的给定值
寻找旋转排序数组中的最小值
有重复数据的循环有序数组中查找给定值
思路：把数组分成山的两侧，一侧是左边，一侧是右边
然后命中目标的条件是 mid>mid-1 && mid > mid+1
查找峰值
二分答案
二分查找的变形
二分查找
利用二进制位来表示，位图存的是范围，每次设置的都是位图的最大范围
如有1千万的数据，数据是32位的整型数，存储需要大约40M（32位，1字节=8位，每个数据是4字节，1千万*4字节/1024/1024约等于40M）
使用位图，如果数字范围是在1到1亿之间，取最大值，1亿个二进制位，（1亿/8位/1024/1024约等于12M）
分析
大数据量节省内存（数据分布均匀）
无重复数据可以直接排序，时间复杂度为O(n)
优点
如果数据的元素的范围特别大（数据分布不均匀），那么很消耗内存
元素不是整型的时候，不适用
比如1千万数据，数据为32位整数型，数字范围是1到10亿，那么取最大值，10个二进制位，（10亿/8位/1024/1024约等于120M）
缺点
index = num/8
remainder=num%8
增：bit[index] |= 1<< remainder
查：(bit[index] & (1<< remainder))!=0
删：bit[index] &^= 1<<remainder
位图
基于位图实现，利用哈希冲突（设计多个哈希函数），减少存储空间带来的问题
基于位图实现
实现多个hash函数，来分别计算元素应该存储在哪一位上
不需要100%准确的，允许存在小概率误判的大规模判重场景
请求特别大的时候，查询数据库前，先查布隆过滤器，如果数据不存在，就不需要访问数据库，这样来减少数据库的操作
如 某个数据是否存在数据库中，uv去重，防止缓存穿透等
使用场景
快速判重、节省内存，对位图的优化，属于CPU密集型
会误判，不适合高精的判重场景
例如：3123和1123 哈希值相同，位图中存储了 3123，没有存储1123，那查询1123也会返回true
判定存在，有可能不存在
例如查询3123 返回false，那就3123不存在
判定不存在，那肯定不存在（主要使用这个特点）
特点
布隆过滤器
特殊存在
散列表/哈希表
没有父节点的结点是根节点
根节点
比如根节点，它有左右两个子节点，相对于子节点来说，他是两个子节点的父节点
父节点
父节点下的节点
子节点
右子节点和左子节点可以互相叫为兄弟节点
兄弟节点
把没有子节点的节点叫叶子节点
叶子节点、叶节点
节点到叶子节点的最长路径（边数）
节点的高度
根节点到这个节点所经历的边的个数
节点的深度
节点的深度+1
节点的层数
根节点的高度
树的高度
概念
有两个叉的树，也就是两个子节点
左子节点和右子节点
二叉树
除了叶子节点外，其他的所有节点都有左右两个子节点
满二叉树
和满二叉树稍微有些不同，只要是最后一排子节点的叶子节点是顺序缺失的就是完全二叉树(除了最后一排子节点外，其他的子节点都是满的)
完全二叉树
分类
完全二叉树>平衡二叉树>近似平衡二叉树
各个操作的性能
维护平衡的成本
在工程中使用红黑树，这种近似平衡二叉树的原因是，能降低维护平衡的成本，并且操作性能也不差
树
分辨是不是完全二叉树还有一个小技巧，把二叉树的节点落在数组中
如果数组中间没有空洞，那就是完全二叉树
如果数组中间有空洞，那就不是完全二叉树
分辨小技巧
BST
二叉搜索树
平衡二叉树\\VAL
图
二叉树图
代码
基于指针存储
只适合于完全二叉树、堆、线段树
根节点存储在下标为1的位置
左子节点位置为 2*i
右子节点位置为 2*i+1
父节点位置 i/2
存储方法(根存储在下标为1的位置)
左子节点位置为 2*i+1
右子节点位置为 2*i+2
父节点位置 (i-1)/2
存储方法2(根存储在下标为0的位置)
基于数组存储
存储方式
先当前节点，然后左子节点，然后右子节点
前序遍历
先左子节点，然后当前节点，然后右子节点
中序遍历
先左子节点，然后右子节点，然后当前节点
后序遍历
这里的前序，中序，后序说的就是当前节点在遍历中的位置，前序就第一个是当前节点，中序就当前节点在中间，后序就是当前节点在最后
三种遍历方法图
遍历方法
log2^n次方
最优时间复杂度
O(n) 二叉树成了一条线的链表
最坏时间复杂度
一种特殊的二叉树，支持快速查找、插入、删除数据
左子树中的每个节点的值，都小于父节点的值
右子树中的没个节点的值，都大于父节点的值
在二叉树中的任意一个节点
如果出现反着来的，那么上面的条件也反过开
如果比根节点小，从左子树查找
如果比根节点大，从右子树查找
查找操作
要插入的数据比当前节点的值小，且当前节点左子树为空，直接把数据插入到左子节点的位置
如果左子树不为空，继续递归左子树，直到找到左子树为空的位置
右子树一样
插入操作
直接把父节点中指向要删除节点的指针指向null即可
第一种情况：被删除的节点没有子节点
把父节点中指向要删除节点的指针，重新指向要删除节点的子节点即可
第二种情况：被删除的节点只有一个子节点
找到这个节点的右子树中的“最小节点”或者左子树中的“最大节点”，把它替换到要删除的节点上
然后再删除掉这个“最小节点”或者“最大节点”
如果用“最小节点”，那么它肯定没有左子节点，所以，可以应对第一种和第二种情况来处理
如果用“最大节点”，那么它肯定没有右子节点，所以，也可以应对第一种和第二种情况来处理
第三种情况：被删除的节点有两个子节点
二叉树的查找、插入、删除性能，跟书的高度成正比
时间复杂度位于 log2^n ~ h 之间
二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于log2^n情况
从而各个操作效率下降，极端情况下，二叉树退化为链表，时间复杂度退化为O(n)
复杂度分析
删除操作
任意一个节点的左右子树的高度相差不能大于1
红黑树
近似的树
log2^n
平衡二叉查找树/AVL树
二叉搜索树\\查找树
一、堆必须是一个完全二叉树
二、堆中的每个父节点的值必须大于等于(或者小于等于)左右子树中每个节点的值
大顶堆：堆中每个节点的值都大于等于其左右子树中每一个节点的值
小顶堆：堆中每个节点的值都小于等于其左右子树中每一个节点的值
存储：堆事完全二叉树，适用于数组来存储
定义和存储
左子节点位置 2*i
右子节点位置 2*i+1
以根节点为下标1的数组
左子节点位置 2*i+1
右子节点位置 2*i+2
以根节点为下标0的数组
计算父节点和子节点位置方法
自上而下的操作
自下而上的操作
操作
先插入数据
对比插入值和父节点的大小，如果堆是大顶堆，哪个值大哪个就在父节点，小的成为子节点
如果是小顶堆，把小的那个放到父节点
然后自下而上的堆化
操作方法：
最好情况 O(1) 插入之后不需要堆化
最坏情况 O(h) h是堆的高度
插入数据
取堆顶元素
先把最后一个节点替换到堆顶，然后删除原有堆顶
判断左右子节点和父节点，三个中哪个最大，把大的交换到父节点
然后自上而下的堆化
最优时间复杂度O(1)
最坏时间复杂度O(h)
删除堆顶元素
更新之后的值变小了，进行自上而下的堆化
更新之后的值变大了，进行自下而上的堆化
操作方法
更新元素值
堆
基于堆
先建堆，把数组中的元素原地组织成一个堆
然后再基于堆进行排序
从前往后处理每个元素，对每个元素执行自下而上的堆化
时间复杂度O(nlogn)
第一种方法
从后往前处理每个元素，对每个元素执行自上而下的堆化
时间复杂度O(n)
第二种方法
建堆
将堆顶元素与最后一个元素交换，最大元素就放到了下标n的位置，堆大小 -1
交换之后的堆顶元素，自上而下堆化，重新构建成堆
一直重复这个过程，直到最后堆中只剩下一个元素，排序工作就完成了
因为他会把元素重复的哪来放在堆顶
堆排序
匹配过程，模式串和主串的匹配过程，模式串在主串中不停地往后滑动
暴力算法
分为主串和模式串(就是短的那个匹配串)
让模式串在主串中一个一个的去对比，直到全部匹配
BF算法
Rabin-Karp 算法
通过哈希算法对主串中的 n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较
n代表主串的长度，m表示模式串的长度 n-m+1 是主串按照模式串的长度分割，主串的最后m个不能分割，视为1，所以主串能分割n-m+1个子串
哈希算法，普通的哈希算法太复杂，RK算法设计了一套利用当前子串来算出下一个子串的哈希算法
模式串不能太长
缺点：
比如主串，模式串是由26个字母组成
我们用26进制来做哈希算法
比如 h[i] = \"dfc\"，那么h[i]的哈希函数为 ('d'-'a')*26^2+('f'-'a')*26^1+('c'-'a')*26^0
h[i+1]=\"fca\
h[i]的哈希公式为 (26^(m-1))*(s[i]-'a')+(26^(m-2))*(s[i+1]-'a')+...++(26^0)*(s[i+m-1]-'a')) 这里的s代表着字符串
h[i+1]的哈希公式为 (26^(m-1))*(s[i+1]-'a')+...+(26^(1))*(s[i+m-1]-'a')+(26^(0))*(s[i+m]-'a')
所以h[i+1]的哈希公式为 (h[i] - (26^(m-1))*(s[i]-'a'))*26+(26^(0))*(s[i+m]-'a')
哈希函数可以根据 h[i]返回 h[i+1]的哈希值
RK的哈希算法思想：
RK算法 掌握就好，不需要写
遇到不匹配的字符时，讲模式串往后滑动一位，然后模式串的第一位开始重新匹配
BF和RK的做法
最好情况下时间复杂度O(n/m)，n是主串的长度，m是模式串的长度
最坏情况下，O(n)
复杂度
寻找某种规律，借助这种规律，当模式串和主串中的某个字符不匹配时，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位
BM和KMP的做法
BM和KMP算法
在字符串 abcdefg 中查找字符串 abc
单模式串匹配
在字符串 abcdefghijk 中查找字符串 abc，def，ijk
可以用 Trie树 和 AC自动机，首选AC自动机
多模式串匹配
适合前缀匹配
Trie树是一颗多叉树，根节点不包含字符，其他每个节点表示字符串中的一个字符，从根节点到红色节点的一条路径表示字符串集合中的一个字符串
Trie树图
完全匹配
代替方案：红黑树，散列表
字符串查找
优先使用AC自动机
例如自动提示，搜索引擎、输入法、浏览器
前缀匹配
应用场景
Trie树
字符串匹配
是DFS和动态规划的基础
需要用到递归
解决穷举问题
枚举所有的解，找出其中满足期望的可行解
为了枚举所有可能的解，避免遗漏和重复，可以把问题求解的过程归纳为多阶段决策模型
每个阶段的决策会对应多个选择，从可选的选择列表中，任意选择一个，然后继续进行下一个阶段的决策
回溯的处理过程是一个穷举的过程。
回溯穷举所有解来查找可行解的过程，就是在决策树中进行遍历的过程
遍历过程中记录的路径就是解
整个决策的过程，如果用图像形象话表示，就是一颗决策树
递的过程进行函数调用，对应到递归树上为从一个节点进入它的子节点
归的过程进行函数调用返回，对应到递归树上是从子节点返回上一层节点
回溯一般使用递归来实现，递归树和决策树完全一样
核心思想
源码
代码模板
思路：暴力遍历把元素拆分成树，类似于二叉树那样的遍历
全排列
思路：检查每一的每个位置能不能放皇后，直到找到能放皇后的位置为止
能放皇后的位置：在随意一个位置检查当前位置的整列，左上角对角线，右上角对角线，只要有任何一条线上有皇后，就不可以放皇后，否则就可以放
N皇后
思路：也是暴力遍历，只不过把是把总重量不超过规定重量的最大值即可
决策树就是装和不装两种关系
0-1背包问题
思路：和N皇后思路差不多，检查每一个要插入的位置的行，列，块（所在的小九宫格）是否有重复元素，没有就插入
不一样的地方，借助位图，来判断行，列，块里的位置有没有元素和查找重复元素
数独问题
思路：把整个数组拆成决策树来遍历，那么就会出现两种情况，选与不选
子集问题
和子集问题相思，不过是先把数转换成类似数组，然后进行决策树来遍历，选与不选
组合问题也是一种全排列问题
组合问题
常见算法
回溯（重点）
微博、微信、Linkedln 等可以互加好友的
图的算法：图的搜索，最短路径、最小生成树、二分图等
应用：
图是一种非线性表数据结构
图中的元素被称为“顶点”
图中的顶点可以和任意其它顶点建立连接关系，这种关系我们叫“边”
ABCDEF叫顶点，他们之间的线叫做边
什么是图
无向图就是没有指向，他默认是双向的
无向图
边带指向的图叫有向图
定义
有几条指向这个顶点的边就说明有几个入度
入度
这个顶点有几条边指向别的顶点就说明有几个出度
出度
度
比如A有一个入度，2个出度
有向图
每条边有一个“权重”
通过这个权重表示某种关系度，亲密度等
A，C 的边权重是5，这个图是个无向图
带权图
底层依赖一个二维数组
他把两个顶点组合成一个二维数组，比如1，3之间有边
邻接矩阵
底层是一个链表加数组构成
数组的下标表示图的顶点，数组的链表表示了该顶点的指向顶点，有可能是一个，有可能是多个
邻接表有邻接表和逆邻接表
用来表示你关注了谁
邻接表
用来表示谁关注了你
逆邻接表
社交使用场景
邻接表：1关注了2，2关注了3，5，4，逆邻接表：1被4关注了，2被1，4关注了
链表构成
不适合快速判断两个用户间是否关注与被关注
基础邻接表
使用跳表
支持快速查找，插入，删除
时间复杂度 O(logn)
空间复杂度 O(n)
跳表有序，分页获取粉丝列表或关系列表非常高效
优化版
可以通过 哈希算法 等数据分片方式，将邻接表存储在不同的机器上
或者利用外部存储，持久化到存储关系数据库，在表上建立多个索引
用邻接表存储在不同服务器
邻接表的优化
邻接矩阵存储方式
邻接表（内存中存储，可以使用邻接表）
关系型数据库（图需要持久化就需要关系型数据库）
图数据库（超大图，并且设计大量图计算，用专业的图数据库）
存储图的方式
BFS
DFS
搜索 or 遍历
针对有权图的单源最短路径算法，并且要求没有负权边
Dijkstra
针对有权图的单源最短路径算法，允许存在负权边
Bellman-Ford
针对有权图的多源最短路径算法，允许存在负权边，但不允许负权环
Floyd
启发式搜索算法，求有权图的次优最短路线
A*算法
最短路径
Prim 算法
Kruskal 算法
最小生成树
Ford-Fulkerson
Edmonds-Karp
最大流、二分匹配
图上常用的算法
Breadth-First Search 广度优先算法
树是图的一种特殊情况
二叉树的按层遍历，实际上就是广度优先搜索，先遍历与根节点近的，再逐层与根节点远的
图的广度优先搜索和树上的按层遍历很像，先查找离起始顶点最近的，然后是次近，依次往外搜索，直到找到终止顶点
二叉树广度优先遍历（层序遍历）使用的是队列，顶点的下一层是2*i和2*i+1
图的广度优先搜索也要用到队列
图的按层遍历，需要用一个 visited 数组，记录已经遍历过的顶点，这是为了防止图中存在环，出现循环遍历多次的情况
思路：
Depth-First-Search 深度优先算法
类似于树的递归，前中后序遍历
DFS&BFS（深度和广度优先算法）搜索/遍历
解决穷举但是有重复子问题的
背包问题（0-1、完全、多重、二维费用、分组、有依赖）
路径问题
打家劫舍&股票买卖
爬楼梯问题
匹配问题（LCS、编辑距离）
其它（LIS）
经典模型
使用于可以用回溯解决，但是有重复字问题的
适用问题
需要穷举搜索才能得到结果的问题
能用动归解决的问题都能用回溯解决
能用回溯解决的问题不一定能用动归解决
最值、可行、计数
可用回溯解决
是否能将问题求解过程分为多个阶段
构建多阶段决策模型
是否有多个路径到达同一状态
查看是否存在重复子问题
如何记录每一阶段的不重复状态
int dp[n][w+1]记录每一阶段可达的所有状态
dp[i][j]表示第 i 个物品决策完之后，存在背包中物品重量为 j ，对应的最大物品价值
二维费用背包
定义状态 （难点）
找到如何通过上一阶段的状态推导出下一阶段的状态
定义状态转移方程 （难点）
辅助理解，验证正确性，确定状态转移的初始值
画状态转移表
问题：对于一组不同重量的物品，选择其中一些物品装入背包，在不超过背包最大重量限制的前提下，背包中可装物品总重量的最大值是多少？
1、可以用回溯解决， 穷举问题
2、构建多阶段决策模型：每一阶段决策一个物品是否放入背包
3、查看是否存在重复子问题：某一阶段背包中物品重量为cw，可以通过不同路径到达
4、定义状态：var dp[n][w+1] bool 记录每一阶段可达的所有状态dp[i][j]=true 表示第i个物品决策完之后，存在背包中物品重量为j这种状态
dp[i][j]=dp[i-1][j]||dp[i-1][j-weight[i]]
5、定义状态转移方程：
6、画状态转移表：辅助理解，验证正确性，确定状态转移的初始值
7、写代码
问题：对于一组不同重量、不同价值的物品，选择其中某些物品装入背包，不超过背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少？
二维费用背包问题
问题：有N个物品，选择其中一些物品装入背包，在不超过背包最大重量限制的前提下，背包中可装物品总重量的最大值是多少？
var dp [n][w+1]bool 记录每阶段可达状态
dp[i][j]=true 表示第 i 个物品决策完之后背包重量为 j 这个状态可达
状态：
dp[i][j]=dp[i-1][j] || dp[i-1][j-weight[i]]
状态转移方程：
最值
问题：有n个物品，选择其中一些物品装入背包，正好装满背包所需物品的最少个数？（如果装不满，返回-1）
var dp[n][w+1] int 记录每个阶段可达状态，就是记录每个阶段最少物品个数
dp[i][j] 表示第 i 个物品决策完，重量为 j ，对应的最少物品个数
问题： 有n个物品，选择其中一些物品装入背包，能不能正好装满背包？
可行
问题：有n个物品，选择其中一些物品装入背包，装满背包有多少种不同的装法？
var dp [n][w+1]int 记录每阶段可达重量对应的装法个数
dp[i][j]表示第 i 次决策完之后，背包重量为j，对应有几中装法
dp[i][j]=dp[i-1][j]+dp[i-1][j-weight[i]]
状态转移方程
计数
动态规划代码
解题步骤
使用二维的滚动数组来替代dp数组
只使用一维数组来代替二维数组
空间优化
DP专题
动态规划
数组
链表
栈
队列
线性结构
非线性结构
数据结构
排序算法
顺序查找
哈希查找
查找算法
算法
数据结构与算法
0 条评论
回复 删除
下一页
