TomatoHead

分类

/ 注册

全部文章（共16篇）

题解 | #最短路径问题#Dijkstra算法#最详细

本题为单源最短路径问题，故可以考虑使用迪杰斯特拉算法，传入一个整型变量作为起点，同时维护两个全局记录最短距离和最小花费的数组。在迪杰斯特拉算法的内部，通过对邻接表的遍历更新这两个数组，遍历完成后数组下标对应的元素即为所得，打印即可。详细算法步骤见注释 #include <bits/stdc++...

2024-03-23

0 320

题解 | #还是畅通工程#

本题关键在于如何实现克鲁斯卡尔算法。该算法需要将边从小到大进行排序，每次选出不会成环且最小的边，直到边数为节点数减去1，意味着最小生成树生成完成 /*请计算最小的公路总长度。输入描述：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应...

2024-03-22

0 196

题解 | #畅通工程#并查集思想

写好并查集的查和并两个模块后，我们考虑，每次新输入的边代表着两个节点直接有关联，我们只需要把其中一个节点置为另一个节点的子节点，就可以维护一个并查集结构。直到遍历结束，此时用一个整型变量记录剩余并查集数量。代表着类似于自治域的不连通的模块，我们只需要在这n个模块之间修n-1条路就可以使其联通，故打印...

2024-03-21

0 204

题解 | #二叉树遍历#

简单的数组建树＋中序遍历 #include <bits/stdc++.h> using namespace std; struct TreeNode { char data; TreeNode* left; TreeNode* right; }; TreeNode...

2024-03-20

0 208

题解 | #搬水果#做法同哈夫曼树#优先队列

#include <bits/stdc++.h> using namespace std; int main() { int n,m; priority_queue<int> Myqueue; scanf("%d",&n)...

2024-03-20

0 160

题解 | #哈夫曼树#优先队列

运用优先队列，可以将哈夫曼树序列的数字从小到大排列（借助负数取反技巧)当队列中至少有两个元素的时候，取出队列头的两个元素相加，权重和加上这个数之后，把这个数重新压入优先队列，重复操作。 #include <bits/stdc++.h> using namespace std; int...

2024-03-20

0 173

题解 | #复数集合#优先队列#重载运算符

本题思路很简单，借助重载运算符和优先队列，我们可以很容易的将输入的复数进行从大到小排列并输出，每次根据具体情况决定打印顺序即可。主要应该关注重载运算符和构造函数的使用，以及优先队列隐含的数据类型必须支持小于运算符的思想。重载运算符也是把大根堆变成小根堆的方式之一 #include <bits/...

2024-03-20

0 190

题解 | #二叉搜索树#重要模板#

本题思路是在于，根据给定的序列先插入一棵二叉搜索树，随后的序列中，如果有序列的先序和中序序列与其完全一致，则证明后续建树的二叉搜索树和自己一致。需要三个函数：1.建树函数，参数为当前根节点和将要插入的数值2.中序遍历函数，参数为根节点的指针，返回字符串3.先序遍历函数，参数为根节点的指针，返回字符串...

2024-03-20

0 180

题解 | #最长公共子序列(一)#二维动态规划

思路：本题需要处理两个字符串的最长公共子序列（可以不连续），故考虑使用一个二维的dp数组，存储遍历两个字符串时每个子问题对应的最长公共子序列长度解法：用两个变量i和j分别遍历两字符串，不妨对于每个i，都遍历j。对于此时的dp[i][j]，如果此时两字符串中i和j分别指向的元素相等，立刻将dp[i][...

2024-03-15

1 227

题解 | #吃糖果#北京大学机试

原理同上台阶问题 #include <iostream> #include <cstdio> #include <vector> #include <string> #include <set> using namespace std; i...

2024-03-15

2 193