【2018秋招笔试】2018.9.6 美团 算法工程师
前言
美团的算法工程师题型有选择题和编程题,2道编程题过了一道半。
第一题
题目描述:
给了一个生成树,恰好N个点N-1条边,每条边权重相同都是1,从固定起点遍历,求遍历该生成树的每个节点至少一次的最少路费。
注意:遍历到叶子节点之后如果还有没遍历的节点,那么需要返回到分支,继续遍历。但是如果所有节点都遍历完了,则不需要再返回了。
思路:
可以看到路费主要花在返回的路上,那么我们就把最长深度的叶子节点放到最后遍历,这样这个最长深度就不用返回了。
那么最少路费的计算公式便是,(n-1)*2-图最大遍历深度。
所以写一个 dfs 计算生成树的最大深度即可。
提交后AC。
代码:
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MAXN 100010
int g[MAXN][100];
int f[MAXN];
int isv[MAXN];
int maxn = 0;
void dfs(int curp,int curs)
{
int i;
// 当前节点走过了
isv[curp] = 1;
// 当前节点是否全部走过,默认为是
bool isallv = true;
for(i=0;i<f[curp];i++){
if( ! isv[g[curp][i]]){
// 当前节点的第 i 个子节点没有被走过,那么可以走
isallv = false;
dfs(g[curp][i],curs+1);
}
}
if(isallv){
//当前节点的所有子节点都被走过,那么不能再走了,计算走到这儿的最大深度
if(curs>maxn)
maxn = curs;
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
memset(isv,0,sizeof(isv));
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
g[a][f[a]++] = b;
g[b][f[b]++] = a;
}
dfs(1,0);
printf("%d\n",(n-1)*2-maxn);
}
return 0;
}
第二题
题目描述:
忘了
思路:
貌似是个dp(动态规划)题。
提交之后好像过了50%。
代码: 没保存 - -|||
原创声明
转载请注明:呓语 » 【2018秋招笔试】2018.9.6 美团 算法工程师