美团点评 2019校招后台开发方向职位试卷

第一部分选择考IQ；第二部分选择30道很繁杂，主要是java，数据库；编程题第一题是遍历无向图的最短路径，忘记截一下题目了；不过截了第二道。(第一题参考https://www.nowcoder.com/discuss/104554?type=0&order=0&pos=7&page=1的思路；侵删,仅供参考);

第一题:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int e[N];
int main(){
 int n;
 while (cin >> n){
  memset(e, 0, sizeof(e));
  for (int i = 0; i<n - 1; i++){
   int a, b;
   cin >> a >> b;
   e[b] = e[a] + 1;
  }
  int depth = 0;
  for (int i = 1; i <= n; i++)
   depth = e[i]>depth ? e[i] : depth;
  cout << 2 * n - 2 - depth << endl;
 }
 return 0;
}

第二题：

#include <bits/stdc++.h> using namespace std; int main(){
int n,k,t;
while(cin>>n>>k>>t)
{ 
    if (n == 0) cout << 0 << endl;
    vector<int> v0;
    int cnt = 0;
    while (n--)
    {
        int num;
        cin >> num;
        v0.push_back(num);
    }
    map<int, int> dynamic;//维持一个动态表
    for (int i = 0; i < k; i++)
        dynamic[v0[i]]++;
    for (auto j : dynamic)
    {
        if (j.second >= t)
        {
            cnt++;
            break;
        }
    }
    //动态表变化的同时查找是否有满足题意的区间
    for (int i = k; i < v0.size(); i++)
    {
        dynamic[v0[i - k]]--;  dynamic[v0[i]]++;
        for (auto j : dynamic)
        {
            if (j.second >= t)
            {
                cnt++;
                break;
            }
        }
    }
    cout << cnt << endl;
    }
    return 0;
}

#美团##校招##笔试题目##题解##Java工程师#

全部评论

推荐最新楼层

漂移两极

Java

//考完试才做出来，自己写了几个例子试了一下是对的，不知道有没有更高效的思路 import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Scanner; import java.util.Set; public class Main { static class Result{ int back; int notback; public Result(int back,int notback){ this.back = back; this.notback = notback; } } static class Pair{ int p1,p2; public boolean contains(int s){ return p1==s||p2==s; } public Pair(int p1,int p2){ this.p1 = p1; this.p2 = p2; } public int another(int p){ if (p==p1){ return p2; }else return p1; } } public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); s.nextLine(); Set<Pair> pool = new HashSet<Pair>(); for (int i=0;i<n-1;i++){ String[] temp = s.nextLine().split(" "); pool.add(new Pair(Integer.parseInt(temp[0]),Integer.parseInt(temp[1]))); } //System.out.println(pool.size()); System.out.println(func(1,pool).notback); } private static Result func(int i, Set<Pair> pool) { Set<Pair> connted = connected(pool,i); if (connted.size()==0){ //System.out.println(i+","+"0,0"); return new Result(0,0); } pool.removeAll(connted); int m =0,n=0; List<Result> results = new ArrayList<Result>(); for (Pair p:connted){ int v = p.another(i); Result r = func(v,pool); results.add(r); } int max = 0; for (Result result:results){ m += result.back + 2; if (result.back-result.notback>max){ max = result.back-result.notback; } } n = m -max -1; //System.out.println(i+","+m+","+n); return new Result(m,n); } private static Set<Pair> connected(Set<Pair> pool,int target){ Set<Pair> ret = new HashSet<Pair>(); for (Pair p:pool){ if (p.contains(target)){ ret.add(p); } } return ret; } }

美团点评 2019校招 后台开发方向职位试卷

全站热榜

美团点评 2019校招后台开发方向职位试卷