- 博客(13)
- 收藏
- 关注
RSS订阅原创 链表常见问题解决思路
链表结点链表结点声明：struct ListNode{ int value; ListNode * next; ListNode(int x) : value(x), next(NULL) {}};常见链表问题解决思路1.1 单链表的逆置方法一：头插法（迭代法）算法思想：逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插...
2020-04-24 12:18:07
1127
2
转载 c++学习笔记——随机数生成
rand（）函数功能：随机数发生器用法：int rand(void)头文件：stdlib.h (c++中为 cstdlib)Note:rand()的内部实现是用线性同余法做的，它不是真的随机数，因其周期特别长，故在一定的范围里可看成是随机的。rand()返回一随机数值的范围在0至RAND_MAX 间。RAND_MAX的范围最少是在32767之间(int)。用unsi...
2020-04-11 10:48:09
584
原创 fill函数与memset函数的区别
头文件：fill函数的头文件为： std;memset函数的头文件为： string.h (c++中为 cstring)fill函数用法：fill(vector.begin(), vector.end(), val);按照单元赋值，将一个区间内的元素都赋予val值；实例：#include <iostream>using namespace std;int ...
2020-04-10 18:30:10
330
原创 图论——关键路径
问题：AOE网：带权有向图，以顶点表示时间，有向边表示活动，边上的权值表示该活动持续的时间；概念：源点：开始顶点成为；汇点 ：结束顶点；关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径；关键活动：关键路径上的活动；每个活动的最早开始时间：该活动的前序活动都已完成，可以进行该活动的时间；每个活动的最晚开始时间：该活动的后续活动要按时完成，该活动必开始的时间；思路：...
2020-04-10 17:41:32
418
1
原创 图论——拓扑排序
思路：从有向无环图（DAG）图中选取入度为0的顶点，输出；从图中删除该入度为0的顶点以及所有以它为起点的边；重复1,2；直到当前图为空，则输出序列为拓扑序列；或者图不存在入度为0的顶点，则图中有环，不存在拓扑序列Note： 为了保存拓扑排序中不断出现的入度为0的顶点，可用队列存储，每次从队首取出入度为0的顶点；代码：#include <iostream>#incl...
2020-04-10 11:20:20
112
原创 图论——最短路径
思路：采用Dijkstra算法；将顶点集合分为S和T；S ：已确定的顶点集合，初始只有源点s；T： 尚未确定的顶点集合；算法反复从集合T中选择当前到源点s最近的顶点u，将u加入S，然后对所有从u出发的边进行松弛操作。选择距离源点最近的点u时，可采用优先队列，避免依次遍历；对于最短路径问题的变式，只需更改松弛操作的条件即可；对于含有负权值的图，不可求解，此时应用Bellman-Fo...
2020-04-10 10:48:23
78
原创 图论——最小生成树
思路：将边按照权值从小到大排序；利用并查集的思想，判断边两个端点是否在同一连通分量，如果不在，则将这条边选中，且合并两个端点；遍历完所有边即可得到最小花费；代码：#include <iostream>#include <algorithm>using namespace std;const int MAXN = 101;struct Edge{...
2020-04-09 22:00:41
91
原创 图论——联通分量
求解连通分量数目思路：采用并查集的模板具体为两个操作：查找、合并代码：#include <iostream>using namespace std;const int MAXN = 101;int father[MAXN];//保存父亲结点的下标int height[MAXN];//结点高度void initial(int n)//初始化函数{ f...
2020-04-09 21:32:13
190
原创 背包问题（0-1背包、完全背包、多重背包）
0-1背包问题问题描述：n件物品，每件物品重量为w[i]，价值为v[i]，现有一个容量大小为m的背包，如何选择使得背包内物品价值最大思路（动态规划）：设置二维数组dp[][]，令dp[i][j]表示前i件物品容量为j的背包所能获得的最大价值，则dp[n][m]为所求解；只考虑第i件物品，可将情况分为放入或者不放入两种：2.1对容量j的背包，不放入第i件物品，则问题转化为将前i...
2020-03-30 11:14:46
240
原创 c++学习笔记之文件函数
c++的文件读取函数https://blog.csdn.net/Cross_Entropy/article/detailsc的文件读取函数https://blog.csdn.net/l740450789/article/details
2020-03-26 20:45:52
109
原创 c++学习笔记——队列
队列头文件：#include <queue>定义：queue<typename> name;//typename为任意数据类型，name为所定义队列名常用函数：函数名返回值q.empty( )判断队列是否为空q.size( )返回当前队列元素个数q.pop( )删除队首元素q.push(x)向队尾添加元素...
2020-03-26 16:33:15
81
原创 KMP算法
KMP算法问题：在字符串匹配问题中，给出两个字符串，文本串test，模式串pattern，如何判断模式串是否是文本串的一个子串KMP算法核心：模式串失配后，不是从下一个字符开始重新匹配，而是利用已有的信息，跳过不可能成功匹配的位置，减少匹配次数，达到快速匹配的目的；失配之后具体要跳过多少位置，可以提前用模式串计算出来，计算出来的结果就存在next[]数组中；next[j] = k;...
2020-03-25 19:31:50
119
原创 大数计算——加减乘除取余
大数计算终于把这几个运算搞明白了，我太菜了。。。。注释写的比较明白了，在不懂得可以评论问；需要哪些部分就敲对应的就行了；写着挺累，，觉得有用的兄弟们给个赞呗~（=/=）核心代码：#include <iostream>#include <cstring>//包含memset函数，方便初始化#include <string>using names...
2020-03-24 16:19:44
318
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人