tags
type
status
date
slug
summary
category
password
icon

# 数据结构

数据结构(data structure)就是数据的组织和存储形式。描述一个数据结构，需要指出其逻辑结构、存储结构（数据在物理存储器上存储的方式）和可进行的操作
逻辑结构：集合结构、线性结构、树结构、图结构
存储结构：顺序结构、链接结构、索引结构、散列结构

# 线性表

元素类型相同，所占内存长度相同，分为顺序表和链表
顺序表支持随机访问
顺序表比链表更加Cache友好
为了防止链表悬空，可以加入一个空的头结点
队列的实现（也是python实现list的方式）：可以先开一个有限空间的循环队列（空置一个位置，不然没法判断head=tail到底是空时满），如果一次push之后超过范围，就新开一个k(如1.2)倍的空间，把整个队列复制过去。这样平均复杂度是O(1)的。
也可以用两个栈实现队列。执行push(x)操作时，将x压入栈inStack，执行pop()或front()操作时，看另一个栈outStack是否为空，若不为空，弹出栈顶元素或访问栈顶元素即可；若为空，则先将inStack中的全部元素弹出并依次压入outStack，然后再弹出或访问outStack的栈顶元素。
库：collections中的deque

# 递归

注意在递归时不要直接传递整个数组，那样每次传递复杂度都是O(n)，可以用闭包把数组放在外层函数，内层只传递位置信息

# 动态规划

能用动规解决的问题的特点：
  1. 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。（否则无法用一样的方法求出子问题的解）
  1. 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。（否则说明状态还要扩展）

记一次动态规划的优化

  • 题面
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 正整数n的这种表示称为正整数n的划分。
输入
标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。(0 < N <= 50, 0 < K <= N)
输出
对于每组测试数据，输出以下三行数据:第一行: N划分成K个正整数之和的划分数目第二行: N划分成若干个不同正整数之和的划分数目第三行: N划分成若干个奇正整数之和的划分数目
  • 想法一
f[n][k][max]表示把n分成k份，其中ni的最大值恰好为max的方法数
从大到小分，枚举这次从i里面分出x（且最大值就是x因为从大到小），那么剩下的数自然是i-x，剩余次数为j-1，把f[i - x][j - 1][max ≤ x]的全部加到f[i][j][x]上就行
对于后面两个问题，略微改变循环的边界即可，最后再对k求和
递推完备性：算f[i][j]的时候，比i小、比j小的状态一定都已经确定
答案会算重吗？不同的max一定是不同方案，归纳可证不会重复
  • 想法二
对于后面两个问题，其实k根本不重要，f[n][max]表示把n分解且最大值恰好为max的方法数，于是有以下n^3递推
  • 想法三
既然上面要对max≤x的求和，干嘛不搞个前缀和呢，于是优化到n^2
此时，f[n][max]表示把n分解，且最大值不超过max的方法数。注意的是，在x的循环中计算的还是恰好为max的方法数，因为如果此时把>max的也更新，复杂度又会来到n^3。而在x循环完之后一起加则解决了这个问题。
  • 想法四
能不能把问题一也优化优化呢？联想到组合数分组问题里，≥好约束，直接把总数去掉一些就行；而≤却难以约束。所以能不能从小到大选呢？f[n][k]表示把n分成k份，且每个数≥1的方案数
其中，i-x-(x-1)*(j-1)就是把x去掉之外，再把剩下的数≥x的约束直接反映到“n”这项上。而这就要求x*j≤i，因此可以缩减x的范围，这样复杂度为
至此，已经能通过本题
  • 想法五-还能更简单
想法四的瓶颈在于，必须同时枚举最小数x并且确定“这一个就是它了”，但其实也可以不确定。
f[i][j] = f[i - 1][j - 1] + f[i - j][j]
分两种情况计数：一种min=1，则就是f[i - 1][j - 1]，与想法四x=1情况相同；如果min>1，那么f[i - j][j]就是后面所有x的情况下的总和，这里j没有减1，所以使得当前这个可以取遍2~i//j
  • 后记
为什么问题2和3的答案总是相同呢？有没有证明？

# 二叉树

二叉树是有限个元素的集合。空集合是一个二叉树，称为空二叉树。一个元素(称其为“根”或“根结点”)，加上一个被称为“左子树”的二叉树，和一个被称为“右子树”的二叉树，就能形成一个新的二叉树。要求根、左子树和右子树三者没有公共元素。
二叉树的左右子树是有区别的
结点的度(degree)：结点的非空子树数目。也可以说是结点的子结点数目。 叶结点(leaf node)：度为0的结点。 分支结点：度不为0的结点。即除叶子以外的其他结点。也叫内部结点。（包括根） 祖先(ancestor)：从父节点到根的所有节点，包括根 子孙(descendant)：与祖先相反 兄弟结点(sibling)：父结点相同的两个结点，互为兄弟结点。 结点的深度(depth)、层次(level)：树根是第0层的。如果一个结点是第n层的，则其子结点就是第n+1层的。 二叉树的高度(height)：二叉树的高度就是结点的最大深度。只有一个结点的二叉树，高度是0。结点一共有n层，高度就是n-1。
完美二叉树(perfect binary tree)：每层都填满 完全二叉树(complete binary tree) 满二叉树(full binary tree)：没有1度结点的二叉树（采用国际定义）
任意二叉树中，n0=n2+1
非空二叉树中，空子树数目等于其结点数目加1 （空子树=2n0+n1=n0+n2+1+n1=n+1）
完全二叉树中，n0=floor((n+1)/2)（因为完全二叉树中n1=0或1），n=2n0-1或2n0，且两种一定均能构建
非递归中序遍历

# 堆

区别于二叉搜索树！堆只要求儿子>父亲，是完全二叉树；而二叉搜索树不一定
原地建堆：把list看成一棵完全二叉树，从倒数第二层开始依次进行“下沉”操作。复杂度O(n)

# 并查集

f[getf(y)] = getf(x)两边都要到根

# 二叉搜索树

key的关系：Left<Root<Right
  • 添加
      • 根节点的key==x，则直接更改根节点信息；否则如果key>x则进入左子树，key<x则进入右子树
  • 删除
    • 节点为叶子节点：直接删除
    • 节点只有左儿子：左儿子替代该节点的位置
    • 节点只有右儿子：右儿子替代该节点的位置
    • 节点即有左儿子又有右儿子：找左子树中最大者（从左儿子开始一直向右走）or右子树中最小者（从右儿子开始一直往左走），用它覆盖要删除的节点并删除它（化归为前3种情况，因为找到的这个节点不可能既有左儿子又有右儿子）

# 平衡树

在二叉搜索树的基础上，在每个节点引入平衡因子(Balance Factor, BF)，定义为左子树高度-右子树高度。在任意一次操作完成后，总是保证BF在-1,0,1中，即左右子树高度差不超过1
  • 添加
      • 按二叉搜索树方法先加入节点，然后从下到上依次更新从新节点到根的BF。具体地，讨论两种情况：
    • cur的BF从0变成+-1，则显然以cur为根的子树高度+1，因此cur的父亲BF应+1（cur为左儿子）或-1（cur为右儿子）
    • cur的BF不变，或者从+-1变成0，则cur的父亲不用变
      • 如果更新过程中发现cur.BF不在-1,0,1中，则触发调整。调整后一定有cur.BF=0，因此所有祖先的BF都不用变。由此可看出，添加一个节点时至多进行一次旋转操作。
  • 旋转
      • 分四种

# KMP

nxt[i]表示1~i的子串的前后缀长度。如ABABA，nxt[3]=1。也就是说，从nxt+1开始匹配
实际上，把第二段匹配的代码改成a[pa]与b[pb+1]匹配而不是a[pa]与b[pb]匹配，代码一致性会更高

#图

无向图两个顶点之间最多一条边，有向图两个顶点之间最多两条方向不同的边。 无向图连接顶点u,v的边，记为(u,v) 有向图连接顶点u,v的边，记为<u,v>
路径的长度：路径上的边的数目 简单路径：除了起点和终点可能相同外，其它顶点都不相同的路径
度：相连的边的数量（有向图则为入度+出度）
连通无向图：图中任意两个顶点u和v互相可达。
强连通有向图：图中任意两个顶点u和v互相可达。【带“强”的都是对有向图而言的】
子图：从图中抽取部分或全部边和点构成的图
网络：带权无向连通图
连通分量（极大连通子图）：无向图的一个子图，是连通的，且再添加任何一些原图中的顶点和边，新子图都不再连通。
无向图的极小连通子图(去掉一条边就不连通的子图)就是生成树
强连通分量：有向图的一个子图，是强连通的，且再添加任何一些原图中的顶点和边，新子图都不再强连通。
  • dfs复杂度：邻接矩阵O(V^2)，邻接表O(V+E)
  • Prim：每次找一条权值最小的边，两个点一个在树内，一个不在树内。
      • 维护Dist数组，Dist[i]表示Vi到T的“距离”，即Vi和T中所有的点的连边的最小权值，开始所有Dist[i] = 无穷大, T 为空集
      1) 若|T| = N，最小生成树完成。否则取Dist[i]最小的不在T中的点Vi, 将其加入T
      2) 松弛操作：更新所有与Vi有边相连且不在T中的点Vj的Dist值：Dist[j] = min(Dist[j],W(Vi,Vj))
      复杂度：用邻接矩阵O(V^2)；用邻接表+堆优化取dist，O(ElogV)
  • Kruskal：把边按权值排序，从小到大依次验证
      • 复杂度：O(ElogE)，适用于稀疏图

#Hash（散列表）

Python的dict和set都是散列表
hash函数要求：1.简单计算快 2.尽量均匀分布 3.尽量减少冲突 4.可以覆盖整个存储区间。h(key) 的结果越没有规律（相似的key的h(key)不相似）越能满足后3条。key中的信息被h(key)用到越多（比如每个二进制bit都有用），越能满足后3条。
常见Hash函数设计思路：
  1. 数字分析法，抽取整数的若干位
  1. 折叠法，将较长的关键字切成几段，然后合并
  1. 平方取中法，取整数关键字的平方中的若干位。在实际运算中，却二进制形式的若干位速度更快。平方取中法的随机性比较突出。
  1. 取余法，计算速度快，但是有规律，容易冲突
  1. 基数转换法，将整数的十进制表示看作是一个k进制数，然后再转换成十进制。之后取余or折叠
冲突消解：分为内消解和外消解
  1. 内消解，探查序列：，P为不超过表长度的最大质数。若已经被占据，就考虑放在 D=0,1,2..称为线性探查；也可以另外设计一个Hash函数g，称为再散列函数，令，称为双散列探查，比线性探查更能避免元素聚集。
      2. 在这种情况下检索key的元素：槽分为空、闲、满三类。依次检索位置的槽，如果是空则没有该元素；如果是闲or满但匹配不上，都要接着检查，因为“闲”是之前插入的元素又删除了，而当前要找的key可能因为冲突的原因在后面。
  1. 外消解，溢出区。用另外一个列表顺序存放冲突的数据。查询时先看散列值的位置，没找到则到溢出区顺序查找。 冲突多时时间接近线性。
  1. 外消解，桶散列。每个槽都挂一条链表。
装载因子=（满槽+闲槽数）/ 总槽数。装载因子小于0.75时，散列表的性能基本都是O(1)
Python的散列表选择了冲突内消解，而且装载因子大于2/3 就会重新分配空间。

#排序

对内存上的数据进行排序称为内排序，复杂度不可能优于nlogn。对外存上的数据进行排序称为外排序。

插入排序

直接用给定列表进行排序：左边有序，右边无序。每次x=右边无序的第一个元素，把左边的有序元素从右往左依次右移，直到找到合适位置插入x。
时间复杂度平均O(n^2)，最好已经有序O(n)，最坏O(n^2)
额外空间O(1)
稳定。
改进：在找插入位置的时候用二分，但是不改变总的时间复杂度因为仍然需要依次移动元素

希尔排序

在插入排序的基础上改进。取一些D>1，把下标同余的分成一组先进行插入排序。D依次减小，最后直到D=1，化归为插入排序。这样看起来步骤变多了，但是由于之前的很多预排序，最后依次插入排序中需要移动元素的次数总体降低了。
时间复杂度平均O(n^1.5)，最好O(n)，最坏O(n^2)
额外空间O(1)
不稳定。

选择排序

序列左边有序，右边无序。每次找无序部分最小的放在有序部分的后一个。
时间复杂度无论如何都是O(n^2)
额外空间O(1)
不稳定。

冒泡排序

无序部分依次相邻比较
时间复杂度无论好坏都是O(n^2)。改进后（如果扫一遍没有交换就结束）最好时间复杂度可以到O(n)
额外空间O(1)
稳定。

归并排序

合并两个已经有序的子序列，需要另外开一个数组，双指针扫描。
时间复杂度无论好坏都是O(nlogn)
额外空间O(n)+递归栈空间O(logn)
稳定。

快速排序

要完成的事情：选定一个元素key，经过一定重排之后左边小于它右边大于它。
实现方式：左右两个指针扫描，扫到不满足要求的就把key扔过去。可以保证key的位置总在ij之间。
时间复杂度最好&平均O(nlogn)，最坏倒序or基本有序（一个不满足的元素可能会导致很多次交换）O(n^2)
额外空间：对两次递归的普通写法，最坏情况需要递归n层，需要n层栈空间，复杂度O(n)。最好情况和平均情况递归log(n)层，复杂度O(log(n))
不稳定。
时间优化：办法1) 排序前O(n)随机打乱 办法2) 若待排序段为a[s,e]，则选a[s],a[e],a[(s+e)/2]三者中的中位数作为分隔基准元素
空间优化：采用一次递归的尾递归优化写法，只递归排序短的那一半，可以做到最坏情况O(log(n))，最好O(1)

尾递归优化

如果递归调用在return，且return的表达式中不包含其他局部变量，那么当递归下一层时这一层栈里的东西就没有用了，递归栈空间就不用加深。
第一种方式不是尾递归，空间复杂度为O(n)；第二种是尾递归，空间复杂度O(1)，只要在递归栈空间中存当前的product&counter即可。

堆排序

把一个列表原地变成堆，O(n)。采取的方式为：先把列表看成一课完全二叉树，然后从最下一层非叶子节点开始，每层的节点依次“下沉”。
时间复杂度无论好坏均为O(nlogn)
额外空间：如果采用递归写法为O(logn)，但是可以优化到O(1)
不稳定。

桶排序

时间复杂度无论好坏均为O(n+Max)
额外空间：O(n+Max)

基数排序

将待排序元素看作由相同个数的原子构成的元组(e1,e2...ed)。长度不足的元素，用最小原子补齐左边空缺的部分。从ed开始依次按照关键词进行稳定排序
时间复杂度O(d*(n+radix))，radix为各个关键词取值可能值的个数
额外空间O(d*radix+n)
稳定。

总结

notion image
 
相关文章
[置顶]学业任务备忘
数字逻辑基础与Verilog设计
Introduction to Computer System
Systems & Signals
Introduction to Artifitial Intelligence微电子与电路基础