2月19号
- 其他
- 2025-08-28 03:48:01
寒假每天敲代码的过程中,从先前的什么都不懂,在一步步看题解,学习新知识,运用学到的知识,解决问题,很多时候对数据结构和算法的选择有问题,不能准确选择,这个时候还是得多敲代码,就我自己而言,代码敲多了会让自己更熟练掌握这个知识点,也能更好的去运用,遇到相似的问题还可以举一反三,加深思考和理解.但是我也意识到,我写题时,每次就只会思考一会觉得不会了,就直接放弃思考,看题解了,没有更多的耐心去多理解思考题目,总是依赖题解.在最近这几天,我回头看了之前写的题,有些之前做错了改正的题,隔到现在去看还是会错,说明写错了的题也要时不时去看看,加深记忆,增强理解.通过这个寒假,我学习到了许多知识,同时相比之前也更加自律,很庆幸将这个寒假期间利用了起来来提升自己,希望自己以后变得更好.
这个寒假学习了一些数据结构与算法知识,包括栈,单端队列,双端队列,单向链表,双向链表,树,二叉树,前缀和,差分,并查集,背包问题,还学习了map函数与set函数; map函数: map<int,int>a; a.count(x); //判断x为下标的元素是否在a中,是就返回1,否就返回0; a.erase(x); //删除a中x为下标的元素; a.size(); //返回a中元素的个数; a.clear(); //清空;
map<string,int>a;定义一个string到int对应的map; 自变量为string类型,函数值为int类型;对于每一个string,就有一个int类型的值与它对应; a["wyxniubi"]=1; //赋值; cout<<a["wyxniubi"]; //调用，此时输出1;
二维数组开一个10的5次方*10的5次方,会导致空间复杂度炸死; 我们可以用map函数: map<int,int>a; // 相当于 int a[int] 一个一维数组;
set函数: set是STL的一个关联容器,底层为红黑树; 它可以有序的储存数据,提供快速的查找,添加删除的功能; set<int>q; //以int型为例,默认按键值升序; set<int,grezter<int>>p; //降序排列; set<int>::iterator it //定义一个名为it的迭代器; q.insert(x); //将x插入q中; q.erase(x); //删除q中的x元素,返回1或0,0表示set中不存在x; q.clear(); //清空q; bool b=q.empty(); //判断q是否为空,若是返回1,否返回0; int x=q.size(); //返回q中元素的个数; it=q.find(x); //在q中查找x.返回x的迭代器,若x不存在,则返回指向q尾部的迭代器即q.end(); it=q.lower_bound(x); //返回一个迭代器,指向第一个键值不小于x的元素; it=q.upper_bound(x); //返回一个迭代器,指向第一个键值大于x的元素;
并查集:是一种树形的数据结构; 合并:将两个子集合并成一个集合; 查找:确定某个元素处在哪个集合; f[x]存节点x的父节点:(f[]的初始化) 每个节点是一个集合,每个节点的父节点是自己: for(int i=1;i<=n;i++) f[i]=i ; 查找:(找根节点就是找元素的根) int find(int x) { if(x!=f[x]) f[x]=find(f[x]); return f[x]; } 合并:(把一个集合的根指向另一个集合的根) void unionset(int x,int y) { f[find(x)]=find(y); }
前缀和:数列的前n项求和; 假设有a1,a2,a3,a4,a5,a6...个数; 则前缀和prefix[1]=a1; prefix[2]=a1+a2; prefix[3]=a1+a2+a3; prefix[4]=a1+a2+a3+a4; ..... prefix[n]=a1+a2+a3+a4+....+an; 前缀和用途:降低算法的时间复杂度;处理区间之间的问题; 第i个数到第j个数的和: sum=prefix[j]-prefix[i];
一维数组的前缀和:前n项和 二维数组的前缀和:s[i][j](以a[1]][1]到a[i][j]的对角构成的 i*j 的矩形内所有元素的和; 递推式:s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1]; 求a[3][3]和a[5][5]为对角线的矩阵求和: s[5][5]-s[4][2]-s[2][5]+s[2][2]; 以a[x1][y1]和a[x2][y2]为对角顶点元素的子矩阵的和: S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1];
差分: 假设有a1,a2,a3,a4,a5,a6...个数; 则差分diff[1]=a1-a0; diff[2]=a2-a1; diff[3]=a3-a2; diff[4]=a4-a3; ..... diff[n]=an-a(n-1); 对差分进行前缀和: diff[1]+diff[2]+diff[3]=a3; 对差分数组进行前缀和，就可以的到原数组; 对前缀和数组进行差分,就可以得到原数组; 如果diff[i]+1,在做前缀和时,第i个数开始,原数组都加 1 ; 如果让区间 [i,j] 都加上 x : diff[i]+=x;(让ai到an都加 x ); diff[j+1]-=x;(让aj+1到an都减去 x );
二维数组的差分: d[0][0]=a[0][0]; d[0][j]=a[0][j]-a[0][j-1]; d[i][0]=a[i][0]-a[i-1][0]; 递推式：b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; 对a数组中的(x1,y1)到(x2,y2)之间的元素都加上 c : { b[x1][y1]+=c; b[x2+1][y1]-=c; b[x1][y2+1]-=c; b[x2+1][y2+1]+=c; }
栈(先进后出): 使用前需要引入 stack 头文件; stack<int>a; a.push(); --> 入栈顶部; a.pop(); --> 出栈顶部元素; a.top(); --> 调取顶部元素; a.empty(); --> a中元素为空; a.size(); --> a中元素的数量;
单端队列(先进先出)(尾进头出): 使用前需要引入 queue 头文件; queue<int>a; a.push(); --> 入队列尾部; a.pop(); --> 出队列首部元素; a.front(); --> 调取首部元素; a.back(); --> 调取尾部元素; a.empty(); --> a中元素为空; a.size(); --> a中元素的数量;
双端队列(头尾都能进都能出): 使用时需要引入 deque 头文件; 双端队列支持的操作有 4 个： 在队首插入一个元素; 在队尾插入一个元素; 在队首删除一个元素; 在队尾删除一个元素; deque<int>a; a.front(); --> 调取首部元素; a.back(); --> 调取尾部元素; a.push_front(); --> 在对首插入元素; a.pop_front(); --> 出队列首部元素; a.push_back(); --> 在队尾插入元素; a.pop_back(); --> 出队列尾部元素; a.insert() 在指定位置前插入元素（传入迭代器和元素); a.erase() 删除指定位置的元素（传入迭代器); a.empty(); --> a中元素为空; a.size(); --> a中元素的数量;
链表与数组的区别: 1.数组的地址是连续的; 2.而链表元素在存储时都会配备一个指针,用于指向后续元素,链表是用指针找到下一个元素,所以链表元素可以存储在内存任意位置; 1.通过a[3]找到数组中第四个元素; 2.而链表则需要从头开始遍历; 1.数组中删除元素,则需要把其后面元素都往前移一位; 2.链表中删只需要找到元素后,让前一个data的指针指向后一个data,释放该元素就行;
树: 顶部节点:根节点; 父节点和子节点; 没有子节点的节点:叶子结点; 数中一个节点的子节点个数称为该节点的度; 数中度数最大称为该数的度;
二叉树: 每个节点只有两个子节点:左子结点和右子节点; 二叉树的形态: 左斜树:只有左子结点; 右斜树:只有右子节点; 就是链表!!!(一个指针); 满二叉树:最下方的叶子节点无左右子节点,其余都有; 完全二叉树:叶子节点是允许缺失的,且叶子结点都必须靠左排序; (链表里面两个指针); 5: 4 6: 1 2 7 8: 遍历顺序: 前序:(中左右) 5 4 1 2 6 7 8 ; 中序:(左中右) 1 4 2 5 7 6 8 ; 后续:(左右中) 1 2 4 7 8 6 5 ;
01背包问题: 有 n 件物品和一个容量是 m 的背包;每件物品只能使用一次; 第 i 件物品的体积是 w,价值是 v; 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大; 输出最大价值; 输入格式: 第一行两个整数，N，V，用空格隔开，分别表示物品数量和包容积; 接下来有 N 行，每行两个整数 v , w ,用空格隔开,分别表示第i件物品的体积和价值; 输出格式: 输出一个整数，表示最大价值; dp[j]: 表示背包容量为 j 时的最大值; dp[i][j]: 表示在背包容量为 j 时,从下标为 0 到 i 的物品里取任意的最大值; 思路:当前物品 i 能不能放得下背包 j ; 1.放不下:不放,继承上一层的状态; 2.放得下:考虑要不要放; a.不放:继承上一层状态; b.放:背包容量剩余 j-w[i]; (w[i]是体积,v[i]是价值); 二维代码: for(int i=1;i<=n;i++){ for(int j-1;j<=m;j++){ if(j<w[i]) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); } } cout<<dp[n][m]; 一维代码: for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[m];
完全背包问题: 有 n 种物品和一个容量是 m 的背包;每种物品都有无限件可用; 第 i 种物品的体积是 w ,价值是 v ; 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大; 输出最大价值; 输入格式: 第一行两个整数, n, m,用空格隔开,分别表示物品种数和包容积; 接下来有 n 行,每行两个整数 w ,v ,用空格隔开,分别表示第 i 种物品的体积和价值; 输出格式: 输出一个整数,表示最大价值; 思路: 先继承上一层状态,(放不放得下); 放得下,考虑要不要放: 1.不放,继承上一层状态; 2.放,背包容量剩余 j-w[i]; 二维代码: for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dp[i][j]=dp[i-1][j]; if(j>=w[i]){ dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]); } } } cout<<dp[n][m]; 一维代码: for(int i=1;i<=n;i++){ for(int j=w[i];j<=m;j++){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[m];
多重背包问题: 有 n 种物品和一个容量是 m 的背包; 第 i 种物品最多有 s 件,每件体积是 w ,价值是 v ; 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大; 输出最大价值; 输入格式: 第一行两整数, n , m ,用空格隔开,分别表示物品种数和背包容积; 接下来有 n 行,每行三个整数 w , v , s ,用空格隔开,分别表示第 i 种物品的体积、价值和数量; 输出格式: 输出一个整数,表示最大价值; w[i]表示物体体积; v[i]表示物体价值; s[i]表示物体数量; 法一:转换成01背包问题; for(int i=1;i<=n;i++){ for(int k=1;k<=s[i];k++){ for(int j=m;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } } cout<<dp[m]; 法二:二进制优化法; for(int i=1;i<=n;i++){ int k=1,p=0; cin>>w>>v>>s; while(k<=s){ v[++p]=v*k; w[p]=w*k; s-=k; k*=2; } if(s){ v[++p]=v*s; w[p]=w*s; } } for(int i=1;i<=p;i++){ for(int j=m;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[m];
