【预览】计算机考研复试、保研算法机试｜笔记和代码模板｜最全总结
在好久之前我就写好了这一份笔记，尽管覆盖了很多知识点，但美中不足的一点是，在我整理笔记的时候，都没有给代码写注释（因为自己写的代码自己都看得懂嘛）。
对于需要快速学习机试重点知识的人，以及在考前要快速复习的人来说，看一遍（没有任何注释的）完整版笔记是一个过于庞大的任务。
那么在这里，我为大家总结了一份精华版考研保研参考算法笔记，添加了更多的说明和注释，方便我自己查阅，也给大家的复习提供了方便。
文章目录
【预览】计算机考研复试、保研算法机试｜笔记和代码模板｜最全总结参考书和刷题题库必考算法快速排序质数判断质数筛质数-朴素版筛质数-线性筛法质因子分解试除法求所有约数最大公约数和最小公倍数栈和队列括号匹配链表删除链表倒数第k个点合并两个有序链表合并k个升序链表双指针算法/滑动窗口二叉树的遍历前序中序后序层序遍历锯齿形层序遍历（拓展）二叉树的重建前+中序列重建树后+中序列重建树平衡二叉树判断二叉树的最小深度二叉树的最大深度二叉树的路径总和最短路问题邻接矩阵建图邻接表建图朴素dijkstra堆优化dijkstraBellman-ford算法Floyd算法SPFA算法拓扑排序BFS法拓扑排序（常用）DFS法拓扑排序：并查集并查集初始化并查集查找并查集合并最小生成树Kruskal算法Prim算法归并排序动态规划DP数字三角形最长上升子序列最长公共子序列背包问题01背包多重背包-每个物品有s[i]个完全背包-每个物品有无限个分组背包-每组若干物品 一组内只能选一个参考书和刷题题库
《算法笔记》，里面的代码都是很好的模版洛谷（按照专题来刷）《剑指Offer》，比较经典的算法和数据结构题目，有标准答案《算法竞赛入门经典》北大百练OJ POJ，适合刷题浙大PAT甲级（想去浙大的话要刷，并且建议提前报名PAT考试，可以抵充机试的分数）Leetcode Medium以上难度的题 按照专题刷Leetcode Top100 Liked QuestionN诺课本和题库必考算法
快速排序质数有关的计算最小公倍数、最大公约数栈和队列（相互转化）leetcode的链表题二叉树的四种遍历二叉树重建（重点）二叉树最小/最大深度4钟最短路算法（Dijkstra、Bellman-ford、Floyd和SPFA）最小生成树（Prim和Kruskal）并查集数字三角形最长上升子序列最长公共子序列背包问题快速排序
快排基于分治，先分再排序
快排是不稳定的，如果想让快排变得稳定需要把每个元素变成独一无二的二元组<ai,i>表示位置
暴力的快排：时间复杂度O(n)
开辟新的数组 a[ ] b[ ]选取q[left-right]中某个数作为x 小于等于x放在a数组 大于x放在b数组a[ ] 和 b[ ]先后放在q[ ]
优美的快排：
最左和最右各一个指针i和j
i往右跑跑跑（往中间） 跑到i指向的数大于x
j往左跑跑跑 跑到j指向的数小于等于x
i和j所指的数交换
重点：
初始化的时候i和j都分别往外走一个 i=left-1,j=right+1在跑完一遍，i与j重合之后分别对两边进行快排。更新的时候是(left,j)和(j+1,right)
🔓解锁完整版笔记后方可查看代码～
质数
判断质数
试除法，一直除到大于等于n/i的时候停
bool is_prime(int n){if(n<2) return false;for(int i=2;i<=n/i;i++)if(n%i==0) return false; // 有因子 不是质数return true; // 没有任何一个数可以整除它}
筛质数-朴素版
用质数i的倍数筛出2-n之间的质数
false表示质数，true表示不是质数
const int N=1000010;bool st[N]; // 记录某个数是否是质量数int primes[N]; // 记录质数int cnt=0; // 记录质数的个数void get_primes(int n){for(int i=2;i<=n;i++) // 从2到n{if(!st[i]) // st[i]是false表示此数是质数{primes[cnt++]=i;// 所有这个数的倍数都不是质数for(int j=i+i;j<=n;j+=i) st[j]=true;}}}
筛质数-线性筛法
比朴素筛法更高效，每次都用一个数的最小质数因子筛掉合数，每个数都只会被筛一遍。
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
质因子分解
#include<iostream>#include<algorithm>#include<unordered_map>using namespace std;int n;int main(){scanf("%d",&n); // 对n个数字进行分解质因数while(n--){unordered_map<int,int> primes; // 记录每个质因子和出现的次数int x;scanf("%d",&x);for(int i=2;i<=x;i++)while(x%i==0){x/=i;primes[i]++;}if(x>1) primes[x]++;for(auto prime:primes)printf("%d %d\n",prime.first,prime.second);}}
试除法求所有约数
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
最大公约数和最小公倍数
最大公约数gcd计算
if(b==0) return a;
else return gcd(b,a%b);
最小公倍数是(a*b)/gcd(a,b);
最小公倍数=两个数的乘积/最大公约数
#include<iostream>#include<stdlib.h>using namespace std;int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}int main(){int a,b;scanf("%d %d",&a,&b);printf("最小公约数是：%d\n",gcd(a,b));printf("最大公倍数是：%d",(a*b)/gcd(a,b));}
栈和队列
括号匹配
输入括号序列，判断是否合法
思路：
对于左括号，直接压入栈中。
对于右括号，弹出栈顶第一个括号，看是否匹配。
1.如果栈是空的，不合法，退出
2.如果匹配，继续操作
3.如果不匹配，表示序列不合法，退出
如果括号序列输入结束，栈中为空，表示序列合法。否则不合法。
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
链表
重点操作
1.对于头结点可能改变的情况：使用虚拟头结点dummy
初始化虚拟头结点：auto dummy=new ListNode(-1); dummy->next=head;
最后返回虚拟头结点：return dummy->next;
2.插入结点node->next=pre->next; pre->next=node;
3.删除结点node->next=node->next->next; //删除了node的下一个节点
删除链表倒数第k个点
leetcode19题
思路：
1.使用虚拟头结点dummy（就不需要区分删除的是否是第一个节点的情况）
2.求链表总长度n，然后找到倒数第k+1个点（删除的时候需要从前一个点来删）
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
合并两个有序链表
leetcode 21
思路：
1.两个链表用两个指针，一起向后跑并不断把更小的加入当前链表
2.直到两个链表指针有一个为空（也可能两个链表都为空）
3.查看两个链表是否为空（至多有一个不为空）然后把不为空的链表接到当前链表的末尾
class Solution {public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {// 虚拟头节点auto dummy=new ListNode(-1);auto tail=dummy; // 新链表的尾指针while(l1 && l2){ // 两个链表都不为空的时候if(l1->val < l2->val){tail=tail->next=l1;l1=l1->next;}else{tail=tail->next=l2;l2=l2->next;}}// 至少有一个链表为空if(l1) tail->next=l1;if(l2) tail->next=l2;return dummy->next; // 虚拟头节点的下一个节点（真实头节点）}};
合并k个升序链表
leetcode 22
class Solution {public:// 结构体内重载运算符struct Cmp{bool operator() (ListNode* a, ListNode* b){return a->val>b->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*,vector<ListNode*>,Cmp> heap;auto dummy=new ListNode(-1),tail=dummy;for(auto l:lists) if(l) heap.push(l);while(heap.size()){auto t=heap.top();heap.pop();tail=tail->next=t;if(t->next) heap.push(t->next);}return dummy->next;}};
双指针算法/滑动窗口
最长不包含重复数字/字母的连续子序列
暴力做法：
算法复杂度为O(n2)O(n^2)O(n2)
枚举j，从后往前枚举i，移动到有重复字母的时候停。
双指针做法：
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
二叉树的遍历
前中后序列本质上的区别就是访问操作的位置。
前序
leetcode 144
// 递归前序遍历class Solution{public:vector<int> ans;vector<int> preorderTraversal(TreeNode* root){dfs(root);return ans;}void dfs(TreeNode* root){if(!root) return;// 访问操作的位置决定了是前、中还是后序ans.push_back(root->val);dfs(root->left);dfs(root->right);}};
// 迭代前序遍历🔓订阅本专栏，解锁完整版笔记后方可查看代码～
中序
leetcode 94
//递归写法class Solution{public:vector<int> ans;vector<int> inorderTraversal(TreeNode* root){dfs(root);return ans;}void dfs(TreeNode* root){if(!root) return;dfs(root->left);ans.push_back(root->val);dfs(root->right);}};
//迭代而不是递归的中序遍历🔓订阅本专栏，解锁完整版笔记后方可查看代码～
后序
leetcode 145
// 递归的后序遍历class Solution {public: vector<int> ans;vector<int> postorderTraversal(TreeNode* root) {traverse(root);return ans;} void traverse(TreeNode* node){if(!node) return;traverse(node->left);traverse(node->right);ans.push_back(node->val);}};
迭代法：
由于后序遍历顺序是左、右、根，其逆序则为根、右、左。因此，可以先以根、右、左的顺序遍历整个二叉树（此时与前序遍历相似）;然后将遍历后的结果进行逆序。
即每到一个节点N，先访问它。接着将N的左子树压入栈，然后遍历右子树。遍历完整棵树后，将结果序列逆序。
解题步骤：
1.先将节点本身的值放入容器;
2.接着将左子节点放入栈中；
3.然后遍历右子树节点，即更新右子树节点为当前节点;
4.当右子树遍历到叶节点后，开始弹出该栈顶元素;
5.若栈中弹出的元素非空，则执行1～4；若为空，则不进行任何处理，继续弹出栈顶元素；
6.直至站内元素和当前元素为空，此时，对容器进行逆序，然后返回逆序后的结果即可。
// 迭代的后序遍历(逆向操作然后reverse一下)🔓订阅本专栏，解锁完整版笔记后方可查看代码～
层序遍历
leetcode 102
利用队列这种数据结构，用BFS来遍历每一层
注意如何区分层号（提前记录当前层的节点个数）
class Solution {public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;queue<TreeNode*> q;if(root) q.push(root);while(!q.empty()){vector<int> level;int len=q.size(); // 当前层的节点个数while(len--){auto t=q.front();q.pop();level.push_back(t->val);if(t->left) q.push(t->left);if(t->right) q.push(t->right);}res.push_back(level); // 把本层的加入答案res里}return res;}};
锯齿形层序遍历（拓展）
leetcode 103
就在原有锯齿形遍历的基础上，加一个判断层的单双号，然后决定是否要reverse
// 锯齿形遍历🔓订阅本专栏，解锁完整版笔记后方可查看代码～
二叉树的重建
必须有的是中序的序列，中序+前序和中序+后序都可以
前+中序列重建树
leetcode 105
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
后+中序列重建树
leetcode 106
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
平衡二叉树判断
leetcode 110
在dfs的过程中，对每一个访问的节点计算左右子树的高度，并且判断是否平衡。如果有一个节点不平衡，那么子树就不平衡。
dfs函数返回的是某节点的高度！
class Solution {public:bool res;bool isBalanced(TreeNode* root) {res=true;dfs(root);return res;}int dfs(TreeNode* root){if(!root) return 0;int lh=dfs(root->left); // 左子树高度int rh=dfs(root->right); // 右子树高度if(abs(lh-rh)>1)res=false; // 在计算树的高度的任何一个步骤中如果有return max(lh,rh)+1;}};
二叉树的最小深度
leetcode 111
最小深度：根节点到叶子节点的最短距离
计算最小深度：
u是叶节点：深度为1
u不是叶子节点，ab是左右子树
a,b都不空min(f(a),f(b))+1
a不空,b空f(a)+1
a空,b不空f(b)+1
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
二叉树的最大深度
简单的dfs，每访问一个节点都计算该节点左右子树的高度，然后返回该节点的高度
计算：1+max(左子树高度，右子树高度)
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
二叉树的路径总和
leetcode 112
f(u) 表示从根走到u节点的总和/sum-总和
对于u的左右子树a和b
f(a)=f(u)+a->val
f(b)=f(u)+b->val
如果一个节点是叶子节点且f(u)==sum或者f(u)==0
🔓解锁完整版笔记后方可查看代码～
最短路问题
初始化的操作需要用到头文件cstring
void *memset(void *s, int ch, size_t n);
函数解释：将s当前位置后面的n个字节用 ch 替换并返回 s 。
举例：把数组g全部设置为正无穷
memset(g,0x3f,sizeof g);
邻接矩阵建图
#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N=510;int n,m;int g[N][N]; // 邻接矩阵来存放各条边的长度int dis[N]; // 后面用最短路算法时候的disint main(){cin>>n>>m;memset(g,0x3f,sizeof g); // 初始化为正无穷while(m--){int a,b,c;cin>>a>>b>>c;g[a][b]=min(g[a][b],c); // 处理重边的情况 取权值较小的边}return 0;}
邻接表建图
#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N=510;int n,m;int w[N],e[N],ne[N],h[N];// w是权值 e是这条边的第二个点 ne是指向下一条边的指针 h是各节点的表头指针int idx=0;void add(int a, int b, int c){w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;}int main(){scanf("%d %d",&n,&m); // n表示点的个数，m表示边的个数for(int i=0;i<m;i++){int a,b,c;scanf("%d %d %d",&a,&b,&c);add(a,b,c);}// 图就建好了return 0;}
朴素dijkstra
朴素dijkstra的复杂度是O(n2)O(n^2)O(n2)，使用邻接矩阵存放边的信息。
dijkstra算法适用于单源最短路问题。
注意：
首先把dis数组设置为正无穷（表示不可到达），再将起点设置为距离0
#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N=1010;int n,m;int g[N][N];int dis[N];bool st[N];int dijkstra(){🔓解锁完整版笔记后方可查看代码～}int main(){cin>>n>>m;memset(g,0x3f,sizeof g);while(m--){int a,b,c;cin>>a>>b>>c;g[a][b]=min(g[a][b],c);}cout<<dijkstra()<<endl;return 0;}
堆优化dijkstra
堆优化dijkstra的复杂度是O(mlog2n)O(mlog_2n)O(mlog2n)。使用priority_queue来表示堆。
使用邻接表存放边的信息，适用于单源最短路。
#include<iostream>#include<cstring>#include<stdlib.h>#include<queue>using namespace std;const int N=100010;typedef pair<int,int> PII;int n,m;int h[N],e[N],ne[N],w[N],dis[N],idx=0;void add(int a, int b, int c){w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;}int dijkstra(){🔓订阅本专栏，解锁完整版笔记后方可查看代码～}int main(){scanf("%d %d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b,c;scanf("%d %d %d",&a,&b,&c);add(a,b,c);}cout<<dijkstra()<<endl;return 0;}
Bellman-ford算法
for循环n次，每次遍历所有边。
假设遍历的那条边是a->b，每次把dis[b]更新一次，dis[b]=min(dis[b],dis[a]+w(a,b))看是现在有的路径更短还是经过b到a到路径更短
#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N=510,M=10010;int n,m,k;int dis[N],backup[N];struct Edge{int a,b,w;}edges[M];int bellman_ford(){🔓订阅本专栏，解锁完整版笔记后方可查看代码～}int main(){cin>>n>>m>>k;for(int i=0;i<m;i++){int a,b,w;scanf("%d%d%d",&a,&b,&w);edges[i]={a,b,w};}int t=bellman_ford();if(t==-1) printf("impossible\n");else printf("%d\n",t);}
Floyd算法
Floyd算法是算法复杂度最高的，O(n3)O(n^3)O(n3)
Floyd算法可以解决多源汇的最短路问题。
SPFA算法
SPFA算法的一般时间复杂度是O(m),最坏时间复杂度是O(nm).
在算法竞赛中写最短路的题目一般用SPFA！SPFA过不了再用堆优化dijkstra算法。
SPFA算法核心：只修改最短距离有变化的点的出边
// SPFA算法🔓订阅本专栏，解锁完整版笔记后方可查看代码～
拓扑排序
只有有向无环图才有拓扑序列。
拓扑排序不是唯一的！
BFS法拓扑排序（常用）
拓扑排序（bfs法）的算法思路：
第一步：所有入度为0的点进入队列
第二步：
while(队列不为空)
取出队头的点;
枚举从队头的点出去的所有边，删掉那些边;
如果某个被删掉的边的b点的入度变为了0，将这个点加入队列;
拓扑排序-BFS（数组版）
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
拓扑排序-BFS（队列queue版）
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
DFS法拓扑排序：
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
并查集
并查集初始化
const int N=100010;int p[N];for(int i=0;i<n;i++) p[i]=i;
并查集查找
int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];}
并查集合并
注意：有的时候需要判断两个点在不在同一个集合，有点时候不要判断（如果维护了一个在根节点的元素，就需要判断.
把两个点（两组点）合并为同一个集合：
if(find(a)!=find(b)){p[a]=p[b];}
最小生成树
Kruskal算法
Kruskal算法适合用于稀疏图。重点在于如何给struct结构的边按照权值weight排序。
Kruskal算法思想：
每次取最短的边 判断是否形成环或者说这条边的两个点是否已经相连（通过并查集判断）
第一步：所有边按照权重从小到大排序
第二步：从小到大 枚举每条边ab 权重c
如果ab不连通（加ab不产生回路） 将这条边加入集合
在kruskal算法中，不需要存储邻接表或邻接矩阵，只需要把每条边用struct结构体存下来。
#include<iostream>#include<algorithm>using namespace std;const int N=200010;int n,m;int p[N]; // 并查集的辅助数组struct Edge{int a,b,w;// 重载运算符 在sort的时候就会按照这里的规则排序bool operator<(const Edge &W) const{return w<W.w;}}edges[N];int find(int x){if(x!=p[x])p[x]=find(p[x]);return p[x];}int main(){scanf("%d %d",&n,&m);for(int i=0;i<m;i++){int a,b,w;scanf("%d %d %d",&a,&b,&w);edges[i]={a,b,w};}sort(edges,edges+m);for(int i=1;i<=n;i++) p[i]=i; // 初始化并查集int res=0,cnt=0;for(int i=0;i<m;i++){int a=edges[i].a,b=edges[i].b,w=edges[i].w;a=find(a),b=find(b);if(a!=b){p[a]=b;res+=w;cnt++;}}if(cnt<n-1) printf("impossible\n");else printf("%d\n",res);}
Prim算法
prim算法适用于稠密图，用的比较少 不需要掌握
归并排序
归并排序和快速排序都是用的是分而治之的思想，先递归排序再归并合二为一
归并排序算法思想：
第一步：找分界点mid
第二步：递归排序
第三步：归并 把两个有序序列变为一个有序序列 这一步复杂度为O(n) 每个元素都只会被比较一次
🔓解锁完整版笔记后方可查看代码～
动态规划DP
数字三角形
求一个数字三角形的路径最大/最小值
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
最长上升子序列
求最长的单调递增子序列（的长度）
#include<iostream>#include<algorithm>using namespace std;const int N=1010;int n;int a[N],f[N];int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++){f[i]=1; // 初始化 最大长度为1// 遍历前面的每个字符for(int j=1;j<i;j++)// 如果前面的某个字符小于这个字符if(a[j]<a[i])f[i]=max(f[i],f[j]+1);}int res=0;for(int i=1;i<=n;i++) res=max(res,f[i]);return 0;}
求最长的单调递增子序列（的序列和长度）
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
最长公共子序列
重点在于把最后一个字符分情况讨论。
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
背包问题
01背包
当空间优化为1维后，只有完全背包问题的体积是从小到大循环的
#include<iostream>#include<algorithm>using namespace std;const int N=1010;int n,m;int v[N],w[N];int f[N];int main(){cin >> n >> m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--) //用的是上一层的状态f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[m]<<endl;return 0;}
多重背包-每个物品有s[i]个
朴素版多重背包(类似完全背包,只是k=0,1,2…s[i],多了一个判断)
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
完全背包-每个物品有无限个
🔓订阅本专栏，解锁完整版笔记后方可查看代码～
分组背包-每组若干物品 一组内只能选一个
思路类似多重背包
#include<iostream>#include<algorithm>using namespace std;const int N=110;int n,m;int v[N][N],w[N][N],s[N];int f[N];int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=0;j<s[i];j++)cin>>v[i][j]>>w[i][j];}for(int i=1;i<=n;i++)for(int j=m;j>=0;j--)for(int k=0;k<s[i];k++)//用的是本层状态 所以体积从小到大if(v[i][k]<=j)f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);cout<<f[m]<<endl;return 0;}
