普罗列塔丽亚 - 个人主页动态 - 牛客网

发布(55) 刷题

普罗列塔丽亚

2022-02-16 13:48

实验室研究员/技术员

题解 | #二叉树遍历#

使用前序和中序序列建树 用size()去substr，避免out_of_range #include<iostream> #include<string> using namespace std; struct TreeNode {     char data;     TreeNode *lchild=NULL,*rchild=NULL; }; void BuildTree(TreeNode *root,string pre,string mid){     root->data...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-14 17:30

已编辑

实验室研究员/技术员

题解 | #最短路径问题#

【迪杰斯特拉算法】 每轮先更新距离，再选择最近的，用selected数组锁定 没用邻接表也没用邻接矩阵，直接用边集硬干，复杂度有点高 #include<iostream> #include<vector> #include<climits> #include<queue> using namespace std; struct Edge{     int a,b,distance,cost; }; int main(){ &nbs...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-13 22:27

实验室研究员/技术员

题解 | #大整数的因子#

判断大整数能否被整除，直接用字符串从最高位开始取余即可 #include<iostream> #include<string> using namespace std; bool isDividable(string num,int divider){     int total = 0;     for(int i=0;i<num.size();i++){  &n...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-12 18:26

实验室研究员/技术员

题解 | #继续畅通工程#

【存在已经建好的道路】 答案的思路是已经建好的道路，权值设定为0 我的做法是分成两个队列，先用已建好的道路构造生成树，再处理需要建造的 分阶段完成规划 #include<iostream> #include<vector> #include<algorithm> using namespace std; struct Edge{     int a,b;     int cost;  &n...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-12 16:39

实验室研究员/技术员

题解 | #还是畅通工程#

基于并查集实现克鲁斯卡尔算法 两个端点不再同一集合中则union #include<iostream> #include<vector> #include<map> #include<algorithm> using namespace std; struct Road {     int a,b,cost; }; bool isShort(Road a,Road b){    ...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-12 15:48

实验室研究员/技术员

题解 | #Is It A Tree?#

【基于并查集判断树】 +无环(a->b,b->a)：getRoot(a)!=b +无多入(a->b,c->b)：parent[b]==b +必连通：计算连通子图数 #include<iostream> #include<map> #include<string> using namespace std; int getRoot(map<int,int> parent,int i){     while(p...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-12 15:00

实验室研究员/技术员

题解 | #第一题#

【基于map的并查集】 题目中给出的结点是离散的，因此不能用数组 需要用map<int,int>来映射 #include<iostream> #include<map> using namespace std; map<int,int> parent; int getRoot(int i){     if(parent.find(i)==parent.end()) parent[i] = i; &nb...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-12 14:50

实验室研究员/技术员

题解 | #畅通工程#

【并查集求极大连通子图数量】 i==getRoot(i)的数量就是极大连通图的数量 再-1就是最少还需几条路 #include<iostream> using namespace std; int parent[1000]; void init(int n){     for(int i=0;i<n;i++){         parent[i] =&nbsp...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-12 14:43

实验室研究员/技术员

题解 | #连通图#

【利用并查集检查图连通性】 不断Union，然后检查getRoot(i)==i有多少个即有多少极大连通子图 #include<iostream> using namespace std; int parent[1001]; void init(int n){     for(int i=0;i<n;i++){         parent[i] = i;...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-12 02:44

实验室研究员/技术员

题解 | #合唱队形#

【勘误】题目没说清楚，不一定严格的先增后减，单调增/减也可以 【思路】 求从0开始、以i结束的最长递增序列 求从i开始、以n结束的最长递减序列 再根据以上两个数组求出以k为分割点的最长合唱队形 最后减法得出最少出列个数 #include<iostream> #include<math.h> using namespace std; int main(){          int n;    &nbsp...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-12 01:17

实验室研究员/技术员

题解 | #最大上升子序列和#

【最长递增子序列】 dp[i]表示“以i结尾”(指必须取num[i])的最长递增子序列长度，因此结果可以累加到dp[n]，直接取dp[n]即可 【最大递增子序列和】 dp[i]表示“从0到i”(可以不取num[i])的最大递增子序列和，各自结果独立，因此需要求max #include<iostream> #include<math.h> using namespace std; int main(){     int n;  ...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-11 19:52

实验室研究员/技术员

题解 | #最大连续子序列#

没看清题目要求，数字全<0时输出0 0 N-1 maxEnd在每次重新开始时更新即可 maxStart不好记录，倒推即可 #include<iostream> #include<climits> #include<math.h> using namespace std; int main(){          int K;     int data[1000...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-11 19:25

已编辑

实验室研究员/技术员

题解 | #最大序列和#

“连续序列”，直接线性dp即可 因为只能是连续序列，最值无法传递到末尾 所以使用一个maxSum来记录最值 #include<iostream> #include<math.h> using namespace std; int main(){          int N;     int seq[1000000];     long&...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-11 16:27

实验室研究员/技术员

题解 | #神奇的口袋#

【01背包问题】从后往前滚动数组 【要求凑整数】边界值：[0][0]=1，0枚硬币凑0面值、算一种方案；[0][j]=0 【统计方案数】转移方程：a+b #include<iostream> #include<climits> using namespace std; //0-1背包的凑整问题统计方案数 int main(){          int n;     int ...

0 点赞评论收藏

转发

普罗列塔丽亚

2022-02-11 14:07

实验室研究员/技术员

题解 | #最小邮票数#

用没有状态压缩的二维数组来动态规划 第i行考虑加入第i张邮票 第j列考虑目标面值为j 用结构体存每个位置凑出的最接近j的面值price和所需的最小张数num 最后看dp[N][M].price是否等于M，输出其num即可 比较烦人的是状态转移 #include<iostream> using namespace std; struct node {     int price;     int ...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务