- 博客(175)
- 收藏
- 关注
原创 【算法基础课模板笔记+注释】 数据结构13 --- 散列表
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:用数组模拟散列表平均时间复杂度约为O(1)包括四个部分:散列队头(邻接表头)h[N], 数组元素e[N], 下一跳ne[N], 下一次可用指针idx求模一定要这样int k = (x % N + N) % N;注意h初始化为-1可以先写一个程序求一下最大素数模板记忆这个模板分为四个部分:插入:求得散列值,使用头插法插入(静态链表)查询:求得散列值,遍历对应链表模板代码v
2022-02-20 17:43:53 266 1
原创 【算法基础课模板笔记+注释】 数据结构12 --- 堆排序
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:堆排序取出最小的数平均时间复杂度为O(logn)模板记忆这个模板分为四个部分:up:上升,用于尾插入和中间插down:下降,用于删除头后补插模板代码void up(int x){ if (x == 1) return; if (q[x / 2] > q[x]) swap(q[x / 2], q[x]), up(x / 2); return;}
2022-02-20 16:05:05 345
原创 【算法基础课模板笔记+注释】 数据结构11 --- 并查集
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:并查集这里并查集用下标代表元素模板记忆这个模板分为四个部分:初始化:并查集用一个数组即可,表示父节点,根节点指向自己并:把两个集合合并成一个,使用递归模板代码int p[N];int find(int x){ if (p[x] != x) p[x] = find(p[x]); // 非根递归指向根 return p[x]; // 返回已经改过的根}v
2022-02-20 10:54:39 264
原创 【算法基础课模板笔记+注释】 数据结构10 --- 最大异或对
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求一些数字最大异或对平均时间复杂度为O(n),暴力为O(n^2)模板记忆这个模板和trie一样,不用单独记忆模板代码int son[N][2] = {}, idx; // 用trie树存储二进制数字int insert(int x){ int p = 0, q = 0, res = 0; // p用于插入,q用于查找最大异或对,res记录最大异或对 for (in
2022-02-19 18:30:59 128
原创 【算法基础课模板笔记+注释】 数据结构09 --- trie树
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:保存字符串的hash平均时间复杂度为O(size)树的构成有26叉指针son[N][26],下一个可用结点idx,标记cnt[N]这棵树的结点没有信息,信息直接保存在了路径上,这是为了随机访问模板记忆这个模板分为三个部分:初始化:三个部分son[N][26],cnt[N],idx插入:用p表示遍历到的结点:1字符定数字 2查改son 3改p 4改cnt查询:1字符定数字 2查s
2022-02-19 17:24:45 113
原创 【算法基础课模板笔记+注释】 数据结构08 --- KMP
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:字符串匹配平均时间复杂度为O(n)注意字符串从1开始模板记忆这个模板分为两个部分:next:更新next数组,每次循环:迭代移动j,匹配成功j ++ , ne[i] = j;匹配:字符串匹配,每次循环:迭代移动j,匹配成功j++,到达结尾j = ne[j]注意的点:next和匹配部分的区别next的i从2开始,匹配的i从1开始next的i指示p的下标,匹配指示s下标n
2022-02-19 15:22:38 375
原创 【算法基础课模板笔记+注释】 数据结构07 --- 单调队列(滑动窗口)
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求一个滑动窗口中满足某条件的值使用一个数组a存储原数组,一个数组q存储窗口队列中有用的下标保证:窗口中新进入一个元素就可以排除掉没有用的元素保证:队列中下标的范围在窗口内模板记忆这个模板分为三个部分:保窗口:移动队头,保证窗口大小删元素:移动队尾删除被新元素筛掉的元素插元素:插入新元素模板代码int a[N], q[N]; // a是原数组,q是队列(存储下标)int
2022-02-18 23:51:06 96
原创 【算法基础课模板笔记+注释】 数据结构06 --- 单调栈
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:依次查找某个数组每一位前第一个满足某条件的数遍历到的数既是目标对象,也是被查集合的元素比如查找比那个数小的第一个数,则当压入栈的数比栈顶小的时候,栈顶就没有了作用。模板记忆这个模板分为两个部分:查:遍历到某个数的时候,通过依次弹出来查找满足条件的数压:新数字压入栈中模板代码while (n -- ){ int x; cin >> x; w
2022-02-18 21:03:08 60
原创 【算法基础课模板笔记+注释】 数据结构05 --- 模拟队列
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:用数组模拟一个队列主要包括:队列数组q[N],头head尾,rear指针模板记忆这个模板分为五个部分:初始化:head = 0(下一个输出), rear = 0(下一个输入)压入:压入尾部弹出:弹出头部判空:判队列空查队头:查队头元素模板代码void init(){ head = 0, rear = 0;}void push(int x){ q[rear
2022-02-18 20:47:49 73
原创 【算法基础课模板笔记+注释】 数据结构04 --- 表达式求值
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求中序表达式的值模板记忆这个模板分为四个部分:运算:从num弹出两个数,从op弹出一个操作符,运算结束再压入num优先级:初始化一个优先级hash表判:依次判断:数字压入、左括号压入、右括号运算到左括号弹出、运算符运算到优先级小于当前压入清空op:把栈中剩余运算符弹出并运算模板代码#include <iostream>#include <stack>
2022-02-18 18:45:11 198
原创 【算法基础课模板笔记+注释】 数据结构03 --- 模拟栈
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:用数组模拟一个栈主要包括:栈数组st[N],下一个可用指针top模板记忆这个模板分为四个部分:压入:压入一个元素弹出:弹出一个元素判空:判断站是否为空栈顶:查找栈顶元素模板代码int st[N], top;void push(int x){ st[top ++ ] = x;}void pop(){ top -- ;}bool empty(){
2022-02-18 16:52:15 145
原创 【算法基础课模板笔记+注释】 数据结构02 --- 双链表
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:用数组实现双链表主要包括:结点内容e[N],结点右指针r[N],结点左指针l[N],下一个可用结点idx双链表一般都要使用头尾结点!模板记忆这个模板分为四个部分:初始化:头尾两个指针+idx插入:插入三部曲:内容、指针、被指针++删除:两侧指针互相指遍历:从头到尾遍历整个链表模板代码int e[N], l[N], r[N], idx; // 使用头尾结点,不需要head
2022-02-18 15:41:02 142
原创 【算法基础课模板笔记+注释】 数据结构01 --- 单链表
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:用数组实现链表主要包括:结点内容e[N],结点下一个指针ne[N],第一个结点指针head,下一个可用结点指针idx四个部分也可以用带头结点的,ne[0]视为头结点,idx从1开始模板记忆这个模板分为四个部分:初始化:头和idx的初始化头插:插入三部曲:内容、指针、被指针++中间插:插入三部曲:内容、指针、被指针++删除:跳过即可遍历:从头到尾遍历链表模板代码int h
2022-02-18 14:37:42 216
原创 【算法基础课模板笔记+注释】 基础算法13 --- 区间合并
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求多个区间合并的问题平均时间复杂度为O(n)简单贪心(或者双指针)模板记忆这个模板分为两个部分:排序:把区间按照左边缘递增排序使用双指针依次合并:遍历到新区间查看是否可以合并模板代码void merge(vector<PII> &segs) // 把segs数组中存的区间合并{ vector<PII> res; // 结果数组
2022-02-18 11:52:34 135
原创 【算法基础课模板笔记+注释】 基础算法12 --- 离散化
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:把下标范围很大但是多数无效的数组,映射到一个较短的数组和一般的哈希表不同,这里下标必须保持有序(对应map)查找时间复杂度为O(logn),(使用二分)思路:把有用的下标存到一个数组中,内容存到另一个数组中,这两个数组一一对应,使用二分查找原下标对应的新下标模板记忆开设数组:alls:记录原下标a[N]:记录对应下标的内容s[N]:附加的使用前缀和求范围数大小add,quer
2022-02-18 11:07:18 73
原创 【算法基础课模板笔记+注释】 基础算法11 --- 位运算
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:n的第k位二进制(n >> k & 1)解决问题:lowbit求x的最后一位1(x & -x)模板代码n的第k位n >> k & 1lowbitx & -xlowbit — 二进制中1的个数for (int i = 0; i < n; i ++ ){ int x = 0; while (a[i])
2022-02-17 23:00:18 116
原创 【算法基础课模板笔记+注释】 基础算法10 --- 双指针
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求一个数组排序问题平均时间复杂度为O(nlogn)必然能找到一个答案的问题可以在指针遍历时不加边界可能不能找到的必须加边界模板记忆窗口型双指针for (int i = 0, j = 0; i < n; i ++ ){ 1.根据条件移动j;(j <= i) 2.具体操作;}双数组型双指针for (int i = 0, j = 0; i < n; i
2022-02-17 22:29:24 120
原创 【算法基础课模板笔记+注释】 基础算法09 --- 差分
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求一个数组一段连续区间同时加一个数生成和还原需要O(n),加数需要O(1)模板记忆这个模板分为三个部分:插入:对差分数组操作实现[l,r]都加c生成差分:对每一位插入一遍还原原数组:用差分数组求出原数组模板代码// 插入函数,用b记录原数组的前缀和,对数组的[l, r]范围加cvoid insert(int l, int r, int c){ b[l] += c;
2022-02-17 21:07:03 52
原创 【算法基础课模板笔记+注释】 基础算法08 ---前缀和
声明本文资料参考acwing算法基础课地址:https://www.acwing.com数组概述解决问题:求一个数组中部分连续数的和初始化时间复杂度为O(n),求解时间复杂度为O(1)模板记忆这个模板分为四个部分:输入:s[i] = s[i - 1] + a[i]输出:s[r] - s[l - 1]注意的点:s和a都从1开始模板代码// 输入for (int i = 1; i <= n ;i ++ ) s[i] = s[i - 1] + a[i];// 输出pr
2022-02-17 17:53:45 210
原创 【算法基础课模板笔记+注释】 基础算法07 --- 浮点数二分
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求一个满足某条件的浮点数平均时间复杂度为O(logn)浮点数一般用1e-10表示很小的数一般二分都是循环和[l, r]范围有关模板记忆这个模板分为四个部分:初:确定l和r循环:当r - l在一定范围时,进入循环mid:定mid移动指针:根据mid移动l或r模板代码double n, l, r, mid;cin >> n;l = -10000, r = 1
2022-02-17 17:00:45 156
原创 【算法基础课模板笔记+注释】 基础算法06 --- 整数二分
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:查一个有序数组的某个数平均时间复杂度为O(logn)思想查找第一个满足条件的数:当mid为左侧数的时候,l = mid + 1当mid为右侧数或者满足条件数的时候,r = mid其实要注意的点就是当mid为被查数时,要把r指向mid,因为这是mid右侧不可能是第一个满足条件的数了,但是mid和左侧的数都有可能是最后一个同理模板记忆这个模板分为四个部分:循环:当l ==
2022-02-17 16:27:11 112
原创 【算法基础课模板笔记+注释】 基础算法05 --- 高精度(大整数)
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求大整数的各种运算时间复杂度为O(size)大整数表示使用string读入,使用一个vector数组存储,从0位开始分别表示大整数由低到高的位上数字。// 输入string a;vector<int> A;cin >> a;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'
2022-02-17 15:46:00 49
原创 【算法基础课模板笔记+注释】 基础算法04 --- 逆序对数量
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求一个数组逆序对数量平均时间复杂度为O(nlogn)模板记忆这个模板分为终:递归终点初:初始化mid,把数组分成两部分以便于递归递归:在操作之前递归,这样的话递归到最深层才开始操作填:用3个while把两个有序的数组填到tmp中回:再把q填回tmp注意的点:与归并的不同在于函数返回了long long型递归终点return了0递归调用时使用res记录填入tmp的
2022-02-16 21:13:39 308
原创 【算法基础课模板笔记+注释】 基础算法03 --- 归并排序
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求一个数组排序问题平均时间复杂度为O(nlogn)模板记忆这个模板分为终:递归终点初:初始化mid,把数组分成两部分以便于递归递归:在操作之前递归,这样的话递归到最深层才开始操作填:用3个while把两个有序的数组填到tmp中回:再把q填回tmp模板代码const int N = 100010;int q[N], tmp[N];void merge_sort(int
2022-02-16 16:33:29 253
原创 【算法基础课模板笔记+注释】基础算法02 --- 快速选择(第k个数)
声明本文资料参考acwing算法基础课地址:https://www.acwing.com概述解决问题:求一个数组的第k个数最小时间复杂度算法平均时间复杂度为O(n)模板记忆这个模板分为四个部分:终:递归的终点初:初始化指针+枢轴移:移动指针,由3个while + 一个if swap组成递归:递归两侧注意的点:与快排的不同函数返回一个int递归的终点return了一个值,这个值可以是q[l]也可以是q[r]递归部分用一个if语句return一个值模板代码cons
2022-02-16 15:18:12 40
原创 【算法基础课模板笔记+注释】 基础算法01 --- 快速排序
声明本文资料参考acwing算法基础课地址:https://www.acwing.com模板记忆这个模板分为四个部分:终:递归的终点初:初始化指针+枢轴移:移动指针,由3个while + 一个if swap组成递归:递归两侧注意的点:初始的x是可以改的:q[l] 或 q[r] 或 q[l + r >> 1] 或 q[l + r + 1 >> 1]递归的中点是可以改的:j 和 j + 1 或 i - 1 和 i其中q[l] 和 q[l + r >&g
2022-02-16 11:01:48 227 1
原创 PAT 甲级 2019年秋季考试 Forever 个人错误总结
我英语好差,看懂题目就花了好久,暴力解法秒写出,但是不是很好,这题可以dfs我没有买题,所以只是给了大概的思路,不一定ac,可能过测试点不一定能过,只是样例秒过了(暴力还是要处理一定时间的)。题目:7-1 Forever (20 分)“Forever number” is a positive integer A with K digits, satisfying the following constrains:the sum of all the digits of A is m;the s
2020-09-01 15:10:27 271
原创 PAT 甲级 1040 PAT Ranking 个人错误总结
简单字符串,写之前总觉得可能超时不敢这样写,想多了。#include<bits/stdc++.h>using namespace std;map<char,int>mp; int issym(string a){ for(int i=0;i<a.size()/2;i++){ if(a[i]!=a[a.size()-1-i])return -1; } return a.size();}int main(){ string str; getline(cin
2020-08-30 15:43:37 76
原创 PAT 甲级 1151 PAT Ranking 个人错误总结
lca都是套路。#include<bits/stdc++.h>using namespace std;int main(){ int m,n; cin>>m>>n; vector<int>in(n),pre(n); unordered_map<int,bool>mp; unordered_map<int,int>inorder; for(int i=0;i<n;i++){ cin>>in[i];
2020-08-28 23:54:48 92
原创 考研路上的插曲
想写点东西,这两天压力太大,8.24还是25的时候通知我9.5搬宿舍,我的心态直接崩溃了,因为准备了有一个半月pat了吧,结果正好在那一天有事,所以就3天没学习,想了好多事情,从7月初开始,我基本每天都有8-12个小时的学习,现在看好像有点矫枉过正了,之前我觉得浙大必上不可,然后从两个月每天不断地紧绷的状态通过三天的休息打回了原形,回家只想睡觉,之前每天都4点睡7点起。因为我回家吃饭了,老妈专门给我做了3天的饭,好久没吃家里的饭了。貌似经过三天的什么也不学,我看开了,之前我一直心气非常高,看着同学各个去了
2020-08-28 20:36:29 114
原创 PAT 甲级 1146 PAT Ranking 个人错误总结
拓扑排序,简单。#include<bits/stdc++.h>using namespace std;int n,m;vector<int> g[1001];int main(){ cin>>n>>m; int a,b; vector<int>indegree(n+1); for(int i=1;i<=m;i++){ cin>>a>>b; g[a].push_back(b); indegr
2020-08-28 20:27:18 110
原创 PAT 甲级 1111 PAT Ranking 个人错误总结
吐槽一下学校9.5号搬宿舍,真的烦,我回头找同学给搬一下,唉,还要找宾馆考试。。这个题最后一个点RA,可以一小会,发现是一个地方复制忘记该数组,结果竟然前面几个点都过了,真的是运气哈哈哈。#include<bits/stdc++.h>using namespace std;const int INF=1000000000;const int maxn=510;int len[maxn][maxn];int tim[maxn][maxn];int l[maxn],tl[maxn];
2020-08-25 01:12:09 132
原创 PAT 甲级 1087 PAT Ranking 个人错误总结
睡不着,写一道题,dijkstra+dfs卡的点:输出输反了。。还有就是没看懂题,the average happiness (take the integer part only) of the recommanded route的意思我还以为是所有最短的路径平均值,不过过样例就知道了。#include<bits/stdc++.h>using namespace std;const int INF=1000000000;const int maxn=20000;int s2i(st
2020-08-24 03:30:32 120
原创 PAT 甲级 1072 PAT Ranking 个人错误总结
这个题错在没有给vis赋初值,讲道理,我检查了50分钟bug啥也没发现,因为之前做的题不赋初值也能过。。这个不赋就给2分。。还有一个点是string可能是G10,别只读一位。#include<bits/stdc++.h>using namespace std;const int maxn=1020;const int INF=1000000000;int g[maxn][maxn];int n,m,k,ds;int s2i(string str){ if(str[0]=='G
2020-08-23 22:29:17 103
原创 PAT 甲级 1030 PAT Ranking 个人错误总结
dijkstra基本背过了,错误出在下标写错上。。#include<bits/stdc++.h>#define MAXN 510using namespace std;const int INF=1000000000;int n;int g[MAXN][MAXN];int cost[MAXN][MAXN];int d[MAXN];int cc[MAXN];bool vis[MAXN];int pre[MAXN];void dijkstra(int s){ fill(d,
2020-08-23 20:40:42 75
原创 PAT 甲级 1018 PAT Ranking 个人错误总结
好难,这个题,主要是英文阅读理解不行,硬是没找到错误。还有一个点是循环的数组下标用错了,半天没看出来。。主要还是背dijkstra,这个题其实逻辑不难,但是深入复杂的代码,容易把自己搞晕,背板子可以减少不必要的思考。#include<bits/stdc++.h>using namespace std;const int INF=1000000000;int n,c;int g[501][501];int weight[501];int d[501];bool vis[501]
2020-08-23 00:09:42 139
原创 PAT 甲级 1003 PAT Ranking 个人错误总结
dijkstra有点难背。一定要掌握掌握!!#include<bits/stdc++.h>using namespace std;const int INF=100000000;struct node{ int v,dis;};vector<node> g[500];bool vis[500]={};int d[500];int weight[500];int w[500];int num[500]={};int n;void Dijkstra(int
2020-08-22 20:45:20 90
原创 PAT 甲级 1150 PAT Ranking 个人错误总结
一开始没看懂题,还以为是dp旅行商问题。。#include<bits/stdc++.h>using namespace std;bool flag[201];int llist[201][201];int main(){ int n,m; cin>>n>>m; int a,b,l; for(int i=0;i<m;i++){ cin>>a>>b>>l; llist[a][b]=l; llist[b][
2020-08-22 16:38:24 73
原创 PAT 甲级 1142 PAT Ranking 个人错误总结
这个题没看懂题目,一定要在纸上画一下图,这次直接做了,结果错了。。又花了20分钟重新做,太晚了状态不好。错了两个没写输入,和输入参数写错。#include<bits/stdc++.h>using namespace std;bool ll[201][201];int n;int isclique(vector<int> a){ for(int i=0;i<a.size();i++){ for(int j=i+1;j<a.size();j++){ i
2020-08-21 23:21:47 101
原创 PAT 甲级 1126 PAT Ranking 个人错误总结
这个题还要dfs一下判断是否为连通图。要不就只有20分,我以为默认联连通图了。#include<bits/stdc++.h>using namespace std;int d[501];bool ll[501][501];bool flag[501];void dfs(int root){ flag[root]=true; for(int i=1;i<501;i++){ if(ll[root][i]==true&&flag[i]==false)dfs(
2020-08-21 22:31:23 60
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人