普罗列塔丽亚

题解

/ 注册

全部文章 / 题解（共55篇）

题解 | #二叉树遍历#

使用前序和中序序列建树用size()去substr，避免out_of_range #include<iostream> #include<string> using namespace std; struct TreeNode { &nb...

C++

2022-02-16

0 368

题解 | #最短路径问题#

【迪杰斯特拉算法】每轮先更新距离，再选择最近的，用selected数组锁定没用邻接表也没用邻接矩阵，直接用边集硬干，复杂度有点高 #include<iostream> #include<vector> #include<climits>...

C++

2022-02-14

0 380

题解 | #大整数的因子#

判断大整数能否被整除，直接用字符串从最高位开始取余即可 #include<iostream> #include<string> using namespace std; bool isDividable(string&nbs...

C++

2022-02-13

1 647

题解 | #继续畅通工程#

【存在已经建好的道路】答案的思路是已经建好的道路，权值设定为0 我的做法是分成两个队列，先用已建好的道路构造生成树，再处理需要建造的分阶段完成规划 #include<iostream> #include<vector> #include<...

C++

2022-02-12

0 523

题解 | #还是畅通工程#

基于并查集实现克鲁斯卡尔算法两个端点不再同一集合中则union #include<iostream> #include<vector> #include<map> #include<algorithm> using nam...

C++

2022-02-12

0 439

题解 | #Is It A Tree?#

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

C++

2022-02-12

1 436

题解 | #第一题#

【基于map的并查集】题目中给出的结点是离散的，因此不能用数组需要用map<int,int>来映射 #include<iostream> #include<map> using namespace std; map...

C++

2022-02-12

0 419

题解 | #畅通工程#

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

C++

2022-02-12

0 392

题解 | #连通图#

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

C++

2022-02-12

0 451

题解 | #合唱队形#

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

C++

2022-02-12

0 453