呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

【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 美团 算法工程师