算法基础课每一题的大致想法，持续更新

2021.6.1，开坑，大家六一快乐啊

快排就是找一个数(注意，在进入while排序循环之前找这个数一定要定死数字，而不是位置，因为这个数的位置是不断变化的)，每次把它放到正确位置，当然不断递归去找的时候注意如果l == r可以返回了要不MLE，O(nlgn)

快速查找第k个数，也是快排思想，但是不用每次都排序了，也是挑一个数放到对的位置，看这个时候，第k个数应该落在接下来排序的两个区间中的哪个，只递归排序这个空间就行，O(n)

归并排序两个排好序的区间进行合并，用到一个额外数组保存后再复制回去，O(nlgn)

逆序对个数也是归并排序思想，每次排序时候出现前一个区间大于后一个区间某个数，那么前一个区间的剩余所有数也都大于后一区间的这个数了，O(nlgn)

二分首先要查找的序列要有一个单调性，当然不只是数字的大小序，这里简化说明假设就是数字的大小序，对于查找k这个值有两种查询方式，一种是找小于k的最大值另一种是找大于k的最小值，其实本质是不断缩小区间，最终返回一个位置（返回l或者r都行，因为最终两者相等），往左走就是找小于k的最大值，往右走就是找大于k的最小值

小数二分和整数二分不一样，不必考虑边界问题，但需要注意没有严格相等，二者相差小于一个偏差值就够了

2021.6.2，今天刚去了医院开了些药，最近好像坐多了，腰疼，接着写吧

高精度加法没啥可说的两个字符数组读进来数字后用vector存，注意是倒着存，因为我们可能会向上进位，而对于vector来说处理尾部比头部更轻松，我们假设前一个vector更长一些，然后不断取出前一个vector的第i位和后一个vector的第i位（如果有）两者加到新的vector上，然后返回这个vector就可以了

高精度减法需要注意的是计算的时候可能要向前一位借位，这里A[i] - B[i]也许会小于0，那么插入C的我们可以这么写(t + 10) % 10，这样就不用去特判了，算是一个简化吧，然后注意计算完可能出现前导0，需要去除

高精度乘法是每次拿A[i] * B，把这个数的个位放进C里，剩下的数字/10加上接下来的A[i + 1] * B接着算，注意同样的有可能一个数字乘0，最终全是0需要去除前导零

高精度除法，可以想一下我们正常怎么算除法，就是A从头捋，一点一点把/B的结果放进去，注意可能还有余数，即%B的结果*10再加上A的下一位接着这样算就可以

一维前缀和，每次输入一个数，将它与前面的所有数字加起来，也就是s[i] = a[1] + a[2] … + a[i]，然后我们想求a[l]到a[r]的和其实就是s[r] = s[l - 1]

二维前缀和与一维前缀和类似，也是把每一个格子单个数字变为前一片格子的和

一维差分，所谓差分就是新开一段数组b使得a[i] = b[1] + b[2] + … + b[i]，那么b[i] = a[i] - a[i-1]

二维差分，与一维差分也差不多，开一个新的数组b使得a[i][j]等于从b[1][1]往右下到b[i][j]的全部值之和

最长连续不重复子序列，就是用一个哈希表和双指针算法，i不断向前走，遇到一个数字把他加到哈希表中，每次加的时候用判断j所在位置是否处于当前子序列区间中，然后如果有的话就把j对应地方的值从哈希表里弹出来，然后j++，这个双指针算法看着像两重循环实际上复杂度是O(n)

2021.6.3，摸鱼，上课写

数组元素的目标和，双指针算法有时候其实就是暴力算法的一个优化，看看其实不必一个一个试，因为两个序列是升序的，也就是其实两个序列分别从小到大和从大到小去找就可以，复杂度是O(n)

判断子序列，两个指针指向两个序列不断移动判断是否是子序列，复杂度是O(n)

二进制中1的个数，就是位运算，不断右移&1，O(n)

区间和这个题有点意思，核心是离散化因为数据范围太大了，而参与操作的数据占比很小。想法就是把add和query操作用到的数都存进一个vector中，然后对这些数去重，要记得怎么做！！！！！然后求每一个query的l和r区间的区间和，这里用到了前缀和，重点在于这个离散化难想到，记得吖！还有一个点容易忽略，就是N开到3倍，因为有x，l，r三种可能的数字，算上排序的话复杂度是O(nlgn)的，其余计算应该是O(n)的

区间合并的话，就是一个vector[HTML_REMOVED]去存各个区间，然后按左端点排序，若下一个区间左端点大于前一个右端点那就res++，然后右端点看情况更新就OK，算上排序的话复杂度是O(nlgn)的，其余计算应该是O(n)的

手打单链表，经过后面题的历练其实手打单链表熟练了很多了，但还是在insert环节出了小问题，但很快debug出来了，没什么说的，别忘了head一开始为-1，然后idx不断变化

手打双链表有点忘了。。令0为左端点1为右端点，idx从2开始了，其他没啥要注意的了

手写栈其实也还好，就是一个一维数组，然后有个单独元素记录顶点位置

表达式求值手也有点生了，但大致记得思路，有一点还是踩坑了，就是当处理到一个运算符号时候只要能算就一直算，还有全部字符处理完可能还是有剩余的运算符号和数字，记得处理

模拟队列其实还算简单，就是一个数组，然后额外用hh = 0，tt = -1记录队列头和尾

单调栈，所谓单调栈其实就是指栈内元素是单调的，在求每个数左侧或者右侧比它小的第一个数的位置用，为啥要单调呢，因为比它大的更用不到了，O(n)的复杂度

2021.6.4，药吃了不少，腰还是好痛啊，接着写吧，嘶，其实感觉到瓶颈期了，动力不足了，干就完了！

单调队列应用：滑动窗口，其实对比一下单调栈，我没发现二者很类似，只不过单调栈只有尾部不断变化，而单调队列在合适的情况下队头也要出队，用q来记录队列中数字对应的下标，复杂度O(n)

KMP，老实说之前做的时候就有点一知半解，这次终于感觉看懂了，就是对子串求next数组，next[i] = k代表前i个字符中1～k和i - k + 1~i是相等的，不匹配的话不用重头比较可以不断回退，而且求next数组与实际比较代码差不多，可以看 这里 ，复杂度O(m + n)

Trie树，就是一个son[N][?]的数组存储一个树，N咋取看总长度最长能达到多长，插入时候记得还要一个cnt数组标记有字符串到这个地方停止，这样查询一个字符串是否出现过需要O(n)

最大异或对和Trie类似，就是对每一个数去找异或最大的，然后再把这些值取max，用位运算，复杂度O(n)，虽然这个复杂度常数有点大但可以接受

2021.6.5，我又双叒叕回来了，希望一切顺利，加油

合并集合，对于每个数字x初始有一个p[x] = x，然后不断合并若对于两个数字a, b的pa, pb相同，则两者可以认为顶层父节点相同，也就是二者处在同一个集合，而且在find顶层父节点时候有路径压缩操作，这个复杂度相当的低

连通块中点的数量就是并查集，只不过对于每个顶层父节点记录一下这个集合节点数量

食物链的题，find函数中更新距离时候，要记录父节点，而不是父节点距离，因为父节点距离也在不断变化

堆排序，手写堆其实还好，从1开始是堆顶，然后对于任意一个节点i，它的左节点是i * 2，右节点是i * 2 + 1，然后排序过程中不需要全部down一边，只需要从size / 2 ～ 1的范围down一遍就好

还是手写堆，但是只不过需要的操作多了点，要记录第k个插入堆的下标（hp、ph），还要自己写swap交换值和hp、ph，还有要up和down

手写哈希表，这个其实我只会开放寻址法，就是先找一个数，满足是将要输入的数字个数的两倍以上的第一个质数N，开这么大的数组，然后正常来说存一个数x的位置应该是(x % N + N) % N，然后如果这个地方不空且不是x，那就往后找直到找到一个空的位置，存为x，当然这个空定义成数据范围外的一个数字，然后记得一开始初始化hash表为空，找这个值的话也是像插入一样循环找，直到找到这个数字应该存的位置，如果这个位置上的数字就是你要找的数字，那就对了，否则就是没有这个数字

字符串哈希，字符串哈希的核心思想是把字符串当成数字一样对待，像我们正常写数字，左侧是高位右侧是地位，开数据范围和普通哈希一样，然后进制是131进制，可以解决很多问题

2021.6.7，昨天懒了哈哈哈，今天高考，各位加油哇

排列数字是个很经典的问题了，但说实话有些时间没做还是有点不熟练了。就是用一个st数组表示1～n的某个数字用没用过，res数组存储结果，记得dfs时候，出来要把你st赋回false，而且n ≤ 30，大概猜出来是用dfs

n皇后也很经典，和排列数字类似，其实dfs就是应该是有几个数组来表示状态是否能用，然后用一个数组存答案，循环所有状态 去看就好

走迷宫23333，bfs就是队列存储状态，和dfs的栈存储状态不一样，栈的话你递归调用就会隐式的用了栈，这个bfs你要显式的定义队列来存储状态，然后有个d来存储从开始到现在这个状态的距离，当然一开始d要全部初始化为-1来定义没走过，因为我们要找最短路径

八数码也很经典，昨晚你就会感受到其实bfs的核心就在于如何表示一个状态队列，和这个状态是否出现过，以及这个状态距离初始状态的距离

树的重心，debug半天 。。没想到是读入时候少读入一个数字 23333，这题需要注意的是dfs，一定要注意状态是否到来过！！！！否则会无限递归爆栈，这个dfs问题每次返回以k为节点的子树大小

图中点的层次，这个题其实还好，一个bfs就搞定，就是要看清是有向边啊！！！

有向图拓扑序列，也是bfs，但是要有一个数组记录每个点的入度数，而且在开始搜索时候记得要遍历所有的点找入度为0的点，因为它并不是确定的，最终答案就是bfs过程的这个队列，所以手写队列比较好

朴素的Dijkstra就是不断找距离一个集合最近一个点作为新的点去更新它到其他节点的距离，那么这个集合是什么呢，就是确定了在最短路过程中出现的点，确定后就不再变了。需要维护两个数组dist和st分别代表起点到该点的距离以及该点是否已经加入到确定最短路的集合范围内了，复杂度O(n^2)。

堆优化的Dijkstra优化在于找那个离已确定最短路的集合范围最近的点，用有限队列来维护这个小根堆，注意小根堆用的pair要把距离放在第一位，因为默认按第一个排序，然后每次取出最小距离的点，看这个点st是不是true是的话就continue，复杂度O(mlgn)

2021.6.8，继续继续，冲刺冲刺！

虽然说bellmanford在spfa面前几乎是没有优势，但是他有一点是spfa无法比拟的，那就是在有边数限制的情况下来求最短路，一共k次更新，每次更新memcpy把d数组拷贝给backup数组，再m次循环，把每个边对应的d[b]更新为新的，当然这个更新要用backup更新，因为每次更新途中会改变某个d，然后造成影响，就不满足k条边数这个限制了，最后返回时候如果d[n] > INF / 2就是错，因为它是不管你怎样都更新距离，可能会把INF值往回收一收，O(nm)

spfa是队列优化的，有个st表示是否在队列中（因为有可能重复入队），每次从队头出来一个点，有必要的话就更新邻边的点到起点距离，然后看邻边的点在不在队列里，不在就放进去，O(m) ~ O(nm)

spfa判负环，比spfa多了一个cnt代表从起点到现在经过了多少条边等于n的时候代表走过n条边，也就是n + 1个点，必有负环，所以就是了，当然注意，这里起点不是唯一，一开始要把所有点放入队列，因为从某一个起点为必到的了负环

floyd是多源汇，可以处理任意由x到y的最短距离的解，直接上三重循环kij，然后g[i][j] = min(g[i][j], g[i][k] + g[k][j]);就可以求出来答案了

朴素版prim算法，这个算法和朴素版Dijkstra非常像，但二者维护的d数组含义不同，prim维护的d数组代表该点到已加入最小生成树的节点集合的距离，所以更新d[j] = min(d[j], g[t][j]);而且每当取出一个新t时候看是否是INF是的话就没有最小生成树，否则加到结果上一块返回

kruskal算法则需要构建结构体（存储边的两端点和权重）和并查集，先把边按权重从小到大排序，然后依次拿出来看两个点是否是一个集合（比较根节点），不是的话把俩集合（并查集）合并，把权重加在结果上，cnt++，最终如果cnt小于n代表没有最小生成树

染色法判断二分图。什么是二分图？就是所有边对应的两个顶点分属于两个集合，充要条件是没有奇数环（环内有奇数个节点），使用染色法对其进行判断。循环所有点若该点尚未被染色则会作为起点将其dfs染色为1，dfs过程中判其邻边对应节点若没染色就对其dfs染色为2，若染色看是不是相同颜色，然后若这俩有一个不能就不是二分图，若全部dfs结束成功了那就是二分图

2021.6.9，I’m back

二分图最大匹配，这个题建立一个有向邻接图，然后从idx为1～n1的点当作左边的点循环去找它邻接的点，如果这个点本轮还没被匹配过就先占上，然后来看如果确实这个点match为空或者它match的点还能再find到一个可以匹配的那就把这个点当作自己的匹配返回true，res++，O(nm)

试除法判定质数，就是for(int i=2;i<=x/i;i++)看x % i是不是0，是的话就不是质数，当然一开始x < 2那也不是质数

分解质因数就是for(int i=2;i<=x/i;i++)枚举若能%开，就是一直除这个数，除到%不开，然后输出一下，最后看一下是不是x > 1，是的话再输出x和1，因为每个数字最多可能有一个大于根号它的质因数

筛质数，就直接用最好的线性筛法，这个算法接近线性的时间复杂度， 看这个解析 就可以了

约数个数的做法有一个公式，对该数分解质因数，并对每一个质因数记录下它的指数值，最终把这些指数值加一连乘就是结果

约数之和也是有公式，和上一题一样记下来质因数和指数值，然后答案就是一个连乘式

最大公约数，使用辗转相除法模版return b ? gcd(b, a % b) : a;

欧拉函数，从1～N中所有与N互质的数的个数有个公式N * (p1 - 1) / p1........p是N的一个质因数

2021.6.10，想休息想放假，早日上岸！！

筛法求欧拉函数，上一个求欧拉函数其实是求单个数的欧拉函数，这个是求1～N的欧拉函数，是用筛法，在筛的过程之中，质数的欧拉函数就是i - 1，剩下的 i % prime[j]就判断是不是0，两种情况略有不同， 可以看这个

快速幂，qmi哈哈哈，a ^ b % p，这个的核心思想是把b拆为二进制，然后从低位开始不断>>1看是不是1，是1就res * a % p，a是不断的翻倍的，因为是不断要用到的

怂了，先动态规划（其实我们能看出来，所谓动态规划就是用f来表示状态，想怎么从前一个状态转移过来）

01背包，所谓01背包就是物品只有一个，这是个网格填写过程，一步一步来就好

完全背包，啥叫完全背包呢？就是每个物品都有无限个，你可以随便装任意个，根据f[i][j]和f[i][j-v[i]]之间的关系可以优化

多重背包就是每个物品有确定个数，不能无限使用，做法就是假设第i个物品有si个，将si拆为1 + 2 + 4 + 8 + 。。。这种，用这些拆出来的个数构建新的物品，这样可以变为01背包问题解决了

分组背包与01背包类似，只不过对于i不再是一个物品而是一组物品，那么在j变大过程中，还要在嵌入一层k的循环来循环本组物品

2021.6.11，继续数学

快速幂求逆元，首先说什么是逆元，若a*b≡1(mod p) ,a,p互质,则称b为a的逆元，那么有费马小定理：如果p是一个质数，a又不是p的倍数，那么有a ^ (p - 1) ≡ 1 (mod p)，那么很显然就是a * a ^ (p - 2) ≡ 1 (mod p)，b就是a ^ (p - 2)，用快速幂求a ^ (p - 2) % p就ok

2021.6.12，昨天被迫拉去开了好久的会，所以就做了一道题23333

扩展欧几里得算法，这道题就是用欧几里得的思想，在算gcd过程中不断求解x和y的值 这里我题解写的很详细

线性同余与扩展欧几里得一样，a * x = b(mod m)，不就相当于a * x + m * y = b(mod m)，最后如果b是gcd倍数输出答案就可以，否则impossible

2021.6.13，快考试了，咋这么多事情啊（数学也太🐔儿难了，再做会dp，虽然dp也很难23333）

数学三角形，就是f[i][j]存储从开始加到现在最大的值，然后在最后一行里找出最大的就OK

最长上升子序列，用f[i]来存从1到i以a[i]结尾的最长上升子序列

对最长上升子序列的优化，用q[i]来存储长度为i的最长上升子序列的结尾值，每次对于新的a[i]，去查小于它的最大值，去复习二分！！！！！！！！（往左走就是找小于k的最大值，往右走就是找大于k的最小值），然后更新q的长度len和q[r + 1]

最长公共子序列，用f[i][j]来表示第一个数组前i个和第二个数组前j个的最长上升子序列，他从前一个状态转移过来有四种状况，分别讨论一下就OK

2021.6.14，1000 - 7 = ？，我的心情就是这个

最短编辑距离，f[i][j]表示将a[1~i]变为b[1~j]的操作次数，那么很显然从a到b可能操作是增删改，增就是代表f[i-1][j] + 1，为什么呢，因为确定a[1~i-1]和b[1~j]相等了，同理减是f[i][j-1] + 1，改是f[i-1][j-1] + 1，相等的话就f[i-1][j-1]

编辑距离和最短编辑距离一样

石子合并，是区间dp，先前都是线性dp也就是1～i，这个是i～j，而且是有个模版的，len = 2开始，i从1开始递增，每次算以i开头len长度的区间，i表示左端点，j表示右端点，然后k从i到j算一遍

整数划分有点像背包问题，每个数字有无数个，f[i][j]表示从前i个数字里挑能凑成j的方法数（可以不挑，也就是j为0时候为1），f[i][j] = f[i-1][j] + f[i][j-i]（和完全背包推导一样）

2021.6.15，难顶，考试周压力有点大

蒙德里安的梦想，你有个p的梦想，这题是状态压缩，也就是用二进制01代表每个位置状态，f[i][j]表示前i-1列摆好情况下，第i列状态为j的数目，然后循环每种状态确定这些从00…00～11…11这些状态有无连续奇数空白块（用来摆的是1x2），然后看两行并一起的有没有冲突或者状态不行的，如果都可那就放入状态表示vector中，然后最后dp

最短hamilton路径，Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。我们想到用f[i][j]，i二进制01来存储是否到达过某点，然后j表示当前在哪个点，f值代表目前走过距离

2021.6.16，一到考试周就上火鼻塞扁桃体发炎的人就是我了

没有上司的舞会，树状dp，有点像dfs，f[N][2]代表一个节点被没被选中情况下该节点带其所有子节点的快乐最大值

滑雪，像bfs，就每次拿出一个点往边上四个方向滑，最终取最大值

2021.6.17，有点没力了23333

区间选点，按右端点排序，然后一个一个看，挑右端点当作放的点

最大不相交区间和上一题一样

2021.6.18，sorry啊，最近考试周压力有点大，可能每天做的不多

区间分组，就是把所有区间按左端点排序，完了拿一个新的来和当前最打头的那个区间的右端点比。最终heap的size就是答案