首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
TomatoHead
获赞
4
粉丝
0
关注
0
看过 TA
22
大连理工大学
2024
算法工程师
IP属地:江西
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑TomatoHead吗?
发布(36)
刷题
TomatoHead
03-23 17:17
大连理工大学 计算机类
题解 | #最短路径问题#Dijkstra算法#最详细
本题为单源最短路径问题,故可以考虑使用迪杰斯特拉算法,传入一个整型变量作为起点,同时维护两个全局记录最短距离和最小花费的数组。在迪杰斯特拉算法的内部,通过对邻接表的遍历更新这两个数组,遍历完成后数组下标对应的元素即为所得,打印即可。详细算法步骤见注释 #include <bits/stdc++.h> using namespace std; int MAXNUM = 1010; int INF=INT_MAX; struct Edge {//边表,记录目标节点,路径长度,花费 int to; int length; int price; Edg...
0
点赞
评论
收藏
转发
TomatoHead
03-22 18:42
大连理工大学 计算机类
题解 | #还是畅通工程#
本题关键在于如何实现克鲁斯卡尔算法。该算法需要将边从小到大进行排序,每次选出不会成环且最小的边,直到边数为节点数减去1,意味着最小生成树生成完成 /*请计算最小的公路总长度。输入描述:测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离, 每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。当N为0时,输入结束,该用例不被处理。 输出描述:对每个测试用例,在1行里输出最小的公路总长度。 输入: 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 ...
0
点赞
评论
收藏
转发
TomatoHead
03-21 16:48
大连理工大学 计算机类
#判断图是否是树#并查集#北京大学复试
https://www.acwing.com/problem/content/3412/思路:本题需要判断一个图是否为树,这需要我们判断三个要素:1.一个树的边数应该比节点数少12.一个树的节点入度应该小于等于2,且只有一个入度为0的节点即根节点 3.从根节点到任意节点有且仅有一条唯一路线1我们使用两个计数变量edgecount和vertexcount解决,2我们用入度数组和访问数组解决,3我们用并查集解决,并维护一个布尔型变量记录当前是否判断可以成树注意点:1.每次完成后需要将数组变量进行初始化防止影响下一步2.将布尔型变量修改后不需要return而是应该继续循环直到所有数据都处理完成 /*...
0
点赞
评论
收藏
转发
TomatoHead
03-21 16:00
大连理工大学 计算机类
题解 | #畅通工程#并查集思想
写好并查集的查和并两个模块后,我们考虑,每次新输入的边代表着两个节点直接有关联,我们只需要把其中一个节点置为另一个节点的子节点,就可以维护一个并查集结构。直到遍历结束,此时用一个整型变量记录剩余并查集数量。代表着类似于自治域的不连通的模块,我们只需要在这n个模块之间修n-1条路就可以使其联通,故打印n-1 #include <bits/stdc++.h> using namespace std; int father[1010]; int setcount;//记录剩余未进行合并操作的子集 void initialize(int n) { for (int i = 0; ...
0
点赞
评论
收藏
转发
TomatoHead
03-20 20:26
大连理工大学 计算机类
题解 | #二叉树遍历#
简单的数组建树+中序遍历 #include <bits/stdc++.h> using namespace std; struct TreeNode { char data; TreeNode* left; TreeNode* right; }; TreeNode* BuileTree(int& i, char arr[]) { char c = arr[i]; i++; if (c == '#') { return NULL; } else { TreeNode* pNew = new...
0
点赞
评论
收藏
转发
TomatoHead
03-20 19:18
大连理工大学 计算机类
题解 | #搬水果#做法同哈夫曼树#优先队列
#include <bits/stdc++.h> using namespace std; int main() { int n,m; priority_queue<int> Myqueue; scanf("%d",&n); int wpl=0; for(int i=0;i<n;i++){ scanf("%d",&m); Myqueue.push(-1*m); } while(Myqueue.size()>=2){...
0
点赞
评论
收藏
转发
TomatoHead
03-20 17:11
大连理工大学 计算机类
题解 | #哈夫曼树#优先队列
运用优先队列,可以将哈夫曼树序列的数字从小到大排列(借助负数取反技巧)当队列中至少有两个元素的时候,取出队列头的两个元素相加,权重和加上这个数之后,把这个数重新压入优先队列,重复操作。 #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); priority_queue<int> Myqueue; for (int i = 0; i < n; i++) { int m; ...
0
点赞
评论
收藏
转发
TomatoHead
03-20 16:43
大连理工大学 计算机类
题解 | #复数集合#优先队列#重载运算符
本题思路很简单,借助重载运算符和优先队列,我们可以很容易的将输入的复数进行从大到小排列并输出,每次根据具体情况决定打印顺序即可。主要应该关注重载运算符和构造函数的使用,以及优先队列隐含的数据类型必须支持小于运算符的思想。重载运算符也是把大根堆变成小根堆的方式之一 #include <bits/stdc++.h> using namespace std; struct Complex { //结构体定义,复数可表示为a+bi int a; int b; Complex(int _a,int _b){ //构造函数 a = _a; ...
0
点赞
评论
收藏
转发
TomatoHead
03-20 16:16
大连理工大学 计算机类
题解 | #二叉搜索树#重要模板#
本题思路是在于,根据给定的序列先插入一棵二叉搜索树,随后的序列中,如果有序列的先序和中序序列与其完全一致,则证明后续建树的二叉搜索树和自己一致。需要三个函数:1.建树函数,参数为当前根节点和将要插入的数值2.中序遍历函数,参数为根节点的指针,返回字符串3.先序遍历函数,参数为根节点的指针,返回字符串注意!!!建树函数的参数根节点需要用引用符号,因为会直接修改原root的值作为下一个参数传入,不然BST树会一直为空 /*判断两序列是否为同一二叉搜索树序列 输入描述: 开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。 接下去一行是一个序列,序列长度小于...
0
点赞
评论
收藏
转发
TomatoHead
03-18 10:15
大连理工大学 计算机类
#广度优先遍历应用#玛雅人的密码#清华大学机试
https://www.acwing.com/problem/content/3388/思路:本题难点在于,如何确保所有可能的子序列都被遍历到,还要保证不能重复遍历。相比于深度优先,广度优先一层一层来的思想更好的保证了这一基本原则,把每一经过旋转的子序列看作是下一层,同时维护一个数据结构记录是否被访问即可解法1.读入数据,若数据小于4直接返回-1;若大于,则维护一个无序map记录是否被访问,一个辅助队列进行广度优先遍历,一个cur字符串记录当前的子序列。将原始字符串压入栈中2.当栈不为空时,先弹出栈顶字符串检查是否有2012,语法采用cur.find("2012" )!= ...
0
点赞
评论
收藏
转发
TomatoHead
03-17 16:59
大连理工大学 计算机类
#广度优先遍历之树的高度#南京理工大学机试
https://www.acwing.com/problem/content/3702/思路:本题明面上是求树的高度,但却给出了类似于邻接表的存储方式,类似于一张无环图,但完全不知道节点之间的父子关系。考虑两种搜索方式,层序遍历可以严格保证先父后子的遍历顺序,故采用层序遍历。同时设置一个辅助数组来记录节点是否被访问过,如有,则证明是当前节点的父辈。做法:分别定义一个vector<vector<int>>型的邻接表结构,一个存储遍历顺序的队列toVisit,一个记录是否访问和最大长度的数组distance,循环访问邻接表。初始将固定的根节点压入队列。当队列不为空时:1.读...
0
点赞
评论
收藏
转发
TomatoHead
03-16 15:03
已编辑
大连理工大学 计算机类
#背包#动态规划#北京大学上机题
https://www.acwing.com/problem/content/3445/思路:对背包dp模板稍加修改,注意转移方程和初始化的方法即可解法:新建dp数组dp[i][j],表示用i个物品凑齐j体积的方法总数,按顺序读取N和物品体积序列之后:1.将dp数组的dp[0][0]置为02.用i和j进行遍历a.对于每一个dp[i][j],首先先把dp[i-1][j](代表少一件凑齐j的方法)赋值给他,意味着这件物品不能使用,故保留上一种方法的数量b.判断,如果此时可以使用这个物品,dp[i][j]就要再加上用i-1件物品凑齐j-arr[i]的方法c.直到遍历结束,打印dp[n][40]即可 ...
0
点赞
评论
收藏
转发
TomatoHead
03-16 11:11
已编辑
大连理工大学 计算机类
#dp背包#北京大学机试题
https://www.acwing.com/problem/content/3448/想法:套二维数组dp公式,先找到小问题及转移方程解法:将题目所述数据读入整型变量c,n和价格数组p[]以及评价数组v[];1.新建一个大小为1001*102的dp数组dp[i][j],每个元素表示:在预算为j元的时候,考虑从0到j号菜品组合中评价最高的评分2.双for循环遍历,注意i是从1到c,j是从1到n(上限取等号)3.对于某个i,遍历的每一个j:a.检查j菜品是否超出价格i,若超出则将上一个菜品对应的评分(dp[i][j-1])赋值给当前评分(dp[i][j])b.若没有超出,则选择上一个菜品对应的评...
0
点赞
评论
收藏
转发
TomatoHead
03-15 15:39
大连理工大学 计算机类
题解 | #最长公共子序列(二)#二维动态规划#上交机试
https://www.acwing.com/problem/content/3511/本题主要思路与上题类似,头文件只用到了一部分我懒得调所以都粘上来了修改的地方:由于需要连续的公共子序列,且只要小写字母不要数字,故相比(一)做出如下改动1.if语句条件改为判断此时是否为小写字母&&两字符串元素是否相等2.满足if语句则仍将该节点值置为上一节点的值加一,同时判断该节点值是否超过由整型变量currentmax记录的最大值,若超过则更新currentmax2.若不满足if语句则将该节点值置为0(为了保证连续子串的性质) #include <bits/stdc++.h>...
0
点赞
评论
收藏
转发
TomatoHead
03-15 15:04
大连理工大学 计算机类
题解 | #最长公共子序列(一)#二维动态规划
思路:本题需要处理两个字符串的最长公共子序列(可以不连续),故考虑使用一个二维的dp数组,存储遍历两个字符串时每个子问题对应的最长公共子序列长度解法:用两个变量i和j分别遍历两字符串,不妨对于每个i,都遍历j。对于此时的dp[i][j],如果此时两字符串中i和j分别指向的元素相等,立刻将dp[i][j]赋值为dp[i-1][j-1]+1;反之,则在该节点的上方和左方选择较大的节点值修改进dp[i][j]。最后输出dp[n][m]即可 #include <iostream> #include <cstdio> #include <vector> #includ...
0
点赞
评论
收藏
转发
1
2
3
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务